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

2020-6-18

打卡第19天，刷了6道题

打卡 day 17

打卡第17天， 刷了3道题

5. Longest Palindromic Substring
left = i//2, right = (i+1)//2 for i in range(2*len(s)-1)
if s[left] == s[right]: left -= 1 right += 1

64. Minimum Path Sum
Dynamic programming, paths[i,j]=min(paths[i-1,j]+paths[i,j-1])+grid[i,j]

70. Climbing Stairs
Dynamic programming, ways[n]=ways[n-1]+ways[n-2]

Day 17,刷三道新题：

Valid Palindrome        LC 125
H-Index II        LC 275
H-Index        LC 274

1. 验证回文很简单，只需要注意每次要判断i < j

2. H-Index II, h-index表示有h篇paper的citations >= h，同时满足其他N-h篇citations <= h。这个题降序排序好想一点，if citations[i] >= i，说明有i篇paper满足要求，就找最大的citations[i] >= i即可。但这个题升序排序的，其实也差不多，就转化成找第一个mid满足citations[mid] >= n - i

3. H-Index。题目给定非排序，有两种做法。既可以降序排序，遍历一遍找到最大的i满足citations[i] >= i，也可以用计数排序。计数排序把引用量作为bucket，h from 0 to n,引用量高于n的不会影响到h-inedx。因此bucket数量可以减少到n。计算出>=K引用的篇数 Sk，找到最大K满足K <= Sk就是答案。

看了一眼公司tag，google的题，怪不得这么绕...

6/18/20

305. Number of Islands II
Union find，用了两个dictionary分别记录position到island index和island index到position list到mapping

42. Trapping Rain Water
Monotonic stack，对每个index找左边最大和右边最大高度，O(n) time, O(n) extra space

146. LRU cache
用Linked list记录顺序，Hash map from key to prev node快速查询

今天的六题

6.18 打卡 6道双指针题目

坚持15天，刷了3题，笔记：
1.Note the j/=10, not j++ or j-- everytime.， for (j=i; j>0; j/=10)； As long as the loop breaks, no matter when, we will not add this number i to the list. Only if the loop doesn't break anywhere, will we make it till only one digit, and this time j//10 will be 0, and the loop terminates itself, and because this time j==0, we can be sure this number satisfy everything we need (because if didn't not break anywhere), so we add it to the result
2. Use LinkedList to implement Queue. Queue<Integer> queue = new Queue();
3. As long as the loop breaks, no matter when, we will not add this number i to the list. Only if the loop doesn't break anywhere, will we make it till only one digit, and this time j//10 will be 0, and the loop terminates itself, and because this time j==0, we can be sure this number satisfy everything we need (because if didn't not break anywhere), so we add it to the result

Day12:
211. Add and Search Word - Data structure design: Trie应用
50. Pow(x, n)：二分递归
636. Exclusive Time of Functions：stack

day 2
在用多种解法做tree
1. Binary Tree Preorder Traversal: 有把所有node都放入stack里面和只放右儿子的方法. 还没有看morris
2. Diameter of Binaary Tree: recursion比较好做, iterative要用到map
3. Symmetric Tree: 同样的recursion是对左右儿子分别进行判断; iterative用queue或者stack都行,
4. Convert Sorted list to binary search tree: 在find mid的时候可以直接把前一段的linklist分开, 这样的话就不要pre和end了
5. Linkedlist cycle II: 怎么样找到环的开口. 不刷不知道.
6. LinkedList cycle I: 复习了一下快慢指正. convert sorted list to binary search tree里面用到