刷题记录帖子

525. Contiguous Array 其实还是

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.

所以第一是把0转化成 -1 这样就和 1 有了相反的相加效果，起到了最后方便分辨数目的效果。
然后就是，通过 记录所有位置之前的所有的 -1，1 之和得到前面所有数字的和，然后记录下第一次出现的位置，然后后面如何 balanceFactor 又一次归零了，说明中间其实是相等数量的0，1然后只要用后面的一个 index 减去 第一次出现的 index 就得到了新的 subarray 长度。
后面只要比较记录全局最大即可。
需要注意的是，后面出现的一定是比前面出现的 subarray 更长，只要 balanceFactor 相等。

注意三点，

第一， balfactorTable[0] = -1 第一个元素的 balanceFacor 的位置，需要记录为 -1
第二，全部数组的 balanceFactor 是 0 所有所有数组都是的，都需要计入。
第三， maxLen 的最小值，因为题目保证一定存在，所以其实是 2.

678. Valid Parenthesis String  还是通过两个堆栈来解决，难点在 * 是可以匹配 （，），empty string 所以就造成需要考虑多个匹配的情况。
这里想到的方法就是 左括号 stack 和 星号 stack，先用左括号和右括号匹配，不够就用星号。如果出现两个stack 都空但是还有 右括号就说明不匹配。
最后对于剩下左括号用星号匹配掉，但是这里有个前提，就是 （* 是可以的，但是 *（ 不可以，所以必须星号的坐标大于左括号。

1. 
   
2. 
   
3. class Solution:
   
4.     def checkValidString(self, s: str) -> bool:
   
5.         leftStack = []
   
6.         starStack = []
   
7.         i = 0
   
8.         for ch in s:
   
9.             if ch == '(':
   
10.                 leftStack.append(i)
    
11.             if ch == '*':
    
12.                 starStack.append(i)
    
13.             if ch == ')':
    
14.                 if leftStack:
    
15.                     leftStack.pop()
    
16.                 elif starStack:
    
17.                     starStack.pop()
    
18.                 else:
    
19.                     return False
    
20.             i += 1
    
21. 
    
22.         while leftStack:
    
23.             if starStack and starStack[-1] > leftStack[-1]:
    
24.                 leftStack.pop()
    
25.                 starStack.pop()
    
26.             else:
    
27.                 return False
    
28.         return True
    

复制代码

200. Number of Islands 精彩的题目，巧妙的把 DFS/BFS 思想用到2d grid 上。所谓的小岛的连通性就是 DFS 可以到达。

1. 
   
2. class Solution:
   
3.     def numIslands(self, grid: List[List[str]]) -> int:
   
4.         count = 0
   
5.         for i in range(len(grid)):
   
6.             for j in range(len(grid[0])):
   
7.                 if grid[i][j] == "1":
   
8.                     self.dfs(grid, i, j)
   
9.                     count += 1
   
10.         return count
    
11.    
    
12.     def dfs(self, grid, i, j):
    
13.         if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] != "1":
    
14.             return
    
15.         grid[i][j] = "0"
    
16.         self.dfs(grid, i, j - 1)
    
17.         self.dfs(grid, i, j + 1)
    
18.         self.dfs(grid, i - 1, j)
    
19.         self.dfs(grid, i + 1, j)[/i][/i][/i][i][i][i]

复制代码

[/i][/i][/i]

新编的题目 30 challenges ， First Unique Number. 其实还是很简单的，就是考察基础的设计题目。

LC 124. Binary Tree Maximum Path Sum
注意点，当前节点的最大可能返回值和全局的最优解。我画了一个总结图在下面。

1232. Check If It Is a Straight Line 很简单的题目，不过练习下复杂程序写法。

Leetcode 367 Valid Perfect Square
经典的二分搜索算法的写法，值得记住如何写。

当然还有奇技淫巧，  (num ** 0.5).is_integer()

楼主都是按照什么顺序刷

LC 997 Find the Town Judge
很有趣的题目，其实就是图的连通性，不过应为简化为有向图的连接列表表示，所以其实可以用 hasttable 解决。

当然最正统的做法是 用 图 的 in_degree 和 out_degree 来解决这个问题。
优化的方法是可以把 in 和 out 合并，只需要使用一个 array 即可以记录每个节点的 degree 然后进行统计。～

278. First Bad Version 还是二分搜索的套路, 当然这道题目需要提醒自己，有时候简化代码的时候我们并不都是需要 return mid 有时候其实 return left or right 也是常见的某种模式。