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

7/1 刷题网 3题朋友圈
排硬币
最大二叉树2

7.3 day2

连续第四天打卡

今天在pramp上mock一题sudoku 写得超级卡所以再刷一遍练熟度

今天做了House Robber II, House Robber III, Koko eating bananas，其中koko bananas是应用的二分查找，这个还需要再多思考。

今天 做了 双指针类型 三题  Lintcode + Leetcode July Challenge

intersection-of-two-arrays
题目有三种解法，1. 最好想的算法是用二个set来做，有点类似于hash Join的思想，把小一点的数组存入hash Set中，遍历长一点的数组，看当前元素在不在 hashSet 里面，如果在丢进result set 里面
2. 第二种是 把二个array 都sort了，然后用二个指针分别代表二个数组的当前index，因为二个数组都是sorted, 只有当二个index 指向的数字相同时，才代表他们是intersection,反正根据二个index指向的数字 的大小来分别增加 二个index
Minimum Size Subarray Sum
标准的 sliding window 模板，二个指针 left/right。 for 循环right 指针， 如果满足条件 -》 就去看当前的sliding window里面是不是存在更小的subarray，--》 如何实现： 移动左指针，直到当前条件不满足。
Matching Subsequences
这道题比较不好想，实际上用了 binary search的思想去查找subsequence
首先建造一个 hashTable <char,vector<int>>ht. key是 每一个 char ， value是 他在string 中出现的位置 (这个一定是sorted 顺序-》可以 binary search）
然后再看每一个词语，寻找词语中每一个char在 string中的位置，用 之前建的hashtable 来找对应的 index array，对着 index array 做 binary search（stl upper_bound ---> > current_element)
比较值是当前你所在的index，如果存在这样的index，就继续前进~直到遍历完所有字符，如果所有字符都符合条件，加入result。

LeetCode 挑战 监狱那道题，没啥说的。。找规律，没做过不是很好想
957. Prison Cells After N Days

20200703:
3: 1109, 1139, 1247
4: 0221, 0688, 0916, 1152
5:

菜鸡七月第四天

今天还是挑了几道简单的做（叹气
1. find peak element: 这个是看如果array里面有multiple peaks，找到其中一个峰值，可以用binary search做，每次看如果
    nums[mid] > nums[mid+1]，就说明当前subsequence是递减，有可能是local maximum，可以把high移过去，不然的话
    就移low，这样总会找到一个peak
2. peak index in a mountain array: 这个虽然只有一个mountain，但和前一道题是一样的lol
3. maximum average salary：这个可以用sliding window，如果知道length是k的话可以求subarray的maximum sum，先算
    第一个window的sum，然后每次移的时候update maxsum，maxsum一开始要initialize成第一个sum，最后除以k就是average
4. search a 2D array: 这个可以把matrix看成一整个sorted array, 还是用binary search，转换成matrix要注意col = mid/colNum,
    row = mid/rowNum
5. jump game: 学习了一下greedy，存一个可达到的最大值，通过比较当前index+nums[index]来update max，如果max小于index
    就return false

竟然今天才发现这个活动 赶紧补上
07/03 三题打卡

最长有效括号用栈模拟字符串生成 将所有不能匹配的括号的位置全置1 变成寻找最长连续的0的长度
删除排序链表中的重复元素使用一个临时指针来访问 然后最后返回指针头部
数字转换为十六进制数 获取num的低4位 然后移位处理

0703 Day3 打卡三题

Time Needed to Inform All Employees， Backtracking/DFS/BFS，遍历整个树，累计边的权重。Top-down：在叶子节点记录最长的通知时间。Bottom-up：将时间累加到root，可以省去建图的时间，更快（复杂度仍为O（n））
String Transforms Into Another String，考察Insight，需要意识到可以通过字符的变换关系建图，图中没有cycle或是cycle可以被打破时输出True。同时需要意识到这可以通过统计str2中的unseen character来判断
Prison Cells After N Days，意识到当N大的时候一定会出现循环，通过找循环开始的位置以及循环长度可以快速得到结果。

7.3 今天刷了三道题，状态有点差