LeetCode刷题笔记 - Lyft高频题

07/19/2022

1) 158. Read N Characters Given read4 II - Call Multiple Times

2) 735. Asteroid Collision

思路: 注意只有正+负会相遇，负+正是反方向不相遇。区分几种情况，正大负小，一样大，正小负大。用Stack存储，消除就pop。

3) 716. Max Stack

思路:

1. 用list模拟stack
2. Double Linked List + TreeMap

4) 238. Product of Array Except Self

思路: 记录0的数量，和非0的其他所有数的乘积，分类讨论

5) 642. Design Search Autocomplete System

思路:

1. 存按热度和alphabete排序的history,以及热度dict,每次遇到#就进行更新
2. Trie

6) 365. Water and Jug Problem

思路:

1. math方法，key idea是结果是x和y的线性组合（因为每一步操作都是x和y的线性组合，所以不管进行了多少步，仍然是x和y的线性组合，且每一步都是当前值的0或1倍，所以每种取值都是有可能的，只要0<=ax+by<=x+y)
   根据Bézout's identity，ax+by=m有整数解时当且仅当m是a及b的最大公约数d（greatest common divisor，gcd）的倍数。
   求最大公约数的方法是，用较小数除较大数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。

    def computeGCD(x, y):
       while(y):
           x, y = y, x % y
        return abs(x)

2. BFS Breadth-first search
   每一步都有6个可能性
   Pour contents of jug1 to jug2. (note that jug1 may still have some water left after pouring water to jug2)
   Pour contents of jug2 to jug1. (note that jug2 may still have some water left after pouring water to jug1)
   Empty jug1 completely.
   Empty jug2 completely.
   Fill jug1 completely (to its maximum limit)
   Fill jug2 completely (to its maximum limit)
   遍历这6种可能性，每一种可能性下一步又能衍生出6种可能性
   直到等于target，或者ax+by的(a,b)出现循环（有限种，因为0