7月缺米的来刷题/Mock interview活动

7.20
1520. Maximum Number of Non-Overlapping Substrings
周赛题目，用greedy，评级是medium但是绝对有hard难度了，卡了好久。
复习Union Find：Number Of Island II，Graph Valid Tree

打卡第十三天
3sum经典题 重新做一遍练练手
3sum两种方法 用指针+sort/用hashmap

Recursion 4 题

7月打卡第四天
刷题六道

1.Print Layer by Layer
-用好Queue
-最简单的BFS

2.Zig-zag print
-用好Deque，双端队列
-按照题目意思来进行根据层数奇偶行来的划分
-决定在这一层poll和offer的顺序
-无论如何poll和offer不再同一边

3.Check if it is complete tree
-use a flag to detect if it is true already
-if true and meet other element under just return false
-until traversing all elements then return true;

4.Bipartite(如何去确定它的颜色？在HashMap里面设置）
-关键是用好Map这个数据结构
-<K,V>里面的V是Integer，标记一下颜色就好

5.TopKinUnsortedArray
-两种方法：minHeap / maxHeap
-1.minHeap N + klogN;
-2.maxHeap k + klogk

6.KthSmallestSortedMatrix
High level:
this is BFS2 question which the value of each upcoming element is not identical
so a general queue is not enough, so a priorityQueue(A.K.K minHeap) can be used to solve this problem.

Details:
Firstly, do the corner case check, the matrix can't be null or empty,
also, k must be valid(k >= 1 && k <= matrix.length * matrix[0].length)
Use a MinHeap with a hashMap which contains traversed coordinate positions so to avoid deduplication
Set up a new class Cell so the row, the col and the value of each element can be recorded in it;

Secondly,
Initialization: use the original point parameters(row, col, val) to create a new Cell;
and put it into the minHeap, also, checked new Cell has been visited;

Thirdly,
Then in the while loop,
which the terminal condition is k <= 1
during each single process, get the current element and check if the two neighbors of current one can be
added into the minHeap or not;
update the minHeap and the visited hashMap;
update k(k--);

Finally,
After jump out the loop, we already poll out K - 1 element, so just return the top one at the min Heap and return it;

马一个 今天晚上刷

07/20 倒数第十天 三题打卡

不同二叉树 利用二叉树性质 每次改变位置 求出当前位置前作为左子树 后作为右子树 递归实现
二叉树垂序遍历 利用层层遍历变形 增加横坐标 并最终排序插入
扑克牌中的顺子 排序 检查第一个非零和最大亚元素距离是否是4  需要特别处理0

0720 Day17 打卡四题

Compare Version Numbers，split+parse，使用String与Integer的API，按规则比较即可
Add Bold Tag in String，brute force，注意这里使用hashset反而慢会超时，原因是字典里单词的个数小于input字符串长度
Simplify Path，stack，遇到.跳过，遇到..出栈，遇到其他字串入栈
Remove Linked List Elements

继昨天palindrome题，再做3题palindrome相关的题。
感觉如果题目是要partition成substring的，可以考虑用dp，存substring的状态，然后找递归公式。

332. https://leetcode.com/problems/reconstruct-itinerary/
dfs 不常规的dfs。思路，细节。


143. https://leetcode.com/problems/reorder-list/
list. 细节。对输入的判定，算法在大于两个element的时候才成立

958. https://leetcode.com/problems/ch ... s-of-a-binary-tree/
少数recursion不如iteration的解法的。

刷题打卡第10天：
23. Merge k Sorted Lists 这是一道hard题，一开始的实现想法是对k个链表中找出最小的然后插入到输出链表中去，这样的计算复杂度O(kn),之后发现可以用priority queue来维持k个链表中最小值，这样就能把复杂度提升至O(nlogk)
24. Swap Nodes in Pairs 设定三个指针，然后按照规则交换即可。
25. Reverse Nodes in k-Group 这是一道hard题，将任务分解成两部分，先将链表每k个节点分成一组，然后对每组内的元素进行反向换向即可。