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

刷题第三天， 今天做的是dp的题。

06/11

复习dp：Lintcode 1834：grouping option
BFS：111 752 314

2020年6月11日，第十天发帖，今天刷了8道题：

以下所有题目全是LC的pick one：
798. Smallest Rotation with Highest Score。昨天刚刚看到了一个类似的题目，也想到了brute force的O(N^2)的做法，但是这么一个看起来如此”规整“的题目应该是有更优解的。如果是在面试的时候我就会和面试官说我先写这个了。于是想不出更优解只好去翻答案，神乎其技又学到新算法了（我是个转专业的小菜鸡，每次刷题都能学到新东西）。
1122. Relative Sort Array。为了安抚自己做的一道题，完全符合treemap的适用案例。于是很快就AC了。
713. Subarray Product Less Than K。这个题目思路变了很久，一开始想到了可以用两层嵌套循环挨个数，时间复杂度O(N^2)，但是后来又想到如果一个subarray满足乘积小于某个数，那么它所有的subarray都满足同样的条件。于是这样子只需要学会如何数数就行了。不过也是不太容易操作，因为会有叠加。后来想到：只数固定以左指针开始的subarray就可以避免重复了，于是问题变成了一个sliding window。
985. Sum of Even Numbers After Queries。这题题干好长，估计面试的时候要出这个题面试官解释都要解释半天。其实本质上就是维护一个array，看数值变化的奇偶性。
869. Reordered Power of 2。这题也挺简单的，统计字符就好了。
1263. Minimum Moves to Move a Box to Their Target Location。这是今天最难的一道题了，以推箱子游戏做背景的问题。自己想到的办法是：用BFS，根据另一层BFS计算shopkeeper可以到达的每一个位置，再以此为基础，enqueue每一个箱子可以到达的下一个位置。不过这样子时间复杂度就是一层BFS的平方，实在是太高了。于是看了答案后深深佩服这个想出state这个概念的人，也佩服他居然可以忍住不吐槽这么恶心的题目。
1413. Minimum Value to Get Positive Step by Step Sum。今天最简单的一道题，presum，7分钟AC。
353. Design Snake Game。说实话这个题的核心思路不算难，解决蛇的位置和顺序需要两个机制：一个可以快速找出首尾的机制，一个可以快速根据索引搜索查找定位的机制。这个思路出现过很多次了：Map + 双链表。同样的方法可以用在LRU Cache上。这样每一个move call的时间复杂度就是O(1)。不过花了太长的时间debug。

总结一下：
0. 简单了解了interval stabbing算法；
1. 在不知道如何有效debug的时候，可以试着和面试官交流一下，说不定会受到启发；
2. 状态（state）这个概念的适用范围不只是DP，还可以是DFS和BFS。

action item：
1. 继续了解interval stabbing；
2. 继续刷更多BFS题目。

继续刷leetcode database的题了
#180-#183 06/11/2020
Takeaway:
除了#180有难度外 剩下3道不是很难
take away: window function lead()的用法

上一周工作太忙了 一直没打卡 自责中。。。

day3 打卡5题

打卡第10天， 刷了3道有关树的题

124. Binary Tree Maximum Path Sum
把题理解成从leaf到leaf， 结果怎么也过不了。用recursive, 注意各种边界条件。

236. Lowest Common Ancestor of a Binary Tree
用recursive， 得到左边的lowestCommonAncestor 和右边的lowestCommonAncestor，如果left is null，返回right，反之返回left，如果都有值，则返回root

257. Binary Tree Paths
recursive. DFS.

Reviewed the FB questions and learned Reservoir sampling Algo
1. Add Strings
2. Add Strings with floating point
3. Read N Characters Given Read4 II - Call multiple times
4. Binary Search Tree Iterator
5. Random Pick Index
6. Linked List Random Node (Apply reservoir sampling Algo)
7. Random Pick Index (Apply reservoir sampling Algo)

6.11号 6题（第二张图片是之前漏传的一天的数据）主要做的sliding window的题型
76. minimum window substring        3
567. Permutation in String        2
438. Find All Anagrams in a String        2
3. Longest Substring Without Repeating Characters        2
66. Plus One        1
91. Decode Ways        2

有个讲解总结的还不错网址：https://labuladong.gitbook.io/al ... kou-ji-qiao-jin-jie
我是用Java的 所以我又用Java转换了一下，转换过程中遇到个问题：Integer比较，耽搁了很久，我就补贴代码了，需要代码的可以私信我。

Day 1. 打卡

day12

lc new 6 review 10+
今天新题做的都是easy嘻嘻
复习了昨天头痛的All one！基本思想是用DDL node 作为一个个bucket， node 有count的属性，就是出现了几次，还有一个linkedhashset 放不同的key；按count从小到大连起来，头尾加上head,count =min, tail,count =max；insert 新的key之后就向后移动一个bucket； delete一个key之后向前移动；
今天尝试了控糖，控制食量，注意力好了不少！

Most recent submissions
AcceptedjavaMinimum Remove to Make Valid Parentheses   6 minutes ago
AcceptedjavaLongest Valid Parentheses   22 minutes ago
Read N Characters Given Read4 II - Call multiple times   1 hour, 18 minutes ago
AcceptedjavaRead N Characters Given Read4   1 hour,
Flood Fill   1 hour, 29 minutes ago
AcceptedjavaN-Queens   1 hour, 52 minutes ago
Wiggle Sort II   2 hours, 4 minutes ago

mock
题目大意是做过的number of islands，体会到了什么是中奖的快乐，还是要多刷题，广撒网