8月刷题/Mock interview接龙活动（缺米刷题的来）

楼主参加了7月份刷题活动（原帖https://www.1point3acres.com/bbs/thread-648249-1-1.html），感觉大家既可以监督刷题也可以得到大米，但是现在已经8月份了，还可以相对应的帖子，所以楼主打算开一个8月份的刷题活动，楼主也会每天都进行刷题，希望大家互相监督学习～

规则和帖子（https://www.1point3acres.com/bbs/thread-648249-1-1.html）一样，参与者每个人除了自己打卡截图以外给前面3位小伙伴加米，这样形成一个良性循环。因为如果只有一个人来给大家加米的话，实在忙不过来。

从今天开始，每个小伙伴完成一次mock interview, 截图发到这个帖子，并且给前面的3位小伙伴加大米，自己也可以获得3米。
加米规则：
- 根据mock interview的数量和质量(欢迎分享感想)，加1-2米
- 每天刷够三题截图发帖有1米, 附上note或者题目多, 加2米
- 坚持5天, 加3米，坚持10天，加6米
楼主每天也会来看一次这个贴子，给小伙伴加米。希望大家相互监督，不要偷懒！记得给前面小伙伴加米。这样的话每位认真学习的小伙伴起码每天能拿3米！一个月就可以加90米！

昨天忘了传照片打卡。

8月第一天，刷leetcode

DFS 复习了一下
Combination Sum       
Combination Sum        II
Factor Combinations       

8.1打卡, leetcode 面试题08.08，632，304，783

day1 三道dp

8.1 打卡
三道graph的题，都可以用Union Find求解
LC 399 Evaluate Division
LC 839 Similar String Groups
LC 952 Largest Component Size by Common Facto

01/08/2020 打卡 Linked List

比较简单的三道题。

328. Odd Even Linked List

创建两个子链：奇链和偶链。逐一遍历所有的节点，用一个mark位来标志当前节点是奇还是偶，将节点接到奇链或偶链上。

92: Reverse Linked List II
Reverse Linked List 的延伸题。
取出需要反转的这一小段链表，反转完后再插入到原先的链表中

237        Delete Node in a Linked List
先把当前节点的值用下一个节点的值覆盖，然后我们删除下一个节点即可

Day 40, solved 1 problem.

Tip: DFS + Memo.

好棒啊，支持一下

我也要加入

8月打卡第一天，这个月要拿若干个OA和至少一个店面！加油！

3道题：
1. LCAV: (给一个Knary Tree，找2个Nodes的LCA，2个nodes都确定一定在树里面）
和LCAI其实没有本质的不同都是recursion
关键是把每个Knary的child都找一遍
然后使用到一个KnaryNode的variable

2.LCAVI（给一个Knary Tree，找m个Nodes的LCA，2个nodes都确定一定在树里面）
有了之前的基础，需要用set来装m个Nodes
其他没有啥变化，就是base case 那里是
if (root == null || set.contains(root)) {
return root;
}

3.Switch a Binary Tree into A LinkedList
照例上recursion
然后用一个Node[] pre = new Node[1];
先确定尾，并update pre
然后再不断去更新root

8月也要继续努力，加油！

打卡 Backtracking 7道

39 Combination Sum
backtracking, 我的做法是建立一个public variable ans, helper function 是每次target递减，当target==0的时候，把temp_ans,加入ans里。
https://leetcode.com/problems/co ... -questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partitioning)
discussion里非常详细的讲解了各种情况的backtracking
40 Combination Sum II
Each number in candidates may only be used once in the combination.
combination(candidates,target-candidates[i],new_ans,i+1)
不是
combination(candidates,target-candidates[i],new_ans,start+1)

78 Subsets
90 Subsets II
subset的基础上without duplicates
在for(int i=index;i<nums.length;i++)
的多了一个
           if(i>index && nums[i]==nums[i-1]) continue;

1. 要记得sort, 不然nums[i]==nums[i-1]没什么用
2. 要记得是 i>index,不是i>0。i>0的话就没有任何duplicates了，eg [1,2,2]->[1,2]

46 Permutations
我最开始是用temp_ans (temp_list) add num， 然后remove, 结果出来全是空的[[],[],[],[]]。两个办法解决，一个是在add num的时候先把temp_ans复制到new_ans, add num to new_ans, 然后helper function call new_ans. 还有一个办法就是每次temp_ans add to ans的时候，用ans.add(new ArrayList<>(temp_ans));而不是直接temp_ans (一个Pointer)
47 Permutations II
参考Subset II

131 Palindrome Partitioning

感觉遇到这种return List<List<Integer>> 就想到跟backtracking有关，共同点1：需要枚举，共同点2：直到partition完，或者像之前combinationSum 的target==0, 是无法直到这条支路行不行得通的。最后直到符合条件的时候，再把现有答案加入最后的return
dp solution
The normal dfs backtracking will need to check each substring for palindrome, but a dp array can be used to record the possible break for palindrome before we start recursion.