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

Day 25, 刷三道题，两道新题：

Reconstruct Itinerary        LC 332
Valid Anagram        LC 242

1. 第K大数，quick select算法，可以只用left判断，返回条件是start > end: return nums[start]

2. 重新安排行程。本质是寻找一个图的欧拉路径。建图、排序、贪心选字典序最小都没有问题，dfs访问图，关键是最后是返回逆序的结果...不是很理解为什么这样做是对的。

3. Valid Anagram。可以用26个字母范围的数组计数器表示，进阶才是用hash。最后还要return len(cnt_s) == 0。

打卡第28天

06/28 第二十七天 已经进入最后几天了 感谢版主一直再更进 希望下个月有类似活动 今天三题

n 的第 k 个因子 遍历一遍所有因子 找到第k个
数组中的第K个最大元素 这个题比价好理解的是借助堆来实现  可以直接里用最小堆 维持size为 k同时所有元素都入堆 那么 堆顶就是所求
在排序数组中查找数字 I 题意比较明确 即实现查找算法 一般用二分查找

Day 19
Have been doing premium problems recently.

6.28 连续第八天 打卡四题

LC332. Reconstruct Itinerary，postorder DFS，对于每个城市，DFS访问所有相连的城市，删掉访问过的边。访问完所有相连的城市后，将当前城市保存的结果（需要addFirst，或者最后reverse result list）。
LC729. My Calendar I，TreeMap的应用。
LC57. Insert Interval，one pass，需要注意讨论全各种情况。
LC1498. Number of Subsequences That Satisfy the Given Sum Condition ，Sort+Binary Search，需要注意到sort（即改变各个元素相对位置）不会影响结果。sort之后将nums[i]作为最小值，用binary search找到最大的合适的nums[j]作为最大值，这两者之间可能的subsequence数量可以直接用组合数学计算。

刷题打卡第一天, 居然今天才看到这个帖子

菜鸡第二十九天

今天还是五道题
1. longest substring without repeating characters: 可以用two pointer + set，每次遇到新的char，如果不在set里，就加进去
    并且把fast pointer向前移，如果char在set里，就去掉当前char并且把slow pointer向前移
2. trapping rain water：用two pointer 同时从左右两边分别记最大值，如果leftmax < rightmax, 就把leftmax - height[left]加
    到result，再把left pointer向右移，不然就加rightmax-height[right]再把right pointer 向左移
3. product of array except self: 可以用两个array分别盛1, nums[1], nums[1]*nums[2],... 和nums[n-1]*nums[n-2], ...不用第二个
    array的话可以用一个temp从右向左每次res[i]乘以temp，temp再乘以nums[i]
4. diameter of binary tree: 可以用recursion，类似找maxdepth，但每次update result, 用left, right children的recursion，取最大值
5. sqrt(x): 可以用 binary search，学习了一下Newton's method, 让r=x, 每次update r = (r + x/r)/2直到r^2 > x

今天毫无动力，又水了一天

第七天，三题

今天做了三道关于sliding window的hard 可 太 hard 了……

995. Minimum Number of K Consecutive Bit Flips 关键在于要把A[i]（当前值）的受其之前的值（当然要在K长度范围内）影响而flip的次数（flippedtimes）算出来，如果flippedtimes为奇数（A[i]肯定会变）且A[i] = 1 或 flippedtimes为偶数（A[i]不会变）且A[i] = 0，那么A[i]肯定要再flip一次

30. Substring with Concatenation of All Words 感觉和传统sliding window做法有点像，要设置和给定word length一样的window然后挨个和word list比较，不一样的继续往右挪

周打卡，总是忘记一天一天的计数，哭哭。。。
sql的easy刷完啦，虽然刚刚看到一个新题，接下来开始刷python的easy。加油~~~