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

06.23. 2020  3道题+ 1道OOD（烦请楼楼加米啊，好多天了，没有米的日子很难过😫））
刷题12天 打卡12天
Leetcode 1290.
Convert Binary Number in a Linked List to Integer

Mindset:
reverse the linked list
then calculate one by one

605. Can Place Flowers

Greedy! and not hard or not even a medium.


771.Jewels and Stones
Mindset: use a HashSet and an int variable to record how many J stones I have.

OOD：
Elevator System（至少两部电梯）

注意：
电梯的每个workflow是什么：是“每个楼层”（其中的逻辑是停或者不停，背后的原因是scheduling判断它需不需要停）
request要写成一个类
然后对于电梯内部的指令是要求从request1当中来
而对于电梯外部，即楼层类的指令是通过control system过来的

另外，对于可扩展而言，每个单独的电梯可以作为一个最高大脑，只有电梯赚到wait状态才会去拿外部的指令；
或者building是一个最高层的大脑，可以调度所有的电梯；要根据实际需求细化control的类型和方式。

day 13 #sql 6题
1. update语句之间用逗号连接--where...
2. replace into...
3.修改表名 alter table... rename to ....
4.创建外键约束foreign key(...) references ....
5.获取两表相同数据，注意主键

打卡5个题

发帖第一天，一共刷了10道题，
今天刷的是Array这个Tag的题，
1. 几道用动态规划求解决方案数量的问题，这个比较常见，一般看到求解决方案的数量，就可以联想到dp
2. Missing Number这个题目，有一种XOR的解法比较有技巧性，虽然是一道easy的题目，但是如果对XOR不熟的话是很难想到的,XOR的几个知识点，第一支持交换律第二0与任何一个数 XOR得到的是哪个数本身第三一个数自己和自己XOR得到的是0
3. 关于螺旋举证的解法，其实就是分4步，从左到右，从上到下，从右到左，从下到上

慕容清 发表于 2020/06/23 11:28:48
打卡14天:

232.implement queue using stack: 这题可以用两个stack，一个inpu...

打卡15天

8.atoi, 主要就是各种case需要进行判断。str.trim().toCharArray(); .trim()可以直接去掉string前后的所有空格。转化成char之后比较好操作。可以直接进行和‘0’想减来得到数字。
刷剑指刷到不用任何循环语句给出1+2+…+n求和。这题用了逻辑符短路做的，感觉有点脑筋急转弯。
121.Best time to buy and sell stock I, 今天又重新做了一下买卖股票这题，这题的变形也有很多种。最基本的是说找出两天，先买后卖，最大利润。这题一开始的想法是暴力解法。之前做的直接看了其他解法的代码，今天又看到这题才明白用的是动态规划的思路。如果用dp[i]来表示第i天的最大利润，那么dp[i] = max (dp[i - 1], prices[i] - min[0: i -1])作为转移方程。之后代码实现就是dp[i]直接被一个变量取代，然后min也是可以直接被一个变量取代。时间复杂度是O(N)。
122.Best time to buy and sell stock ii: 是不限于买卖一次，可以多次买卖；如果能够画图来说明，其实是将所有的“爬山”的高度差进行逐天累加就可以了。如果是下山，那么只要遇到了再次爬山就是盈利的情况。如果是连续爬山，那么完全可以拆分成累计连续的两天之间进行相互累加。
238.Product of Array except self: 在不允许使用除法的情况下，可以把array扩成一个对角为1的矩阵，之后第一次循环计算左下角乘积，第二次循环计算右上角和之前得到的array中相应元素的乘积。
138.single number: 找到一个数，而且只有一个数，没有重复两次。这题是用位运算进行操作的。对于任何一个数，和本身进行异或是零，如果是和零进行异或就是本身，而且异或运算满足交换率。所以就是说如果其他数都是成对的，那么由于交换律成立，所以两两相抵。最后只剩下那个数，和零异或得到本身。

236.single number III 是只有两个数只出现了一次，其他的都出现了两次，还是位运算。有几个点之前没有接触到的一个是 m & -m low bit操作，能够找到最后不是0的那一位。那么对整个数组的数进行异或操作，得到所要的两个数的异或值x ^ y，之后取该值的low bit，那么x和y中的一个一定在该位为0，一个为1；再次遍历array，将nums分为两组，在那位上取0，取1；进行异或，成对元素相抵，剩下的分别是x和y。

打卡第一天，6题。

继续打卡，做了三道题

• Reverse Pairs 考点是结合merge sort，从两边sorted segment里面找出所有的pair
• Count Complete Tree Node 考点是找出tree height，比较左右children的height是否相同，再做recursion处理
• Partition Equal Subset Sum 考点是0-1 背包问题，选出一个等于sum的subset， 剩下的就是另一个subset
  

2020年6月23日，第二十二天发帖。今天面了一轮电子港湾，另外写了个自我检讨式的面经，所以只刷了4道题：

138. Copy List with Random Pointer。这道题的最优解操作实在是太骚了。得抽空专门整理一下这些骚操作。
1067. Digit Count in Range。这道题虽然打了DP的标签，但是做题的感觉和DP没有半毛钱关系，这完全就是个纯数学题。自己的思路是：考虑到之前有一个题是数没有9的数的个数，那么反过来就是“数至少包含1个9的数的个数”，那道题当时是按照数9的n次方来叠加计算的，于是这次自己也试图用（10^N - 9^N) × digit然后求和，但答案说这是错的。事实上：这个算法没有考虑到其它位上digit可能和target digit相同而增加的count。于是参考答案换了个思路：数每个数位上target digit出现过的次数，另外对于0要做个特殊处理，排除0XXX这样的数计入总数。这道题花了两个小时才彻底厘清思路加AC。如果面试碰上那我只能背答案了。
169. Majority Element。这道题用来复习Boyer Moore算法。2分钟AC。当然面试中还是先给一个用map求解的方式，然后过渡到这个最优解。
210. Course Schedule II。二刷这道题，复习了一下拓扑排序算法的BFS实现。

总结一下：
0. 今天复习了Boyer Moore算法和拓扑排序；
1. 定期总结特定类型的题目非常重要，这样才能在考场上触类旁通；

Action item：
1. 明天学习算法：Dijkstra
2.  明天复习算法：KMP
3. 明天总结题目：链表

打卡第23天

打卡第22天， 刷了3道题

15. 3Sum
4sum 的简化， 注意跳过重复的数

16. 3Sum Closest
和上题类似，先排序，然后用3个指针，O(n2)

22. Generate Parentheses
backtracing. Use two integers to count the remaining left parenthesis and the right parenthesis.
if right = 0 append
if left > 0 add '('
if right>left add ')'