刷题记录帖子

1290        Convert Binary Number in a Linked List to Integer        Easy

1306        Jump Game III        Medium        4        DFS / BFS

经典题目，全文背诵

1. """
   
2. 
   
3. BFS
   
4. 
   
5. """
   
6. 
   
7. class Solution_BFS:
   
8.     def canReach(self, arr: List[int], start: int) -> bool:
   
9.         n = len(arr)
   
10.         q = [start]
    
11. 
    
12.         while q:
    
13.             node = q.pop(0)
    
14.             # check if reach zero
    
15.             if arr[node] == 0:
    
16.                 return True
    
17.             if arr[node] < 0:
    
18.                 continue
    
19. 
    
20.             # check available next steps
    
21.             for i in [node + arr[node], node - arr[node]]:
    
22.                 if 0 <= i < n:
    
23.                     q.append(i)
    
24. 
    
25.             # mark as visited
    
26.             arr[node] = -arr[node]
    
27. 
    
28.         return False
    
29.       
    
30. """
    
31. 
    
32. DFS
    
33. 
    
34. """
    
35. 
    
36. class Solution_DFS:
    
37.     def canReach(self, arr: List[int], start: int) -> bool:
    
38.         if 0 <= start < len(arr) and arr[start] >= 0:
    
39.             if arr[start] == 0:
    
40.                 return True
    
41. 
    
42.             arr[start] = -arr[start]
    
43.             return self.canReach(arr, start+arr[start]) or self.canReach(arr, start-arr[start])
    
44. 
    
45.         return False

复制代码

563        Binary Tree Tilt        Medium        4        post-order DFS

"""

post-order DFS

"""

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findTilt(self, root: Optional[TreeNode]) -> int:
        self.ans = 0
        
        def totalSum(node):
            if not node: return 0
            
            left_sum = totalSum(node.left)
            right_sum = totalSum(node.right)
            tilt = abs(right_sum - left_sum)
            self.ans += tilt
            
            return left_sum + right_sum + node.val
        totalSum(root)
        return self.ans

1446. Consecutive Characters

674. Longest Continuous Increasing Subsequence

2103        Rings and Rods        Easy

938. Range Sum of BST

还是要仔细审题的，BST 自身是有 order 的

902. Numbers At Most N Given Digit Set

题目并不难，比 n 位数小的情况很容易计算，但是与 n 位数一样的时候情况就复杂了，这个时候需要考虑的是，首位是不是一样，同时还需要一路比较到最后一个情况。

如何高效简洁地写出code，很考验功力。参考了花花的解答，https://zxi.mytechroad.com/blog/ ... -n-given-digit-set/

394         Decode String        Medium        4        Stack + Reversed Push

1200        Minimum Absolute Difference        Easy        1       

2108. Find First Palindromic String in the Array
2109. Adding Spaces to a String
2110. Number of Smooth Descent Periods of a Stock