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

7月打卡第9天 3道题
1.4 sum follow up（要求打印所有的combination 要求无重复）
a. 将两个元素作为一个pairSum来考虑，并作为Key储存在hashMap中
b. 加法交换律：任何可以组成4sum的4个元素，一定满足array[i] + array[i + 3] + array[i + 1] + array[i + 2] == array[i] + array[i + 1] + array[i + 2] + array[i + 3]
c. 两层循环扫描确保所有能够组成pairSum的index pair是最小的
d. Class pair:
最后的combination结果用Pair包起来，Override hashCode是直接return 0的 -> could be better

2. course schedule I
-topo sort combining with BFS
-use a hashMap to record the mapping relationship
-firstly initialize the hashMap then update the inDegree array
-use InDegree with BFS

3. course schedule II
-based on course schedule I
-use a (map)HashMap <Integer, List<Integer>> to store the chain of finished courses order
-the terminal condition is either the queue is empty or the length of map.get(course).size() == numberCourses

7.25 contest, 第四题没有写出来。

1. Number of Good Leaf Nodes Pairs. DFS处理。
2. Bulb Switcher IV. 从左到右 Greedy.
3. Shuffle String. Index mapping，easy 题。

0725 Day20 打卡7题

Number of Good Leaf Nodes Pairs， recursion，在每个node记录以此node为根的leaf以及其深度，以深度为index统计leaf个数
Bulb Switcher IV，greedy，从左到右，遇到需要换的就换，并记录现在的状态
Shuffle String，one-pass，按定义
Minimum Number of Increments on Subarrays to Form a Target Array，monotonic stack，遇到比栈顶大的元素入栈，遇到小的出栈，并把差加入到结果
Number of Sub-arrays With Odd Sum，dp，以index为状态，dp[i]为以i为结尾的和为odd的subarray数量，i-dp[i]为以i为结尾的和为even的subarray数量
Number of Good Ways to Split a String        ，two-pass，从前向后，从后向前count各个字符的个数
Count Odd Numbers in an Interval Range，Math，算差求模，注意edge cases

day 21mock是lc 283 四个月前做的，已经忘记最优解了。。。就很tricky，看了答案会觉得简单，自己没法come up出来， 多复习8
lc周赛还是三道题小妹

刷题打卡第15天
36. Valid Sudoku 一个比较清晰的思路是先查每一行是不是都正确，然后查每一列是否都正确最后查每一个3*3block是否正确。更巧妙的做法是，将每个格子分别按照行列3*3block进行编码，然后直接加入到hashset里面去，这样只需要遍历一遍即可。
6.ZigZag Conversion 这是一道medium题，关键是想明白采用哪种算法，一种是类似仿真，同步build每一行的string,另外一种是直接计算出每一行的string.然后要处理第一行和最后一行的corner case. 另外我个人漏了考虑输入长度为1的特殊情况。

8. String to Integer (atoi) 这是一道medium题，想明白按照顺序处理string,先把空格都处理掉，然后正负号，然后找到第一个数值和最后一个数值，然后转换，转换的时候检查有没有越界。

菜鸡七月第二十六天

1. continuous subarray sum: 可以用map来存sum和index，sum是cumulative sum mod k之后的值，如果之前map里有同样的
    mod值，就说明中间的subarray是k的multiples，没有就把当前pair放进map里，注意只有k不等于0的时候才能mod
2. string compression: 用两个index pointer，把快的index每次移到重复字母的尽头，同时记重复的count，然后移慢的index存
    当前的char，如果count不是一的话转成char array之后的数字，一直到快的index走完整个array
3. summary ranges：和前一道题有点像，也是先记当前char，再用i向前走到array不再continuous，如果和当前char不一样，就
    加上->把头尾存到list里，如果i没往前走的话就光存当前的char
4. subarray sum equals k：复习一下之前写的，也是用map存cumulative sum和number of ways，如果存在两个cumulative sums
    的差是k的话，就说明有符合条件的subarray，result加map.get(sum-k), 然后再把当前pair放进去
5. mirror reflection: 看了答案感觉还是不是很懂，先求p，q的gcd，然后mod 2来找适合的ratio，然后根据p，q的值来算最后的corner

07 - 25 - 2020

169. Majority Element
本题是easy题，hashMap可秒。
但是Boyer- Moore Voting 算法是个新知识点，值得研究。
算法原理：
每次从数组中找出一对不同的元素，将它们从数组中删除，直到遍历完整个数组。由于这道题已经说明一定存在一个出现次数超过一半的元素，所以遍历完数组后数组中一定会存在至少一个元素。
- 算法在局部变量中定义一个序列元素(m)和一个计数器(i)，初始化的情况下计数器为0；
- 算法依次扫描序列中的元素，当处理元素x的时候，如果计数器为0，那么将x赋值给m，然后将计数器(i)设置为1；
- 如果计数器不为0，那么将序列元素m和x比较，如果相等，那么计数器加1，如果不等，那么计数器减1。
- 处理之后，最后存储的序列元素(m)，就是这个序列中最多的元素。
（如果不确定是否存储的元素m是最多的元素，还可以进行第二遍扫描判断是否为最多的元素）

285. Inorder Successor in BST
Iteration和Recursion做法都可解。

384. Shuffle an Array
Fisher–Yates shuffle 算法：
1. 建立一个数组大小为 n 的数组 arr，分别存放 1 到 n 的数值；
2. 生成一个从 0 到 n - 1 的随机数 x；
3. 输出 arr 下标为 x 的数值，即为第一个随机数；
4. 将 arr 的尾元素和下标为 x 的元素互换；
5. 同2，生成一个从 0 到 n - 2 的随机数 x；
6. 输出 arr 下标为 x 的数值，为第二个随机数；
7. 将 arr 的倒数第二个元素和下标为 x 的元素互换。

Monotone increasing digits : greedy 算法， if(nums[i] < nums[i-1] ) nums[i-1]—记录从index = i-1， 从index +1 之后起变成9， corer case 个位数 1234， 本身符合条件，index+ 1， 直接out of bound, 不该任何数，否组，1234， 变成1239
Contruct k Palindrome String : 题目要求必须用完所有字母，因此odd num 字母决定了时候能有k 个palindrome, 只要 odd num <= k 就行
Find Min in Rotated Sorted Arraya II， 存在duplicate num， 333 123， 与 end 比时mid == end 情况, end = end -1, 可以缩小范围，摈并且不会错过结果。mid  > end, start = mid +1, 取中位数是左中位数， 如果start = mid， 会出现死循环。因此必须start= mid + 1. mid < end , end = mid， 不出现死循环，因为是左中位数两个数时会落到左边。
Task Scheduler: greedy 算法， （ 最大频率数字 max – 1）* n = idle , 其他数字降低idle 次数，其他数字最多降低 max -1, 最后返回length + idle, if(idle < 0, idle = 0)
Course Schedule iii 求最多可以上几节课。 先用finish time 排序，找finish time 最先的为最优， 如果time > finish time, 需要减少目前的1节课， 减少哪节课 ？  目前队列中duration最长时间的，为最佳，这样可以腾出更多时间。增加course 数量。因此使用PQ 按照duration 比较。
is Subsequence : two pointer 完成， slow 指针traverse s string, fast traverse t string.

day5 contest 差一题 加上2道BS

刷题+contest
biweekly contest都不难
weekly contest除了hard都做出来了
求米