刷题记录帖子

1323. Maximum 69 Number

其实就是 Python list index 方法， try except 的练习

140. Word Break II

MaxMing 的这个讲解真精彩，入木三分， https://www.youtube.com/watch?v=wSGIQW0uaeo。

核心要点，如何利用 memo 简化计算并且得到结果。同时通过 DFS 找到合适的单词。

LC 70. Climbing Stair

其实就是斐波拉契数列的在特定场景中的实现，参考这个官方讲解非常好。

https://leetcode.com/articles/climbing-stairs/

LC 520. Detect Capital

简单题，其实还是非常简单的。

主要下 Python 的惯用法，还有如何combine case 2 和 case 3

最后吐槽下 Python 的 函数命名，天秀，为什么不保持一致。多写个 s 其实也没多少工作量。
 

125. Valid Palindrome

简单题目，其实就是一个 double pointer 的题目，参考这个帖子。

https://maxming0.github.io/2020/08/03/Valid-Palindrome/

342. Power of Four

我是直接 log 然后判断奇数和偶数做得。

还有更加巧妙的，参考这个贴子， https://maxming0.github.io/2020/08/04/Power-of-Four/

一个数是4的幂一定是2的幂，区别是对3取余的结果不同

为什么偶数是 n&(n-1) == 0 是偶数除了0，https://maxming0.github.io/2020/06/08/Power-of-Two/ 有详细讲解

代码

1. 
   
2. 
   
3. class Solution:
   
4.     def isPowerOfFour(self, num: int) -> bool:
   
5.         return num > 0 and num & (num - 1) == 0 and num % 3 == 1
   
6. 
   

复制代码

442 Find All Duplicates in an Array

我也想到了下标对应数值的map，就是思路是把元素挪动位置，这样要是出现位置被占用就知道重复了。
但是这个思路需要考虑的 edge case 太多了，不如直接把遇到的元素数值反转成负数，这样更加简洁方便，通过负数与否记录是否出现。推荐这个视频讲解，秒，三言两语说明了思路和要点。 https://www.youtube.com/watch?v=Jgz2nHjydUY&t=0s

LeetCode 987 Vertical Order Traversal of a Binary Tree

Sorting a List of Elements by the First element but if Equal sort by the second == > Forming a tuple and range them by order

1. tmp = sorted(res[i], key=lambda tup: (-1 * tup[1],tup[2]))
   

复制代码

MaxMing 的讲解很好， https://maxming0.github.io/2020/ ... l-of-a-Binary-Tree/

当然我的做法就是慢慢来解决，当然代码不太清晰但是还是可以看出功能。

LC 994 Rotting Oranges

这个题目其实还是很明显的 DFS，但是做得时候很多细节，很多 edge case 需要仔细考虑。
核心要点
(1) 如何解决何时结束的问题？？
通过最后的数目来判断，改变的 rotten 数目应该等于 fresh 数目

(2) 如何避免反复 DFS？
通过 queue 来解决重复 DFS 的问题。

(3) 用 queue 的时候，有一个问题，比如 queue 有三次调用，其实时间只过了 2 min，因为我们统计的是间隔时间。
很简单，

1. 
   
2. if queue:
   
3.         result +=1
   

复制代码

只有 queue 不空才统计。

1. 
   
2. class Solution:
   
3.     def orangesRotting(self, grid: List[List[int]]) -> int:
   
4.         result = 0
   
5.         rotten = 0
   
6.         nrows = len(grid)
   
7.         ncols = len(grid[0])
   
8.         fresh = 0
   
9.         queue = []
   
10.         # get basic statistics
    
11.         for i in range(nrows):
    
12.             for j in range(ncols):
    
13.                 if grid[i][j] == 1:
    
14.                     fresh += 1
    
15.                 if grid[i][j] == 2:
    
16.                     queue.append((i,j))
    
17.         # using rotten orange queue to change
    
18.         while queue:
    
19.             rottenLen = len(queue)
    
20.             #print(queue)
    
21.             while rottenLen > 0:
    
22.                 r,c = queue.pop(0)
    
23.                 # search four adjacent cells
    
24.                 if r-1 >= 0 and grid[r-1][c] == 1:
    
25.                     grid[r-1][c] = 2
    
26.                     queue.append((r-1, c))
    
27.                     rotten += 1
    
28.                 if c-1 >= 0 and grid[r][c-1] == 1:
    
29.                     grid[r][c-1] = 2
    
30.                     queue.append((r, c-1))
    
31.                     rotten += 1
    
32.                 if r+1 < nrows and grid[r+1][c] == 1:
    
33.                     grid[r+1][c] = 2
    
34.                     queue.append((r+1, c))
    
35.                     rotten += 1
    
36.                 if c+1 < ncols and grid[r][c+1] == 1:
    
37.                     grid[r][c+1] = 2
    
38.                     queue.append((r, c+1))
    
39.                     rotten += 1
    
40.                 rottenLen -= 1
    
41.             if queue:
    
42.                 result += 1
    
43. 
    
44.         if rotten == fresh:
    
45.             return result
    
46.         else:
    
47.             return -1
    

复制代码

LC 171 Excel Sheet Column Number

Easy 题，就是 26 进制题目的变体。

不过写法上，其实也有点讲究，更好地解法不是一遍遍计算 26^n 的结果，而是应该这样，

不过实际检验下，发现其实也没多大优化。。。估计是太短了，同时其他计算才是主要部分。