刷题记录帖子

LeetCode 150. Evaluate Reverse Polish Notation (Python)

原理理解了，这里好多 Python 的细节考察啊！～

How to round to Zero + How to get Python string a number either postive or negative

LeetCode 695. Max Area of Island (Python)

DFS 经典运用，题目答案比较奇怪，但是简洁。

1710        Maximum Units on a Truck        Easy

94        Binary Tree Inorder Traversal        Easy        5        Morris Traversal of O(1) Space

145        Binary Tree Postorder Traversal        Easy

22        Generate Parentheses        Medium        5        DFS + Purning

1. class Solution:
   
2.     def generateParenthesis(self, n: int) -> List[str]:
   
3.         ans = []
   
4.         def backtrack(S = [], left = 0, right = 0):
   
5.             if len(S) == 2 * n:
   
6.                 ans.append("".join(S))
   
7.                 return
   
8.             if left < n:
   
9.                 S.append("(")
   
10.                 backtrack(S, left+1, right)
    
11.                 S.pop()
    
12.             if right < left:
    
13.                 S.append(")")
    
14.                 backtrack(S, left, right+1)
    
15.                 S.pop()
    
16.         backtrack([], 0, 0)
    
17.         return ans

复制代码

759        Number of Subarrays with Bounded Maximum        Medium        5        half close half open to remove duplicates

1. class Solution:
   
2.     def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:
   
3.         # pick each ele to be maximum ele
   
4.         # Then sliding windows
   
5.         res = 0
   
6.         for ind,num in enumerate(nums):
   
7.             # num itself is in or not
   
8.             if left <= num <= right:
   
9.                 res += 1
   
10.                 # sliding windows
    
11.                 # p1, p2 in
    
12.                 #   in range 0~len(nums)
    
13.                 #   nums(p1) < num
    
14.                 #   nums(p2) < num
    
15.                 p1, p2 = ind-1, ind+1
    
16.                 while p1 > -1 and nums[p1] < num:
    
17.                     p1 -= 1
    
18.                     res += 1
    
19. 
    
20.                 while p2 < len(nums) and nums[p2] <= num:
    
21.                     p2 += 1
    
22.                     res += 1
    
23. 
    
24.                 if p1+1 != ind and p2-1 != ind:
    
25.                     res += (ind-p1-1) * (p2-ind-1)
    
26.         return res
    
27.                
    
28.             

复制代码

1903        Largest Odd Number in String        Easy

理解下，什么事奇数，其实只用看最后一位。

1904        The Number of Full Rounds You Have Played

分类讨论，同时掐头去尾来计算时间。

1. class Solution:
   
2.     def numberOfRounds(self, startTime: str, finishTime: str) -> int:
   
3.         res = 0
   
4.         if startTime < finishTime:
   
5.             # not overnight
   
6.             s = startTime.split(":")
   
7.             f = finishTime.split(":")
   
8.             res = 4 * ( int(f[0]) - int(s[0]) - 1)
   
9.             t1 = s[1]
   
10.             if t1 == "00": res += 1
    
11.             if t1 <= "15": res += 1
    
12.             if t1 <= "30": res += 1
    
13.             if t1 <= "45": res += 1
    
14.             
    
15.             t2 = f[1]
    
16.             if t2 >= "15": res += 1
    
17.             if t2 >= "30": res += 1
    
18.             if t2 >= "45": res += 1
    
19.             
    
20.         else:
    
21.             # overnight
    
22.             # Day 1
    
23.             s = startTime.split(":")
    
24.             f = finishTime.split(":")
    
25.             res = 4 * ( 23 - int(s[0]))
    
26.             t1 = s[1]
    
27.             if t1 == "00": res += 1
    
28.             if t1 <= "15": res += 1
    
29.             if t1 <= "30": res += 1
    
30.             if t1 <= "45": res += 1
    
31. 
    
32.             # Day 2
    
33.             res += 4 * (int(f[0]) )
    
34.             t2 = f[1]
    
35.             if t2 >= "15": res += 1
    
36.             if t2 >= "30": res += 1
    
37.             if t2 >= "45": res += 1
    
38.         return res

复制代码

LC 1905,  Count Sub Islands

比较经典的题目，还是要检查基本题型的写法，熟悉胖头鱼的思路。

1. class Solution:
   
2.     def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
   
3.         res = 0
   
4.         nrows = len(grid2)
   
5.         ncols = len(grid2[0])
   
6.         directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]
   
7.         self.path = []
   
8.         # grid1 + grid2 and only search for 2
   
9.         # Then in grid2 search if find any island has 1 or 0 is wrong
   
10. 
    
11.         for i in range(nrows):
    
12.             for j in range(ncols):
    
13.                 if grid2[i][j] == 1 and grid1[i][j] == 1:
    
14.                     grid2[i][j] = 2
    
15.         print(grid2)
    
16.         # DFS
    
17.         visited = []
    
18.         for _ in range(nrows):
    
19.             tmp = []
    
20.             for _ in range(ncols):
    
21.                 tmp.append(0)
    
22.             visited.append(tmp)
    
23. 
    
24.         def DFS(r, c):
    
25.             visited[r][c] = 1
    
26.             self.path.append(grid2[r][c])
    
27.             for d in directions:
    
28.                 tmp_r, tmp_c = r+d[0], c+d[1]
    
29.                 if -1 < tmp_r < nrows and -1 < tmp_c < ncols and not visited[tmp_r][tmp_c] and grid2[tmp_r][tmp_c]:
    
30.                     DFS(tmp_r, tmp_c)
    
31. 
    
32.         for i in range(nrows):
    
33.             for j in range(ncols):
    
34.                 if not visited[i][j] and grid2[i][j] == 2:
    
35.                     self.path = []
    
36.                     DFS(i, j)
    
37.                     # print(self.path)
    
38.                     if not (1 in self.path):
    
39.                         res += 1
    
40. 
    
41.         return res

复制代码