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

打卡第八天 6题

打卡第十六天：

102， 107， 872， 814， 669

1.  拿到BST优先思考递归方法。
2.  归纳了JAVA主要Interface中的常用methods。 add, remove, element: throws exception. offer, poll, peek: return special values.
3.  BFS迭代和DFS递归的解法各写一遍。

在职党第三天打卡（非连续，昨天没刷3题）

目前为止刷了12题，其中部分题是lc的mock，不知道算不算mock interview

第四天，三道题：
path sum 2
path sum 3
majority element

path sum 3用的是recursion within recursion因为它需要any path，不仅仅是root to leaf像path sum 2. 写一个recursive helper，然后solution函数本身recursive visit的每一个node就call这个recursive helper。majority element用heap 和hashmap搞定

Day 24，刷三道题，一道新题：

Contains Duplicate II        LC 219

1. 长度最小子数组，sliding windows，还是比较staight forward。注意最后判断下ans != sys.maxsize，以防找不到的情况，要return 0

2. perfect square，和coin change一毛一样，就是前面计算以下有多少可用的平方数，再dp即可。

3. 包含重复数2。hash和set都可以做，但set的空间复杂度貌似优一些，是O(min(k, n))，时刻保持最多只有K个数。

Day 5, solved 6 problmes.

tips:
1. When dealing with the Semaphores in multithreading problems, pay attentions on the exit conditions of all threadings: one thread exits could result another blocked forever. e.g.: LC 1195;
2. For factorization problems, it is possible to find a solution better than time O(n): e.g., LC 1492;
3. Number theory could be very helpful in dealing with integer square sum problems: e.g., LC 279.

day3
继续做top100 liked
lc 338,581,234

周末仍然十道题，终于把前五十写完了。
数组/字符串注意：判断到结尾再取值

06.26 刷题第十五天 打卡第15天 （刷题6道）

已经叫不动楼主大大帮我加米了，55555555.... 觉得总结还有点参考价值的话，看官别忘加个米呗！

1.QuickSort
Mindset: 挡板法，两个挡板 三个区域
搞懂每个pointer的物理意义和base case（size<=1)都可以做为base case
注意在swap pivotIndex的时候要和最右边swap
swap回头要和left swap
为什么？
因为left pointer 对应的永远是>pivot当中的第一个数，和left swap一定能够满足pivot左边都是和他一样或者比他小的；

2.Rainbow sort
不同之处在用用到了3个挡板；
i, j, k;
搞懂物理意义其他都迎刃而解；

3.Selection sort
基本的N^2做法
不费空间，纯练手感

4.Merge Sort
和Quick有一些不同的是
1. 不保证原有数字的相对顺序；
2. 需要用到额外的空间 去存一次helper array
3. base case 必须是size == 1； 如果是size 为0，那就没得搞了，就stack over flow了
4. 再复制array 到helper array 里面去的时候，注意要掌握好头尾的节奏，不是[0-array.length - 1]而是[left - right]；

5. Repeated subString
Mindset:
至少可能要重复1次，也就是最大substring是 size / 2;
然后再造新的substring 一个个地去验证；然后看最后结果；

6. Binary Watch 2刷
物理意义物理意义物理意义；
分两种情况，第一个是hour 另一个是min
//base case
if(num == 0) {
//handle the length of the min
//add to result;
}

do it recursively until hitting the final level
//main logic
//aspect one: index < 4;
//aspect two : the other one;

慕容清 发表于 2020-06-25 20:29:09
补卡打卡16天

79.word search: 还是用的dfs+回溯的方式进行。还是要注意回溯操作完之后需要复原已经visited 的值，如果可以一条路走到黑，这条路上的值可以依次逐个恢复，如果这个

打卡17天
昨天只做了两题今天的和昨天一起

263.ugly number: 注意当本身num已经是0的时候会进入无限循环，所以得把0这种情况删掉。
264.ugly number ii: 找到第n大的丑数。注意到丑数的性质，所有的丑数，其实都需要通过之前的丑数*2，*3，*5得到，从丑数1开始，实际上我们可以利用三组数字，对于所有的丑数进行*2，*3，*5操作得到三组数；那么所有的丑数实际上是这三组数字的去重排序（也就是merge k sorted list）。对于多组数进行排序的问题的解决方法，一般都可以采用指针的方式，每组数都有指针，找到最小数存储在目标数组里，然后对应数组指针加一，如果有多个数组指针对应数值都是那个最小值，则同时加一。还有就是min函数只能处理两个input。
3.longest substring without repeating characters: method2: sliding window: 使用一个set去存储已经访问过的字符。同样需要使用两个指针m和j指向string里面sliding window，一首一尾的位置。首先用指针j进行遍历，如果指针j指向的字符没有出现在set里，那么就填入set中，如果已经出现了这个字符，则m需要移到最近的位置，使得以该位置为起点的字符串，不含重复的那个字符。也就是跑到该字符首次出现的下一位，但注意不是新元素的下一位。需要进行m++，直到m到达那一位。每次循环都需要记录新的字符串长度。可以采用hashmap直接存储两个指针对应元素和位置，直接通过改变位置省掉m++循环。
一个点是指针m的取法是Math.max(map.get(s.charAt(j)), m)就是m一直是在往前走的，不走回头路，否则出现abba这种情况，如果不取max，当再次遇到a的时候，其实是m的值又回到了0。