以梦为马，重整出发——记录刷题 自我打气贴

[9.28]
复习了下各种merge two/k array/linkedlist/bst:

88. Merge Sorted Array
- 把n长度的b merge 到m长度的a里。根据index从后向前填入数值，直到b被填完。
21. Merge two sorted list.
-注意设置dummy节点，以及pre节点，返回dummy.next
23. Merge k sorted lists
-同上题,只不过使用priorityqueue返回当前k个里的最小值
56. Merge Intervals
- 给interval类复写一个comparator函数，从小到大排序，然后遍历有overlap的就合并
1. Two sum
- hashtable
167. Two Sum II - input array is sorted
- two pointers
170. Two sum III - Data structure design
- map记录每个数字出现的个数（以防i + i的情况），list记录出现过的数字（比遍历map快）
653. Two sum IV - input is a BST
- hashset 记录出现的数字，dfs/bfs 遍历查找
617. Merge Two Binary Trees
- recursion. 如果iterative的话，用stack
2. Add two numbers
- linkedlist 记录carry，注意遍历完l1,l2,需要判断carry
445. Add Two Numbers II
- iterative: 两个stack；recursion- 先求出两个list的长度，然后传入两个节点间差的距离offset，求出当前两个节点的和，在递归求他们next的和，connect他们，
231. Power of two
- iterative或者利用n & n-1 == 0，因为power of two only has one bit of 1 in binary.
15. 3 sum
- 排序，然后遍历每一项，剩余部分找2sum(避免当前项和前一项重复，会有重复解）
18. 4 sum
- 同上，两层遍历，然后2 sum. 可以考虑两层里剪枝

10月更新：

[10.1]
703. Kth Largest Element in a Stream

priorityqueue. min-heap control k of biggest element in pq.

215. Kth Largest Element in an Array

QuickSelect. Partition, compare the separate point pivot with k, and continue partition if needed.
partition use the last element as pivot and then traverse from the left and right index. left = lo - 1, right = nums.length - 1; first ++/--, then compare it with pivot, do exchange if needed. until the index left >= right, break, do final exchange of i and right.
[10.2]
218. Skyline Problem

sweepline-> list of int[], saving the index and the height with positive/negative, so that to know at each index, the height is started or ended. sorted it with index, if the indexes are same, sort the start first, then the end.
Using PriorityQueue to save the max value of all heights of current index. Traverse all the index, if it is a start point, add it in pq, if a end point, [remove] (!!not poll) it from pq. Then get the current max value in pq, check if it is different from prev one, then add the int[] to res.
Note, put 0 first to pq. otherwise when all buildings are done, no value in pq represents the 0 height.

[10.3]
220. Contains Duplicates III

TreeSet is a balanced binary search tree. BST is easier to find the smallest number larger than certain number, and found the largest number of the numbers smaller than certain number. -> treeset.ceiling(), treeset.floor()

[10.6]
4. Median of Two Sorted Arrays

中位数的特点：两边元素个数相同，所以确定了一个数组的切分位置，可以通过(m+n+1)/2求出另一个数组的切分位置。然后对小数组二分，比较两个数组在切分位置的大小，如果刚好左边的最大小于右边的最小，则找到了切分点，如果不是，就移动第一个数组的切分点，移动的前提，是i - 1和i+1是有效范围，即i>iMin,i < iMax.

323. Number of Connected Components in an Undirected Graph

Union-find. At first every node is a set, once combine two sets, the total set size will minus 1. And in the find function, we can do path compression, which will reduce the rank of each visited node closer to current node's root.[Note: just after computing the root of i,
set the id of each examined node to root(i).]

To be more efficient on Union-find, should consider union by rank（height), or union by size. Rank[] is initiated as empty, then if there is a union, then the father's rank will + 1.

[10.7]

918. Maximum Sum Circular Subarray

So there are two case：
The first is that the subarray take only a middle part, and we know how to find the max subarray sum.
The second is that the subarray take a part of head array and a part of tail array.
We can transfer this case to the first one.
The maximum result equals to the total sum minus the minimum subarray sum.

One** corner case** to pay attention:
If all number are negative,
return the maximum one,
(which equals to the max subarray sum)

622. Design Circular Queue

环状数组，标记头坐标，和尾坐标，以及计数长度

84. Largest Rectangle in Histogram

Stack，先压入栈-1，作为最左的边界
用stack记录截止到目前的i,前面有哪些数可能比heights[i]高，每遇到一个高于heights[i]的bar, 就可以得到当前的area=barHeight * (i - bar.prev.index - 1)
最后遍历完所有的元素，如果栈里top不是-1，那么继续弹出当前值，当前i相当于heights的长度

179. Larger Number

int->string, 然后实现comparator类。不能只比较最高位，要比较两个数谁该靠前，需要把两个数合并，然后比谁大，即string倒序排列。
corner case: 如果最大的数都是0，那么说明是一串0，直接飞回0即可。

[10.8]

252. Meeting Rooms

sort: Arrays.sort(arr, (a, b) -> a.start - b.start);

160. Intersection of Two Linked Lists

同时两个指针从List A，B遍历，遍历完再分别交换遍历，直到两指针相遇。如果最后相遇的点是空，那么说明不存在intersection。
之所以work，是因为在交叉点前，如果A比B多了k个节点，那么下一轮B会提前k步来遍历A，然后A再来遍历B时，两个节点距离交叉点的距离就相等了。

836. Rectangle Overlap

If the rectangles do not overlap, then rec1 must either be higher, lower, to the left, or to the right of rec2.
we can check position of two recs by comparing the point position, eliminate the false situation.

[10.9]
305. Number of Islands II
Union-find. When a new position is added as an island, regard itself as an root pointing to itself, count++. then traverse its four neighbors, if any legal island neighbor has a different root from this new island, then mark new island's root to be neighbor's root, count--. let current id be the current root, then comparing other neighbors. if the second neighbor's root equals to current it, then do nothing, otherwise similarly update the common root, and id.

783. Minimum Distance Between BST Nodes

dfs:
inorder recursion, for each node, the smallest difference between it and its previous one is root.val - prev.val. Inorder traverse, mark each node to prev, after it is traversed. base case for the smallest node, its prev should be null.

919. Complete Binary Tree Insert

BFS, 把所有有两个子树的节点入栈，直到遍历到有incomplete的节点停止；insert时，读取队头元素，如果它左子树为空，添加到它的左，如果右子树为空，添加到右，更新queue：当前头元素出队，然后左右子树压入。

[10.11]

694. Number of Distinct Islands

DFS找每一个岛，判断岛的形状是否相同，可以使用记录每个点开始走过的方向，存入全局list,然后set存list以去重。存每个方向的时候，对于每个点的四个方向便利完，要加入0作为separator，不然无法分清是基于谁的方向。

距离上次更新已经一个月了，但中间还是有坚持做题的，虽然速度不算快。也试水面了几家，有startup上来JavaScript前端的，有OA或者电面都做出来因为其他原因被挂的，也有5轮下来自我感觉良好被拒遗憾收场的。

总体感觉是坚持刷题确实会有进步，但是自己也确实还有软肋。语言沟通可以更自信更娴熟，简历描述应该更有针对性凸显自己目标岗位的能力，做题时的细节应该尽量第一遍就处理好不要等人提醒，最后系统设计还是要厚积薄发的，另外自己脑子里有的东西虽然没有问到也可以引导面试官分析，大胆说出来，不能太被动。

转眼又是一年年底了，陆续刷题一年了，继续加油吧

翻出打卡贴，一看都是去年11月份的记录了，尴尬。。。中间有继续刷题，年底的时候复习了一些高频题目。12月初也面了狗家，挂之，刷题和系统设计都有待提高。最近又要开始面试了，所以继续刷题打卡，希望一切顺利。

rara2008 发表于 2019-4-8 05:19
翻出打卡贴，一看都是去年11月份的记录了，尴尬。。。中间有继续刷题，年底的时候复习了一些高频题目。12月 ...

祝楼主好运！

18，19年记录的陈年老贴了。今儿又翻出来了，因为不想干了，想辞。但title可以不要，水平不能太差，还是得持续学习。所以又回来了。这次咱们先从系统设计开始。作为小白从零开始一点点记录吧。加油！