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

继续刷了8个题 - -感觉30左右的题都比较蛋疼，很多overflow的问题，很难处理，办法就是不处理- -...遇到了就自认倒霉考

新入组刷题成员报道。

今日刷题：
349 intersection of two arrays
350 intersection of two arrays ii

这两题本质是一道题，349 建立一个dictionary, 然后查找第二个array的元素是否在dictionary中，然后防止重复返回使用了set
350 分别对应两个array建了两个dictionary, 分别存了元素出现的次数，然后当两个dictionary元素出现重复时，使用最小的次数。

1 two sum  这个就不用说了，重做一次这题是因为在复习hash table

347 top k frequent elments  
先建一个dict 存 element 出现的次数
再建一个dict 存 次数 对应的 elements
然后从list 的长度n 往 1 推 次数存不存在，按次数逆序排序建一个array，最后返回前k个elments。

974 subarray sums divisible by k
这道题考虑的方式是 sum( list[0:a])%k == sum(list[0:b])%k, 那么 sum(list[a:b])//k == 0

3. longest substring without repeating characters
这道题就是要用dict来存字母出现的index, 然后用sliding window

726 number of atoms
这题可以用recursion. 我使用的是hash table和stack的方式。遍历formula从最右开始，然后用一个coeff来存括号带来的倍数，一个cnt存当前的数字，stack 用来更新coeff， dict 存元素出现的次数。

学习贪心算法，刷了135 Candy, 435 Non overlapping intervals, 605 Plant flower

截图

今天练了一些 backtracking题

求大米！拜托了各位！！！

打卡第一天 2020.07.05
1010. 总持续时间可被 60 整除的歌曲 https://leetcode-cn.com/problems ... ns-divisible-by-60/
605. 种花问题 https://leetcode-cn.com/problems/can-place-flowers/

解题思路：
1010 题，一开始想着两层遍历，复杂度在 O(N^2) 了；后面用额外的一个数组seconds来记录余数的个数，并且单独处理余数大小为 0 和 30 的情况，这两种情况下可以看作是简单的组合数了（在k个数中任找2个数进行组合），个数为 k*(k-1)/2；剩下的情况就是前后一起遍历数组 seconds[i++]*seconds[j--] 直到 i>=j时。

605 题，这道题可以用贪心算法解决，从前往后遍历，遇到0之后，判断前后是否都是0，如果是，那么这个位置上就可以种花了，计数器相应的增加；不过要单独考虑一下首尾两个位置的情况，只要一边是0就可以满足要求。

7月5日，第二天发帖。今天刷了3题。

1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit。brute force算法给我们的时间复杂度是O(N^3)，根据题目给的数量级暗示这个显然不够理想。于是想到了可以用一个自排序的数据结构，同时不能去重且能同时得到最大值和最小值，于是想到了TreeMap，时间复杂度O(NlogN)。最优解使用了两个双向队列，一个单调递增一个单调递减，这样就不用像treemap一样花额外的时间复杂度去维护最大最小值了。
239. Sliding Window Maximum。受上一题启发，遍历数组的同时维护一个单调递减的双向队列即可。
391. Perfect Rectangle。这个题本来是想拿来复习扫描线算法的。于是参考了一下之前使用扫描线的用例，发现如果这道题用扫描线算法的话基本上相当于一个一个数格子，时空间复杂度会非常高。看答案后了解了一种新的算法：1.小长方形面积之和必然等于大长方形 2. 小长方形在大长方形内部及边上的相同位置上的顶点的个数必然是偶数。

总结：
1. 维护一个双向队列可以代替堆来实现动态寻找在一个连续区间内的最大值/最小值，同时可以节省O(logN)的时间复杂度；

action item：
1. 明天刷关于manacher和dijkstra算法的题目；

Day 5:今日刷了五题，有四题是昨天contest的题
1.Hamming distance：就用XOR function直接做
2. Can make arithmetic progression from sequence:问给定数列是否是等差数列，当然可以sort, O(nlogn)。还可以找到公差，再把此数组放到hashset里面，用首项和公差来verify是否是等差数列, O(n).
3. Last moment before all ants fall out of a plank：绿皮书有这题，有巧解
4. Count submatrices with all ones：这题挺难的只想到了普通的DP解。最优解要用DP加一个stack
5. Minimum Possible Integer After at Most K Adjacent Swaps On Digits： 这题真的不会做，看了答案发现需要greedy和segment tree/binary indexed tree做。自己implement一遍好难哇！

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

6. ZigZag Conversion
string, result=[''] * numRows, 对每个 c in s 更新对应的row

66. Plus One
string

67. Add Binary
string

今天做了Is Subsequence, Nim Game, Stone Game，其中Is Subsequence这道题的follow up需要提前处理下字符串t，记录每个字符的位置，然后用二分查找来快速找到下一个匹配的字符的位置。Nim Game和Stone Game这两道题的DP做法还要再学习一下。