9/17 Mon
感觉自己DFS的掌握太差了，打算今天主要看DFS的题目，希望能有点感觉 新题 109. Convert Sorted List to Binary Search Tree (the same as 108) （Medium）
此题需要将linkedList来build tree。一定要建立helper function来recursively call itself 并且是用DFS不断增加深度。buildTree的task其实就是每次找到root 节点，并且在建立root.left和root.right 时不断call function。找到root节点就是要找到一个list中间的值，回想linkedlist的找middle节点的方法是用快慢指针的方法！ 113. Path Sum II (Medium)
Backtracking 问题。老步骤，向helper function传入root， 总res，当前的depth， 当前currList。一进入helper function立马加入当前节点，再讨论root节点和非root节点的情况。重要的一步：最后时刻remove掉currList中的最后一个。 210. Course Schedule II
Topological Sorting. 深度最深的课程表示：被其他课程依赖最多的->应该最先修的课程，与207code变化不大，增加一个result list，在dfs中每次结束运算，添加到res即可 513. Find Bottom Left Tree Value BFS
Doing BFS from right to left will simply return the last node in the queue
旧题 108. Convert Sorted Array to Binary Search Tree
比109题简单，因为是array，直接可以用left index and right index 来找处在middle 位置的值 111 Min Depth of Binary Tree
Return (left == 0 || right == 0 ) ? left + right + 1: Math.min(left, right) + 1;
意思为如果左右subtree有一个为null时，那么就一定要left + right + 1而不能取最小的0 112 Path Sum
求是否存在从root到leaf节点value的和等于sum。Recursive function：针对三种情况讨论：1）node为null 2）该node是最后的leaf节点并且等于sum 3）recursive该node的left和right。 207 Course Schedule
Topological Order. 建立graph来存每节课所要求的prerequisites。用一个int array来存每个结点的访问状态 1 = visiting；2 = visited. 再对每一节课过一遍dfs查看是否有环。在dfs中对每个点的prerequisites也过一遍dfs看是否有环。
今日收获🌺
• 如何判断是backtracking呢？
○ 看同一个level（depth）是是否面临着多重选择，那么就需要用backtracking的老套路
• Topological Sorting (with DFS)
○ Topological Sorting is mainly used for scheduling jobs from the given dependencies among jobs.
○ 时间复杂度： O(V + E) V: vertex; E: Edges, 当依赖关系越多，E越接近于V的数量，就几乎是线性时间
• DFS 与 Topological 的区别
○ In DFS, we print a vertex and then recursively call DFS for its adjacent vertices. Print-> “5 2 3 1 0 4”, In Topological, we need to print a vertex before its adjacent vertices. (有前后顺序) 例如：4或者5一定要比 0 node先print出来
○ In DFS, helper function只有一个返回状态；In Topological sort, 有两个返回状态： visited & visiting 来判断graph中有无环出现
9/20 Thur First Missing Positive
和find duplicate number, find missing number 题目的做法是一样的，就是利用number和idx的关系来， 有了num，得到idx = num - 1 然后将它变成负数，最后iterate整个array， 哪一个number没有变成负数，那么它做对应的idx + 1就是丢失的
这道题唯一不同的就是将负数和0变成Integer.max_value就不需要考虑它了。
非常常见的做法：考虑num和idx的对应关系 128. Longest Consecutive Sequence
求在此数组中，能连成sequence的最长长度。在这个数组中，是无序的，并且要求是O（n）的时间，所以不能用double for loop，那么能记录这个数组中都有什么数唯一的方法就是用HashSet来存储。接下来，针对每一个数，分别有左bound和右bound，如果也在set中存在，就继续左--， 右++。另外可以优化的方法是：在每一次找过left 和right后，set来remove该数字，避免之后重复计算 159. Longest Substring with At Most Two Distinct Characters 340. Longest Substring with At Most K Distinct Characters
两道题一摸一样的，除了code中k改成2, sliding window类型题目的一种，O（n）
特别的是这道题的window constrain是看有多少种不同的characters，那么这个的记录只能用map,key是char，value是how many count of that char in the window. 套路：在iterate整个string的for loop中，一开始就要update map, 然后考虑如果window size(即 map.size()) 大于k时该怎么办，将leftmost左端点右移，update map，查看如果map.get（c）== 0时->remove map中的c 76 Minimum window Substring
也是一道window题目，求满足target string最短的window长度。用int array 来hash target string。Iterate right指针。
【LinkedList】 Odd Even Linked List
易错点：
while loop的termination情况，到底是(head != null) 还是(head.next != null)不可以想当然
一般有 slow 和 fast两个指针的时候，while的条件是根据fast来定的ex： while(fast!= null && fast.next != null)
楼主: ootsuka
狗仔卡
楼主
