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

Day 10， 3个题

Cheapest Flights Within K Stops比较容易想的是bfs解法，也花了时间去理解Dijkstra（利用了heap）和dp（每一步去更新到达每个city的cost）的解法，bst问recursive和iterative两种解法，都很简单

补昨天～ day15

lc new 5 review 10+
41. 448. 442都有Index as a hash key的思想

打卡第13天
几天复习了tree question,树的问题都用recursive和iterative两种写法写一下
觉得delete in binary search tree这个题目很好， 同时可以复习find the smallest element in Binary search tree 和 BST 的性质
       • Reverse a binary tree upside down
        • Delete In Binary Search Tree
       • Insert In Binary Search Tree

20200614:
3: 0053, 0056, 0152, 0253, 0763
4: 0787
5:

20200613:
3: 1481
4: 0329
5:

06.14.2020 刷题第三天 打卡第三天

1. Sort with two stacks

Given an array, which is initially stored in one stack, sort it with one additional stack (total 2 stacks).
After sorting the original stack should contain the sorted integers and from top to bottom the integers are sorted in ascending order.

Mindset：
Basically it is the kind of selection sort, just use three int variables:
preMax, curMax, count(handle the duplicates) to solve it

2. A to the power of B
Mindset:
Watch out the corner case and not overlooked the odd number of B;

3. Get target in unknown size sorted array
Mindset:
Watch out for the difference between classical binary Search, don't forget to check the rightHand side (equals to null) condition.

4. Use two queues to perform a stack
Mindset:
Offer: just offers into the first queue
Pop: Handle the size limit to 1, then pop it out; do it repeatedly(O(N^2));
Top: Check the size of queue1 and peek it!

also, I can use another way to solve this problem:
generally speaking, that's pretty same, but they use a temp queue as the bridge to swap two queues
Deque<Integer> temp = q1;
  q1 = q2;
  q2 = temp;
  return prev;
Also, it utilized prev and cur two variables to determine the final one element in the first queue and return the prev one.

5.Deque By three stacks
Mindset:
In order to achieve the best time complexity, utilize the buffer as a bridge to contact two stacks, and always check the half size of the stack.

6. Remove repeated element in a sorted array
Mindset:
use three variables: slow/fast/begin(handle the fast and begin in a while loop)
use fast - begin == 1 to detect if duplicated available

在本回复之前，还有3个回复需要加米
本次是第5天打卡，今日3题如图
第一题#787. Cheapest Flights Within K Stops，思路是在dijkstra最短路径算法上稍作变化，在求最短路时，还需记录步数，用到优先队列，需要将代价小的路线入队，也要将步数较少的入队，因为万一代价小的那种路线超过步数被淘汰。BTW，java优先队列是用小顶堆实现的。
第二题#700. Search in a Binary Search Tree，考察遍历二叉树，使用递归式的先序遍历，进入递归函数时，先确定在root为null或者其值是要找的值时，返回root，否则先看左子树，若左子树得来结果node1非空，则直接返回node1即可，不用再看右子树，不然就直接返回右子树就行了，没必要必须左右都求解，这样就避免了冗余。
第三题#1003. Check If Word Is Valid After Substitutions，这题乍一看有难度，其实和匹配有效括号是一个道理，每次匹配到'c'就让stack进行pop，只要stack此时是空，或者没有先pop出b再pop出a，那么就return false。

day6 打卡五题

Day 9
0615 三道题

Minimum path sum: 预处理top left第一排，然后填表，挺简单
Serialize deserialize BST， recursion做deserialize的时候，用一个范围判断是不是走到最后了，因为范围越走越小
kth largest又写了一遍，今天就不算了
group anagrams用 Arrays.sort()的所有字母做key，很巧
Knight probability in chessboard 看了一下思路没写完，明天搞把

连续第 10 天打卡，完成 6 道 BST, Graph 题：(5.5/6)
1. Search in a Binary Search Tree
2. Insert into a Binary Search Tree
3. Delete Node in a BST
4. Construct Binary Search Tree from Preorder Traversal
5. Validate Binary Search Tree
6. Cheapest Flights Within K Stops

Tips 总结：
1. 熟悉掌握 binary search tree 的 search, insert, delete 三个基本操作，其中 delete 要分为 3 种情况进行分类处理；
2. 熟悉 binary search tree 与其各种 traversal 之间的对映关系；
3. 熟悉 graph 的 level order traversal 和 dijkstra's algorithm，前者用 queue 后者用 priority queue，其实熟练后也没那么难。。。目前就是 graph 题做少了罢了。

今天晚上刷完忘了来更新。。
6.14 14天 3题