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

打卡 17 天

刷题第7天打卡 6道题=4道two pointers 2道dp
167 Two Sum II - Input array is sorted
- left, right → sum
15 3Sum
1. sort, for the first number ⇒ inside: two pointers
2. without sort but use additional space to remember seen elements
16 3Sum Closest
- sort, for the first, two pointers
977 Squares of a Sorted Array
- find the zero position
- two pointers to left and to right→merge sort
279 Perfect Squares
1. dynamic programming: count[n] = min(count[n], count[n-sqrt)+1)
2. bfs: for each value in the last level, minus one sqrt to get the next level
647 Palindromic Substrings
1. expand palindrome in each position
2. Manacher's algorithm

day 9 6题
1. 排名--自关联-count(distinct ..)

打卡第9天，240. Search a 2D Matrix II; 287. Find the Duplicate Number; 4. Median of Two Sorted Arrays。无法上传附件，截图放在云盘了。https://drive.google.com/file/d/1dLTZi4Ir2SlkQEtyMGQz3rILAjWpCjrX/view?usp=sharing

Jun 18 第18天 6道新题
275. H-Index II, 二分法，注意[0,1,4,5,6]的情况，low最终stuck在4的位置，也就是有3个数满足，n-low；
465. Optimal Account Balancing, 先利用map计算出所有人的balance，然后backtracking，只有乘积<0才会有offset操作，res=Math.min(res, 1+helper(list, start+1)); 带有返回值的recursive;
985. Check Completeness of a Binary Tree, 可以利用2*i, 2*i+1特性；lee的解法不管是否为null，先加入队列，出队列遇到第一个null，最后判断队列是否empty，因为如果不满足completeness的话，queue里面必然会有一个不是null的node；
1339. Maximum Product of Splitted Binary Tree, 可以用set存放所有可能的subtreeSum；也可以用直接递归，注意点product方法递归的返回值是sum。
979. Distribute Coins in Binary Tree, 每个root只需要管将自己的children balanced，最终root的被返回值是v-1+balance(left)+balance(right); balance可能是负数，看看最终有多少coin跑来；返回值和答案的关系要理解。
542. 01 Matrix, 将非0先设置为MAX，然后将所有0加入队列BFS，每次更新可以被设置的grid；

6/19 连续打卡第六天

刷题8道

总结：
1. BFS做几道题会就行，大多有一题相关。
2. 理解基础上记忆类型模版。
3. 多动脑思考，质更重。

慕容清 发表于 2020/06/17 11:12:03
打卡第11天

- 105：二叉树的重构：用了hashmap，存储的是inorder的内容。然后采用了迭代的方式，最后的...

打卡十二天

112. path sum： 就是找一条从leaf到root的完全路径，使得节点值之和等于给定sum。思路就是recursion，要注意的是左右节点是或的关系，返回值也是只要其中一个满足条件即可。然后base case就是本身是leaf，然后值和给定值相等。还要注意如果本身root是null的时候，直接返回false。
113. Path sum II: 不仅要判断是不是有，还需要给出所有的值，以list的形式返回。采用recursion，也就是回溯的方式。感觉自己想回溯的方法还是很难想明白。还有使用了path 返回的时候需要copy一个新的linkedlist(path) 否则的话path一直在变化。
437. Path sum III: 所有的节点都可以作为开始节点，然后计算可能的path数。注意的一点是不能将pathsum（left，sum - root.val） + pathsum(right, sum - root.val) + pathsum(left, sum) + pathsum(right, sum) 放在一起进行recursive，这样子节点就会重复次数相加。所以这两部分要分开来进行考虑。
103. Binary Tree Zigzag Level Order Traversal。这题和剑指上面那题类似，但是不太一样的是，是分层进行打印，每一层都是一个arraylist。然后整体成为一个list。同样也可以用queue的方式进行存储。解法非常巧妙的就是可以直接将每行都存进queue，然后利用size（），将每行的poll出来，恰好就是那一行的长度，然后用一个新的temp list去存储每一行。还有就是判断条件的写法for(int i = 0; i &lt; queue.size(); i ++)的方法是不对的，因为循环里面在一直改变size；可以改为for（int i = queue.size(); i &gt; 0 ; i—）或者是用一个变量先把size存储下来，之后直接用size。

Day 4 (6/18)

leetcode 刷题10道

bit manipulations & math

gongchangzhANYK 发表于 2020-6-18 14:56
2020年6月17日，第十六天发帖，今天刷了7道题：

403. Frog Jump。这是一个DP，state定义为某一个石块所 ...

坚持了这么多天!!鼓励一下!!坚持!!

Day 11:
6 AC