刷题记录帖子

1025. Divisor Game

最关键的是 质数 只有 2 一个 偶数，所以如果得到 偶数，你就稳赢了，你只要减去 1 给对方 奇数。
拿到了 奇数，你就只能 奇数 - 奇数 得到 偶数，最后给对手 2。
这个时候 ta 减去 1， 你只有（0，1） 可以选择，但是大于0小于1 的整数不存在，你输了。

这个解释不错。

https://leetcode.com/problems/di ... lution-in-Python-3-(With-Detailed-Proof)

1022. Sum of Root To Leaf Binary Numbers

这个题目其实又一次证明了一个观点， recursive 是对付 tree 的良方。看到 tree 第一个想法一定应该是想想如何用 recursive 来做。
这个视频也是不错的参考资料， https://www.youtube.com/watch?v=ge3Q2-eElLI

129. Sum Root to Leaf Numbers

做过类似的题目，就是前天，1022. Sum of Root To Leaf Binary Numbers，其实思路就是比较简单的，path Sum 其实每个数都是一个数位上的数字，这个就是类似十进制，二进制。

当然这也说明了，Leetcode 出题目是会重复的啊！
前两百，前三百，不放心的前四百，应该，应刷尽刷，后面很大概率会重复或者用到的知识你已经熟练掌握。

不同的 level 代表不同的 大小，最后到了 leaf 加上最后的统计量即可。

当然需要做好 tree 的递归。

62. Unique Paths 经典题目，还是依靠 grid 来做 dp。

LC 441. Arranging Coins, 1/July, 争取这次全勤。

还是很简单的 binary serach 做得，但是发现其实还有更简单地公式做。
好吧，我 SB 了，就是坚持用 CS 的思维做，其实可以用公式的。也就是说，得到解析公式的时候，其实还是可以尝试直接做的。

leetcode 957,  prison cells after n days

显然直接做是不行的，关键信息是 N 的范围， 10^9 这是一个超出时间限制的数字。

所以肯定要找方法加速，然后就是找规律。

可以肯定，两端的 cell 一定是 0 只要经过一天，因为没有两个邻居。

然后我们可以改变的 cell 只有1~6，这么 6 个 cell。然后其实就是怎么发现这是一定规律性的图。首先，从前一个 state 到下一个 state 是 确定性的，也就是是唯一的，然后，总共可能的状态只能 有 2^6 个，64 个。

所以一般而言，经过最多变化 64 次一定会有相同的 state 出现，可能 cycle length 比 64 更小，但是最大也只可能是 64。

然后就比较简单了，找出这个 cycle length 即可。注意下，你的初始状态占用一个位置。
本来准备用 string 做 key 发现，其实不需要。

264. Ugly Number II 真是精彩绝伦的题目。融入了 merge sort 的思想，而且是悄默默地体现出来的。
完全想明白题目之后，拍案叫绝。

首先最重要的就是知道，其实新生成的元素，应该是已经存在的元素，x2， x3， x5 得到的。但是下面的问题就是怎么排序。

如果把 x2，x3，x5 想成三条生产线，其实就是不断把三个生产线生产出的元素插入进去，而且是只能把三个生产线当前最小的产品插入最后的 result list。
如果该 list 被插入，那么就可以生产下一个元素，即从 result list 往后移动一位，另外两条生产线保持原状。

核心是，下一个进入生产线的原料必须是 result list！！！
也是我没想到的。

leetcode 461, hamming distance

简单的 XOR 然后统计 1  的个数。

统计 1 在二进制数中的个数，有高效的算法 Brian Kernighan's Algorithm ，参考这个帖子， Count set bits in an integer， https://www.geeksforgeeks.org/count-set-bits-in-an-integer/

Brian Kernighan’s Algorithm: & is bitwise AND. So n = n & (n - 1) clears the rightmost set bit in n.  That’s where the difference between n and n-1

1. 
   
2. 
   
3. # Function to get no of set bits in binary
   
4. # representation of passed binary no. */
   
5. def countSetBits(n):
   
6.   
   
7.     count = 0
   
8.     while (n):
   
9.         n &= (n-1)
   
10.         count+= 1
    
11.       
    
12.     return count
    

复制代码

So if we subtract a number by 1 and do bitwise & with itself (n & (n-1)), we unset the rightmost set bit. If we do n & (n-1) in a loop and count the no of times loop executes we get the set bit count.

The beauty of this solution is the number of times it loops is equal to the number of set bits in a given integer.

10 in binary is 00001010
  9 in binary is 00001001
10&9 =====>  00001000 ( 8 )
  8 in binary is 00001000
8&8 ======>  00001000 ( 8 )
  7 in binary is 00000111
8&7 ======>  00000000

Plus One | LeetCode 66
虽然是简单题目，但是还是挺有挑战性的，需要想清楚怎么做。怎么写出没有冗余的代码。 看这个帖子发现还真有不用carryer 的解法， https://www.youtube.com/watch?v=yzlQj0LR7m8

核心就是把 return 放入循环，其实如果发现不用进位，即可以返回。如果到了必须跑完所有数字的情况，自动就是你需要多出一位的最高位为1的进位。

比我的写法，大大简化。

LeetCode 463 Island Perimeter

虽然不是很难的题目，但是其实做起来也是有很多讲究的。

(1) 循环做，对于每一个 land cell 判断有几个 edge

有几个改进，

1. 只需要计算四条边的两条就行了，其实很简单，就是每个 land cell 贡献 4 个 edge，但是如果有 land cell 邻居，那么就会减少 2 个，各自减少 1 条。但是对于 4 条边，为了避免重复计算 ( 假设每个边减少都计算的，会重复计算 ) 所以只需要计算 当前 cell 的两条边即可。

当然也可以看到，其实可以直接用grid cell 中的 数值，因为分别是 0，1 其实加减 0 不影响最后结果，特别是在你直接算每个 land cell 贡献 4 个边的时候。

(2) DFS 做

这个其实更见复杂了，因为 DFS 需要做两件事，一计算当前 cell 贡献多少 edge，二周边 cell 贡献多少 edge