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

day 15 打卡

刷题打卡第21天

39. Combination Sum 一开始想的挺复杂的，例如拿每一个数遍历其倍数直到超过target，后来发现这个用递归backtrack的方法来实现就好，几个核心细节要注意，第一个是list每次append temp的时候要拷贝不能引用，第二个要对candidates进行排序，然后通过递归中的start position来防止重复，第三是start index可以重新使用本次迭代值，以允许重复。

40. Combination Sum II 和Combination Sum I类似，关键是backtrack算法里如何避免重复，需要使用i>start位置外加连续两个候选数字不相同即可。

37. Sudoku Solver 刷了一道hard题，基本思路是通过递归back track来解决问题，然后关键是思考递归函数怎么写，如果返回值是T/F，要想明白何时返回T何时返回F,如果使用循环要避免遇到真值就直接过去知道False，这样递归返回的就是错误结果。更加优化的方法是使用Priority Queue来策划每次开始的位置，但是要记得定期更新Priority Queue。

今天五题。另外重刷了一些二分搜索和二叉树的题。
我开了一个新的session，所以截了两个屏。
另外分享一些binary search的总结，欢迎拍砖。
Binary Search Methodology
When you can see from the problem, to approaching the target value, everytime you can get rid of half candidates and remain another half of candidates for continuing calculation.
Binary search can also apply to approaching a value in a range, not necessary finding value in an array.
The third usage of binary search is to find an insert position in a sorted array. Then perform a linear algorithm to generate the result sorted which is related to distance.

7月份的最后一天，刷了3题：
Binary Tree Longest Consecutive Sequence II
Boundary of Binary Tree
Climbing Stairs

最后一天7月
IP to CIDR：bit
Largest Unique Number
Rotting Oranges：bfs
Partition List and Sort an Array:复习quicksort

时差党 7月打卡最后一天，1237， 350， 392， 475， 367， 1337

7/31 打卡第31天， 刷了3道题

52. N-Queens II
backtracking, 方法同51题

303. Range Sum Query - Immutable
用一数组存累计加和

344. Reverse String
双指针，左右互换

哎呀妈呀，哭哭唧唧的也没做几道题。光在复习数据结构了。
继续哭唧唧去了

day 15打卡：抓住了7月的尾巴，就抓住了整个夏天。趁着美西时间还是7月，来打这个月最后一次卡。下个月继续加油！

求加米，必回加。一起加油！

菜鸡八月第一天

八月再搞一搞攒够米就该复习了，不然做了的全忘了（叹气
1. climbing stairs: 比较简单的一道dp，每次新的爬楼梯的数量是i-1和i的和，如果n小于等于3可以直接return3
2. spiral matrix: 每次用四个坐标表示当前layer，然后最上面的行从左到右加，右面的从上到下，最下的从右到左，
    最后从下到上，每次动一个坐标，最后把四个都向内移
3. spiral matrix II: 和上一道差不多，只不过记一个num，可以用while loop直到num<=n*n, 和上次一样移四条边，
    每次num+1，同时把layer向里缩
4. kth smallest element in sorted array: 学习了一下binary search做法，其实还是不太会做，lo和hi先从两个对角开始，
    然后再每一行算小于mid的element的个数，同时如果mid不在matrix里面还要找到在matrix里的值，如果count
    等于k，就直接return找到的值，count小于k就把lo往上移，大于k就移hi
5. basic calculator II: 用stack，先把arithmetic symbol initialize成+，然后如果当前char是int就加到当前num里，如果
    当前char是运算符号的话，加号把num存进stack，减号存-num，乘号pop一个出来和当前相乘，除号也pop再相除，
    把对应的结果放进stack之后再把当前num清零，最后把stack里的都加起来