缺大米的请参加这个刷题/Mock interview活动

Day 13:
3 AC

6.21 打卡四题

LC 1231. Divide Chocolate， binary search: 在解空间中binary search，找到最后一个（最大的）valid solution。 第一反应是用DP解，会超时
LC 694. Number of Distinct Islands，BFS/DFS + encode islands，可以用相对位置（相对于左上角）来编码每个island
LC 1167. Minimum Cost to Connect Sticks，greedy + heap，使用heap快速得到最短的stick
LC 174. Dungeon Game， DP

21天 3题

慕容清 发表于 2020/06/19 11:02:38
打卡十二天

112. path sum： 就是找一条从leaf到root的完全路径，使得节点值之和等于给定sum。思路...

打卡13天
235. lowest common ancestor of a binary search tree. 由于bst良好的性质，可以采用recursive的方式进行，如果判断给出的两个节点p和q的值，都要小于root.val或者是都大于root.val，那么就可以直接到左子树或者右子树上面去接着找。当这两种条件都不满足的时候，就说明p和q已经不再同一个子树上了。可能一个节点就是ancestor节点，或者这俩者，一个小于ancester节点，一个大于ancestor节点。那么这个ancestor节点就是我们要找的lowest common ancestor。如果用iterative，可以用while (root != null) 作为限制条件，也可以用是不是满足可以分到左子树或者是右子树跑，自己一开始是用后面的方式写的，有点感觉不保险，可能出现子树为空的情况，而且判断条件很多，跑的慢。

236. Lowest common ancestor of a binary tree. 和上面的题目的区别就是现在的节点已经不是排好序的了，即不满足bst的性质。给出两种做法，一个是recursive的方式，这个方法感觉很难自己想出来。
它是利用一个递归函数，然后去判断p和q是不是存在于左/右子树。base case是说如果我这个节点是给定的其中一个节点，那么就直接return该节点，否则的话，就需要进一步的进行遍历，判断左右节点是不是符合条件，如果遇到的节点一直都不是我们需要的节点，那么最终那个节点必然会遍历到leaf节点，然后返回null。左右节点有一个为空，就返回另一个；如果左右节点都非空，说明已经找到了那个节点，直接就返回那个root节点。也就是从上往下遍历，直到找到目标节点，之后再从下往上进行判断是不是有公共节点。很tricky的一个点是，这个算法最后如果没有公共节点，比如{1，2，3，4，5}4，5是想要的节点, 最后判断到2这个节点的时候，其实也没有找2和3的公共节点，而是直接判断左右节点是否为空，一个为空就返回另一个。感觉自己想不到啊。
Solution里面也有iterative的方法，这个比较简单粗暴，就是直接开一个字典，把每一个节点的父节点存为value，本身存为key。之后再开一个set存储p之前的所有的父节点，然后去判断q的父节点什么时候能够和set相遇，返回那个节点。

230. Kth smallest element in a bst；由于是bst，所以可以利用bst的性质，直接进行dfs inorder遍历，可以存储到一个arraylist里面，用指标返回那个值，或者是直接在dfs函数里面每次遍历k- -, 当k == 0 时，直接返回当前root.val。

最近一直都在刷leetcode sql and python, 刚看到这个活动，赞！正愁大米不够帖子都看不到。。。多谢群主发起的这个活动。打卡第一天

打卡第21天

Day 7 (6/21)

leetcode 刷题6道
sorting

又开始加米了, 上周没打卡, 那补一下上周刷的题吧, 15题

第三天，三题：
nary tree level order traversal
sum of left leaves
range sum query - immutable

打卡第20天， 刷了3道题

130. Surrounded Regions
用DFS， 从边界的O开始。以后再看union find的解法

133. Clone Graph
用hashtable and DFS (or BFS)

204. Count Primes
暴力解法O(n^1.5), Sieve of Eratosthenes O(NlogNlogN)