fresh grad 刷题+补习知识打卡贴

**一枚，2月开始找工作还未上岸，看样子opt开始之前上不了岸啦。决定在这里立个flag每天刷题打卡（希望别打脸）。目前情况断断续续差不多刷了350道，总次数800不到，但到现在很多题目拿出来真的还是两眼一黑。第一遍的时候完全是看discussion top vote抄的。其实自己也没少做总结，整理了一本实体的笔记本了，每个题目也有写comment，也有在旁边写note相关的知识点之类的。有些题目再遇到真的还是觉得自己想不到。。。不过看自己的note pick up起来会快一点。

本帖以后会更新自己的每日刷题和简短笔记，希望能在下半年上岸！如果有同学觉得和我水平差不多欢迎私信一起线上刷题讨论监督，西雅图的同学也欢迎线下交流。

如果有同学想支持我的话可以给我加大米就行了，不必回复我。希望帖子里面只有刷题笔记和问题讨论。

6/3 Sun
547. Friend Circles, Union Find, DFS (similar to 323)
684. Redundant Connection, Union Find
union the two vertices of an edge if they are not in the same group. otherwise return the edge
685. Redundant Connection II, Union Find
737. Sentence Similarity II, Union Find
use HashMap to do union and find; val: key's parent
261. Graph Valid Tree, Union Find
tree must be connected and acyclic

Union Find TEMPLATE
public boolean validTree(int n, int[][] edges) {
        int[] parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        for (int[] e : edges) {
            int x = find(parent, e[0]);
            int y = find(parent, e[1]);
            if (x != y) {
                parent[x] = y;
                n--;
            } else return false; // cycle
        }
        return n == 1; // connected
    }
   
    public int find(int[] parent, int i) {
        while (parent[i] != i) {
            parent[i] = parent[parent[i]];
            i = parent[i];
        }
        return i;
    }
一般可以用array来做，偶尔用到HashMap

844. Backspace String Compare, Stack
845. Longest Mountain in Array
846. Hand of Straights, TreeMap

5/10 Thur
明天有个面试，随便做了点题目。另外来不及做的题型只能过一过不写了。
80. Remove Duplicates from Sorted Array II
392. Is Subsequence, two pointer
115. Distinct Subsequences, DP consider delete or not delete the current char of s
20. Valid Parentheses, stack
22. Generate Parentheses, backtracking
和其他backtracking题目思维不太一样。首先肯定先加左括号，只要左括号数量小于n可以继续加。等到不能加了看右括号是否小于左括号数量，小于的话可以加。
241. Different Ways to Add Parentheses, divide + conquer
use recursion: each left and right sublist contains results from left and right subexpressions.
32. Longest Valid Parentheses, stack
没用dp做，看了一个用stack做的高票答案TLE，然后稍微改了一下就可以了。
1. 遇到'('就push
2. 1)遇到不合法')'(stack为空、stack最上面也是))还是继续push
        2) 遇到合法的')'就会pop，然后计算更新res
不合法的括号还是会留在stack里，在每次计算最大值的时候，就会用现在的index减去stack里最上面的（它后面的都是合法的）。如果stack为空则用index减去-1，因为从头到现在的index都是合法的。
48. Rotate Image, get transpose than reverse each row horizontally
311. Sparse Matrix Multiplication
C[i][j] += A[i][k] * B[k][j]; only calculate the values if A[i][k] and B[k][j] != 0
329. Longest Increasing Path in a Matrix, DFS + memorization
378. Kth Smallest Element in a Sorted Matrix
1) use PriorityQueue, treat each col "like a linkedlist" and first row is the head of each linkedlist。新建一个class Tuple有x,y,val
2) binary search,还没写
74. Search a 2D Matrix, binary search (convert 1D index into 2D indices)

6/4 Mon
616. Add Bold Tag in String, similar to Merge Interval
56. Merge Intervals
817. Linked List Components, Linked List

6/5 Tue
484. Find Permutation
778. Swim in Rising Water, Min Heap
max: max time at cur position
everytime change unvisited neighbor cell's (x, y) time into max(grid[x][y], max)
and put them into pq

6/6 Wed
39. Similar String Groups, Union Find
455. Assign Cookies, Arrays sort + two pointer, greedy
122. Best Time to Buy and Sell Stock II, just cumulate the profits
763. Partition Labels

Interval
452. Minimum Number of Arrows to Burst Balloons, Arrays sort, greedy; sort by start time
435. Non-overlapping Intervals, Arrays sort, greedy; sort by end time
if we choose the interval that ends earlier, then there is more space for other intervals
253. Meeting Rooms II, Arrays sort and use PriorityQueue
先画图，模拟增加房间。正常思维会从开始时间短的开始加。每次遇到新的interval，都会考虑end最早的。如果可以合并则合并。如果不可以则新加房间。如果最早end的都不行，其他都不用考虑了。所以先按照start time sort，min pq是按end time

6/7 Thur
134. Gas Station
If the total number of gas is bigger than the total number of cost. There must be a solution.
738. Monotone Increasing Digits 自己想不到。。。
674. Longest Continuous Increasing Subsequence
747. Largest Number At Least Twice of Others, one pass, find largest and secLargest
624. Maximum Distance in Arrays
605. Can Place Flowers, Greedy
581. Shortest Unsorted Continuous Subarray, sort solution, O(n) time 还没做
562. Longest Line of Consecutive One in Matrix, DP
note need to differentiate the dp value from different directions

5/11 今天面了四个小时，不刷题了 居然真的有人问Integer to English Word, 之前还被问过Integer to Roman。。今天还遇到matrix找规律的题目，好不熟。。。看来真的啥类型的都要刷。

5/12 Sat
今天没咋学习 做的都是stack
155. Min Stack, push: hide old min under new min; pop: pop twice if the top is min and update min
225. Implement Stack using Queues
用一个Queue就行，push根据queue和stack FIFO, LIFO的特性改变一下排列就行。其他method和queue的method一样。
232. Implement Queue using Stacks, use two stacks

这三题一模一样
496. Next Greater Element I
stack and HashMap; keep popping if the stack top is smaller than current num and put them into stack and then push current num
503. Next Greater Element II
stack storing indices; loop over the array two times; same idea of push and pop; note index can be larger than array length n now, so use index/n and only push if index < n
739. Daily Temperatures, stack storing indices

150. Evaluate Reverse Polish Notation
push number token into stack; pop and calculate when seeing an operator and then push the result into stack
71. Simplify Path


补充内容 (2018-5-16 08:45):
496,503,739 monotonic decreasing stack

5/13 Sun
relax的一天。。。明天一定要学习了。。。
394. Decode String
StringBuilder for building cur String
Stack<Integer> for storing count
Stack<StringBuilder> for storing previously formed Strings

5/14 Mon
347. Top K Frequent Elements
bucket sort, each bucket contains the elements of frequency of the index of the bucket
215. Kth Largest Element in an Array, PriorityQueue
227. Basic Calculator II, Stack
224. Basic Calculator, Stack
42. Trapping Rain Water
1) O(n) time and space
当前坑的积水量是由两边矮的边决定
用left和right两个array来记录每个位置从左和从右起最大的高度。
最后每个坑的积水量等于 Math.min(left[i], right[i]) - height[i] if min > height[i]。把每个坑的积水量加起来
2) two pointer left and right, and record leftHighest and rightHighest
407. Trapping Rain Water II
Put every cell on the border into queue
While queue is not empty:
...Poll the cell with minimum height （start from lowest cell because water will leak from here）
...For every cell adjacent to this cell:
......Compute the gap of two cell only when the new one is lower
......Add this new cell into queue and make the height as taller of two.

5/15 Tue
772. Basic Calculator III
https://www.geeksforgeeks.org/expression-evaluation/
basically use two stack: one for operators and parentheses and another for operands
need helper function to calculate and another to indicate precedence
331. Verify Preorder Serialization of a Binary Tree, Stack; brilliant
replace each "number##" pattern with # and there should only one # left in the stack at the end

Greedy
316. Remove Duplicate Letters; Monotonic Stack, greedy
e.g. bcabc, when see a, pop out c and b since b and c occur later again
402. Remove K Digits; Stack, greedy
while the current digit is less than previous digit, discard the previous one
738. Monotone Increasing Digits, greedy
traverse from right to left and use a flag to indicate all digits after that index will be 9
Google tag easy
832. Flipping an Image
812. Largest Triangle Area
760. Find Anagram Mappings
766. Toeplitz Matrix, very easy and sneaky
830. Positions of Large Groups
783. Minimum Distance Between BST Nodes, inorder traversal
643. Maximum Average Subarray I

5/16 Wed

665. Non-decreasing Array, greedy
When you find nums[i-1] > nums[i] for some i, you will prefer to change nums[i-1]'s value, since a larger nums[i] will give you more risks that you get inversion errors after position i. But, if you also find nums[i-2] > nums[i], then you have to change nums[i]'s value instead, or else you need to change both of nums[i-2]'s and nums[i-1]'s values.

Range Based Query
729. My Calendar I, TreeMap
key: start, val: end; compare the neighboring intervals with the current interval
731. My Calendar II, use two ArrayList: intervals and overlaps
key: Math.max(interval[0], start) < Math.min(interval[1], end) means this is an overlap!!!!!!
732. My Calendar III, TreeMap
key: start and end time, val: +1 for start, -1 for end
need to find the max number of ongoing intervals

同刷题，一起加油希望能一起上岸

楼主的帖子不错诶～

补充内容 (2018-5-18 09:53):
= =抱歉回复了。。
希望LZ早日上岸！