加州 妹子一枚 监督自己每天⛽️刷题！！欢迎大家评论分享心得！！

五月份毕业的新生，希望能在年底中找到心仪的工作。目前Leetcode做题情况是235题，最近刷题十分懈怠，知道刷的题目太少，并且很多新题拿到思路不足，所以感觉是因为自己之前刷题总结不足造成的，只是在记得解题思路，如果题目有变形，code就可能就不是bug free。在此开帖，监督自己每天的做题数量和分享每题自己的感悟。十分希望有小伙伴加入一起刷题，大家可以交流分享心得，并且互相督促！！怀挺！

leetcode 上边有个explore,里面有常见题型，大概155道，建议那些反复做，总计模板套路，我最近也要开始重新做了，现在一上班回家发现根本啥也不想干，今天一做新题特别费劲，感觉这样下去就荒废武功了，欢迎楼主来互相交流，可以留个联系方式:cxu264@usc.edu

【9/22 Sat】Tree-base DFS
Binary Tree Problems:
考点本质：DFS
        • 第一类：求值，求路径类二叉树的问题
        • 第二类：结构变化类二叉树问题
        • 第三类：BST 问题

【第一类：求值，求路径类二叉树的问题】
Tree的题目离不了的是recursion下面的三道题目就是一种类型，利用recursive helper function分别recursion出left subtree和right subtree 的结果，再合并不断update result
124 binary tree maximum path sum the path must contain at least one node
687 longest univalue path find the length of the longest path where each node in the path has the same value
543 diameter of binary tree compute the longest length of the diameter of the tree
分析：需要求整棵树上最大/最长的path或者sum， 一定是需要走完整棵树才知道结果，那么需要一个recursive的helper function来不断向下面走。同时需要一个global variable来不断update记录所遇到过的最大的答案
做法：在主函数中callhelper function即可，在helper fucntion中
        • 首先要有return case which you need to return 0 at this moment.
        • 然后用int left  = helper(root.left); int right = helper(root.right) 来分别记录当前left subtree 和right subtree 的答案 (devide 步骤)
                ○ 有时在做选择的时候，如max path sum需要subtree sum为正数，相加才最大，那么
                ○ int left = Math.max(0,helper(root.left)) 表示subtree可选可不选
        • 再update global variable 如：longest = Math.max(longest, left + right + root.val)是情况而定
        • 最后return helper function的值，记住是半边tree的subresult
                ○ 如 return Math.max(left, right) + root.val;

Subtree with maximum average(lintcode597)是124题目的拓展
这道题有点棘手，因为在不断dfs的recursion中既要知道当前subtree最大的sum又要知道subtree节点的个数。解决的方法就是：新建一个ResultType  class，其中包括sum和count这两个preperty。那么dfs每次返回的是resultType的obect instead of just int variable。这个时候就需要有两个global variable，一个是最后返回的subtree node和当前最优秀的resultType object。在dfs中比较当前subtree的sum average并即使update。
**另外一个小策略：当想比较 a/b > c/d时不妨表示成： a * d > c * b 避免了整出后的取整问题
226. Invert Binary Tree
Example:
Input:
     4
   /   \
  2     7
/ \   / \
1   3 6   9
Output:
     4
   /   \
  7     2
/ \   / \
9   6 3   1

public void invertBinaryTree(TreeNode root) {
         if (root == null) { return; }
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        invertBinaryTree(root.left);
        invertBinaryTree(root.right);
        }

124 binary tree maximum path sum && minimum subtree 题目看似相似但其实不同
124: 只要找到 maximum的path就好，所以每次面临的是两个选择：左tree or 右tree，所以每次dfs返回的值也是左tree或右tree较大的那个 + root.val

Minimum subtree
每次就是为了得到subtree的值：left + right + root.val


257 Binary Tree Paths: 返回所有root to leaf 的paths
DFS 每次查看左节点和右节点是否同时为null，不是的话，就分别用dfscall下一个左节点 or 右节点

【第二类：二叉树结构/形态发生变化】
114. Flatten Binary Tree to Linked List
【第三类：BST】
• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.
【题目】
230. Kth Smallest Element in a BST
Follow up: 当BST经常被修改，怎么优化Kth smallest 这个操作？
在 TreeNode 中增加一个 counter，代表整个树的节点个数也可以用一个 HashMap<TreeNode, Integer> 来存储某个节点为代表的子树的节点个数在增删查改的过程中记录不断更新受影响节点的 counter
85. Insert Node in a Binary Search Tree
Given a binary search tree and a new tree node, insert the node into the tree. Return the node of the new BST.
public TreeNode insertNode(TreeNode root, TreeNode node) {
if (root == null) { return node; }
if (root.val > node.val) { root.left = insertNode(root.left, node); }
else { root.right = insertNode(root.right, node); } return root; }


补充内容 (2018-9-24 01:41):
将DFS分为三类复习：Tree-based dfs, combination based dfs, graph&permutation based dfs. 今天复习后两类。

9/15 Sat
新题
127. Word Ladder (Medium)
凡是求最短路径or距离的题目一般都是用BFS进行层级遍历。那么一定会用到Queue。同时这道题需要自己build graph，用set来当dict存下给的wordList。最短距离一定是不能用重复，那么重点就是每用到一个单词，就需要从dict中remove掉。非常经典的BFS题目，需掌握。
273 Integer to English Words (Hard)
看似很难，但不要怕，肯分析。需要清楚一共要讨论哪几个数量级 Hundred, Thousand, Million, Billion. 在合成result时利用recursive call来降低数量级。重点：20以内的英文表述无规律，所以要单独存在一个array中为了以后可以用。
76. Minimum Window Substring (Hard)
用两个ptrs来模拟窗口的移动。进入while loop，首先需要移动右指针， 直到match == t.length() 即找到了第一个符合的substring，接着就在这个substring中移动left ptr，缩小窗口的长度，不符合后则跳出while loop。并用startIdx和minLen来存立冬过程中找到最小的窗口长度。值得注意的是：最后return时要查minLen是否被update过，不然则表明这道题并没有满足条件的窗口。
341. Flatten Nested List Iterator
不难，这道题考查的是阅读题目的问题
124. Binary Tree Maximum Path Sum(the same as 543, 687)
遇到tree的这种问题，要想到用recursive的方法。三种题的做法都是：用一个global variable来存目前为止最大的result 再用一个 recursive helper funtion。并且用divide & conquer的方法，先分别得到left subtree 和right subtree的subresult，再进行合并，并return想要的解。注意的是，helper function每次return的是subtree的result，并不是这道题需要的最终解
547. Friend Circles
和200 number of islands 一摸一样的DFS做法！！时间复杂度O(n^2) 题意唯一的区别是此题的dfs helper funtion中是遍历所有的人看是否互相认识；200题的dfs是遍历四个临界方向看是否为岛。

旧题重做
297. Serialize and Deserialize Binary Tree
Serialize: 用StringBuilder 来帮助，用一个recursive helper function，不断对sb append treeNode val
Deserialize: 先将String拆分存成string array，再全部放入queue中，传入helper function，在helper function 中不断取出进行操作
2. Add Two Numbers
值得记住的是：这一类创建新的linkedList并返回的题目，首先要创建dummyNode来作文起点，并且创建一个ListNode ptr = dummy作为串连前后节点的一个指针，非常好用。
3. Longest Substring Without Repeating Characters
这类题目一定要想到用HashMap来存访问过的char和其index的对应关系，然后用左右两个指针来扫string，若之前访问过当先的char，那么右移left pointer缩窄窗口，update maxLen。大致思想和今天做的76window substring就很像！总结：求满足条件window substring的问题都是需要hashMap + two ptrs来完成
11. Container With Most Water && 42. Trapping Rain Water 一类题
柱形图的trapping water问题都是利用左右两指针来扫一遍的。根据trapping water的不同方式中间做法不一样。稍难的题目：需要用leftmost和rightmost来存扫过地方最高的height。
200. Number of Islands
DFS-> O(mn) m = grid.length, n = grid[0].length

今日收获🌺
        • 求最短路径/距离， 用BFS进行层级遍历
        • 求返回最小的xxx，一般用DP或贪心算法
        • Window substring问题，用hashmap + 2ptrs
        • Trapping water 用2ptrs， 具体问题具体分析，需要额外variables
        • Difference btw "continue" && "return"
                ○ The continue statement stops the current execution of the iteration and proceeds to the next iteration.
                ○ The return statement takes you out of the method. It stops executing the method.

9/14 Fri
4. Median of Two Sorted Arrays hard
题目要求O(log (m+n)) 那么次题一定是用binary search来做。首先要分清中位数是由nums1和nums2的哪个元素构成，将长度和分奇偶讨论。Binary search是用来算出nums1中需要取多少个元素。
遇到hard题不要怕，将问题解读清楚，自己多举例，找规律。将大问题分介绍小问题
7 Reverse Integer easy
不难，但想提醒自己的是，将一个integer做转换后数字有可能 overflow. 解决的方法，用double来存reverse后的结果，最后return时再cast回int。
42 Trapping Rain Water hard
Two pointers 问题，left， right指针扫一遍。O（n）的时间复杂度。特别的点在于，需要另外leftmost和rightmost变量来存扫过的数中最大的值。
681 Next Closest Time Medium
用DFS, 将原时间的数字所能组成的时间结果都iterate一遍，把valid的时间存在一个list中，将list进行排序，得到离input time最近的一个时间。值得注意的地方：先把valid time存到set中的原因：set可以帮助去重！！！聪明的方法

如果可以分类刷题的记录就更好了。

旧题重做和新题的顺序基本上都是按照利口frequency来做的。并没有按照topic来刷，因为想要综合地练习并且锻炼自己拿到题自己分析归类到一个topic的能力～

9/16 Sun
新题
560 subarray sum Equals K
Brute force 2for loops 算 sum[i, j] 是否等于K O(N^2) 需要优化
运用 HashMap 来用preSum 的解法 sum[i, j] = sum[0, j] - sum[0,  i- 1]。和2Sum也十分相似的做法 if (preSum.containsKey(sum - k)) {
                result += preSum.get(sum - k);

295. Find Median from Data Stream O（logn） (Hard)
非常特别的解法，用两个max heap 和 minHeap 来分别存储两端values。maxHeap stores the smaller half of the values; minHeap stores the larger half of the values. Add() in PriorityQueue cost O(logn) poll() in pq costs O(1)
和4. Median of Two Sorted Arrays 的binary search完全不一样。因为input array已经是给好的，不需要自己添加， 在给定的情况下只能是binary search。并且在此题中要求get Median 的时间是O（1）

394. Decode String (Medium) 非常值得做的题目 String + Stack
利用两个stack分别存digit和stringBuilder，在iterate loop中，针对digit, '[',']' ,char 四种情况分别讨论。
339. Nested List Weight Sum
DFS 题目，nestedList这个data structure list 中套list，只能选择用dfs来不断深入

旧题重做
289 Game of Life
简单的Array题目，计算每个点周围lives的情况，再改变当前的value。特别之处：不能边读边改变当前的value，否则改变后在算其他地方的时候会受影响。解决方法：bitwise operation。Board[i][j] = 3 = 11   Board[i][j] = 2 = 10 前一位表示next generation，后一位表示当前位置。当 board[i][j] & 1运算时比较的是当前的value是否为1，前一位的更新并不会影响当前值。
78 Subsets 典型Backtracking，必须要掌握
80 Subsets(with duplicate)
为了skip duplicate只要在进入for loop的时候加一句话
if(i > currIdx && nums[i] == nums[i-1]) continue;   

今日收获🌺
        • Java Priority Queue is implemented using Heap Data Structures and Heap has O(log(n)) time complexity to insert and delete element.
                ○ To insert: add()/offer()
                ○ To delete: remove()/poll()
                ○ Peek(): O(1)
                ○ Contains(): O(n)
        • Max Head: 从大到小，意为：每次poll出来的都是最大的
        • Min Head: 从小到大，意为：每次poll出来的都是最小的
Backtracking：解法特点，在主函数中直接call helper function， 在helper function中需要有tempList来存当前的sub result， 当前的idx来记录iterate到第几个位置。进入helper（）首先加上一个level的result，再for loop从idx开始iterate，勿忘离开for loop之前要移除tempList中最后一个元素

给lz点个赞

楼主是今年5月毕业的还是明年5月毕业？感觉每天时间好充裕。我也刷了200冒尖了。但是秋天的课业workload很重。感觉完全没精力刷题了

naihe1990 发表于 2018-9-17 15:34
楼主是今年5月毕业的还是明年5月毕业？感觉每天时间好充裕。我也刷了200冒尖了。但是秋天的课业workload很 ...

今年五月