07/19/20221)158.ReadNCharactersGivenread4II-CallMultipleTimes(Hard)注意提供的read4(buf4)函数2)735.AsteroidCollision思路：注意只有positive+negative会相遇，negative+positive反方向不会相遇。区分几种情况，正大负小，同样大小，正小负大。使用Stack来存储、消除和弹出。3)716.MaxStack(Hard)idea:用list模拟stackDoubleLinkedList+TreeMap4)238.ProductofArrayExceptSelfidea:记录0的个数，和所有其他不为0的数的乘积，分类讨论5)642.设计搜索自动完成系统（困难）思想：存储按热度和字母表排序的历史记录，以及热度字典，每次遇到#时更新Trie6)365.水和水壶问题思想：数学方法，关键思想是结果是x和y的线性组合（因为每一步都是x和y的线性组合，无论走多少步，仍然是x和y的线性组合，每一步都是当前值的0或1倍，所以每个值都是可能的，只要0<=ax+by<=x+y)根据Bézout恒等式，ax+by=m有整数解当且仅当m是最大公约数da和b（最大公约数，gcd）。求最大公约数的方法是先用大数除以小数，再除以出现的余数（第一个余数），再用第一个余数除以出现的余数（第二个余数），以此类推，直到最后的余数为0。defcomputeGCD(x,y):while(y):x,y=y,x%yreturnabs(x)BFS广度优先搜索每一步有6种可能性将jug1的内容倒入jug2。（注意jug1在将水倒入jug2后可能还有一些水）将jug2的内容物倒入jug1。(注意jug2在往jug1倒水后可能还有水)Emptyjug1completelyEmptyjug2completely.Fillitjug1(maximumlimit)Filljug2completely(toitsmaximumlimit)遍历这6种可能性，每一种可能性都可以下一步产生6种可能，直到等于目标，或者循环出现ax+by(a,b)（类型有限，因为00:num_of_chars_to_be_included-=1#我们减少hash_map值hash_map[s[end]]-=1#如果当前窗口有所有需要的字符whilenum_of_chars_to_be_included==0:#如果end-start+10:num_of_chars_to_be_included+=1#向前移动开始以找到更小的窗口start+=1#向前移动结束以找到另一个有效的windowend+=1ifmin_window_length==len(s)+1:return""else:returns[min_window_start:min_window_start+min_window_length]08/14/202212)91.解码方式输入：s="226"输出：3解释：“226”可以解码为“BZ”（226）、“VF”（226）或“BBF”（226）。思路：1.Recursive，但是如果你尝试不加@lru_cache(maxsize=None)，会超时吗？2.迭代，动态规划，dp=[0for_inrange(len(s)+1)]存储子问题结果，每次测试1个数字和2个数字的可能性13)200.IslandsInput:grid=[["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]输出：3思路：遍历，遇到1时count+=1并进位出DFS，把所有和它相连的1都换成#等其他符号，表示已经统计完了，然后再找下一个没有变成#的1（新岛）14)426.将二叉搜索树转换成有序的双链表输入：root=[4,2,5,1,3]输出：[1,2,3,4,5]思路：递归，DFS。定义first和last变量，先往左找first，返回last节点相互连接，依次类推，直到最右边的last，然后first和last连接起来。deftreeToDoublyList(self,root:'Node')->'Node':如果不是root:返回Nonefirst,last=None,Nonedefhelper(node):nonlocalfirst,lastifnode:helper(node.left)iflast:last.right=nodenode.left=lastelse:first=nodelast=nodehelper(node.right)helper(root)last.right=firstfirst.left=lastreturnfirst15)144.二叉树预序遍历Pre-顺序，NLR访问当前节点。递归遍历当前节点的左子树。递归遍历当前节点的右子树。输入：root=[1,null,2,3]输出：[1,2,3]思路：1.recursive2.iterative，在每个节点用stack保存root，遍历左边，然后popstack16)1028.RecoveraTreeFromPreorderTraversal(Hard)迭代，在每个节点用stack存根，遍历左边，然后不断popstack17)208.实现Trie（PrefixTree）前缀树，也叫字典树。它是一棵N叉树。前缀树用于存储和查找字符串。前缀树的每个节点代表一个字符串的前缀。每个节点都有多个子节点，通往不同子节点的路径具有不同的特征。子节点表示的字符串由节点本身的原始字符串和通往子节点的路径上的所有字符组成。前缀树的一个重要特点是节点的所有后代都有一个与该节点相关的字符串的共同前缀，这就是前缀树名称的由来。没看懂回答。18)114.FlattenBinaryTreetoLinkedList注意就地修改def__init__(self):self.prev=Nodefflatten(self,root):ifnotroot:returnNoneself.flatten(root.right)self.flatten(root.left)root.right=self.prevroot.left=Noneself.prev=root18)22.生成括号输入：n=3输出：["((()))","(()())""(())()","()(())","()()()"]思路：1.蛮力会超时2.回溯。与其像方法1中那样每次都添加“(”或“)”，不如让我们仅在知道它将保持有效序列时才添加它们。我们可以通过跟踪到目前为止放置的左括号和右括号的数量来做到这一点。3.闭合数。该问题可以简化为两个独立的子问题。一个是关于这些括号内的括号，另一个是关于右边的括号。19)210.CourseScheduleIInput:numCourses=4,prerequisites=[[1,0],[2,0],[3,1],[3,2]]输出：[0,2,1,3]解释：总共有4门课程要修。至对于课程3，您应该完成课程1和课程2。课程1和2都应该在您完成课程0之后学习。所以一个正确的课程顺序是[0,1,2,3]。另一个正确的顺序是[0,2,1,3]。思路：1.深度优先搜索2.节点入度没看懂20)98.验证二叉搜索树判断是否是有效的二叉搜索树（BST）。思路：1.RecursiveTraversalwithValidRange2.IterativeTraversal3.RecursiveInorderTraversal4.IterativeInorderTraversal21)3.LongestSubstringWithoutRepeatingCharacters输入：s="pwwkew"输出：3解释：答案是“wke”，长度为3。注意答案必须是一个子串，“pwke”是一个子序列而不是一个子串。思路：滑动窗口
