刷题记录帖子

LC 199. Binary Tree Right Side View

1. # Definition for a binary tree node.
   
2. # class TreeNode:
   
3. #     def __init__(self, val=0, left=None, right=None):
   
4. #         self.val = val
   
5. #         self.left = left
   
6. #         self.right = right
   
7. class Solution:
   
8.     def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
   
9.         if not root: return
   
10.         queue = [root]
    
11.         level_length = 1
    
12.         ans = []
    
13. 
    
14.         while queue:
    
15.             curr = queue.pop(0)
    
16.             level_length -= 1
    
17.             if curr.left: queue.append(curr.left)
    
18.             if curr.right: queue.append(curr.right)
    
19.             if level_length == 0:
    
20.                 # the right most element
    
21.                 ans.append(curr.val)
    
22.                 level_length = len(queue)
    
23.         return ans
    
24.             
    
25. 
    
26. 
    
27. 
    
28.         

复制代码

LC 545. Boundary of Binary Tree

题目：

The boundary of a binary tree is the concatenation of the root, the left boundary, the leaves ordered from left-to-right, and the reverse order of the right boundary.

The left boundary is the set of nodes defined by the following:

The root node's left child is in the left boundary. If the root does not have a left child, then the left boundary is empty.
If a node is in the left boundary and has a left child, then the left child is in the left boundary.
If a node is in the left boundary, has no left child, but has a right child, then the right child is in the left boundary.
The leftmost leaf is not in the left boundary.
The right boundary is similar to the left boundary, except it is the right side of the root's right subtree. Again, the leaf is not part of the right boundary, and the right boundary is empty if the root does not have a right child.

The leaves are nodes that do not have any children. For this problem, the root is not a leaf.

Given the root of a binary tree, return the values of its boundary.



Example 1:


Input: root = [1,null,2,3,4]
Output: [1,3,4,2]
Explanation:
- The left boundary is empty because the root does not have a left child.
- The right boundary follows the path starting from the root's right child 2 -> 4.
  4 is a leaf, so the right boundary is [2].
- The leaves from left to right are [3,4].
Concatenating everything results in [1] + [] + [3,4] + [2] = [1,3,4,2].
Example 2:


Input: root = [1,2,3,4,5,6,null,null,null,7,8,9,10]
Output: [1,2,4,7,8,9,10,6,3]
Explanation:
- The left boundary follows the path starting from the root's left child 2 -> 4.
  4 is a leaf, so the left boundary is [2].
- The right boundary follows the path starting from the root's right child 3 -> 6 -> 10.
  10 is a leaf, so the right boundary is [3,6], and in reverse order is [6,3].
- The leaves from left to right are [4,7,8,9,10].
Concatenating everything results in [1] + [2] + [4,7,8,9,10] + [6,3] = [1,2,4,7,8,9,10,6,3].


Constraints:

The number of nodes in the tree is in the range [1, 104].
-1000 <= Node.val <= 1000

解法

思路一句话再确认
root
→ 左外壳（不加叶子）
→ 所有叶子
→ 右外壳（不加叶子，反着）

特别注意， 这就是只在 left 不存在的时候才看 right，而不是 另一个 if right 存在就加 right。

1. if curr.left: curr = curr.left
   
2.             else: curr =curr.right

复制代码

1. # Definition for a binary tree node.
   
2. # class TreeNode:
   
3. #     def __init__(self, val=0, left=None, right=None):
   
4. #         self.val = val
   
5. #         self.left = left
   
6. #         self.right = right
   
7. class Solution:
   
8.     def boundaryOfBinaryTree(self, root: Optional[TreeNode]) -> List[int]:
   
9.         """
   
10.         adding
    
11.         (1) root
    
12.         (2) left path no leaves
    
13.         (3) all leaves
    
14.         (4) right path no leaves
    
15. 
    
16.         """
    
17.         if not root: return
    
18.         ans = []
    
19.         # add root
    
20.         ans.append(root.val)
    
21.         def is_leaves(node):
    
22.             return node and not node.left and not node.right
    
23.         # add left path
    
24.         curr = root.left
    
25.         while curr:
    
26.             if not is_leaves(curr):
    
27.                 ans.append(curr.val)
    
28.             if curr.left: curr = curr.left
    
29.             else: curr =curr.right
    
30.         # add levaes
    
31.         def add_leaves(node):
    
32.             if not node: return
    
33.             if is_leaves(node) and node != root:
    
34.                 ans.append(node.val)
    
35.             add_leaves(node.left)
    
36.             add_leaves(node.right)
    
37.         add_leaves(root)
    
38.         # add right path
    
39.         stack = []
    
40.         curr = root.right
    
41.         while curr:
    
42.             if not is_leaves(curr):
    
43.                 stack.append(curr.val)
    
44.             if curr.right: curr = curr.right
    
45.             else: curr = curr.left
    
46.         while stack:
    
47.             ans.append(stack.pop())
    
48.         return ans        
    
49.    
    
50. 
    
51. 
    
52.         

复制代码

215. Kth Largest Element in an Array

面试一句话解释模板（非常重要）

“我用一个大小为 k 的最小堆，遍历数组时维护当前最大的 k 个数，最后堆顶就是第 k 大，时间复杂度是 O(n log k)，不需要排序整个数组。”

1. class Solution:
   
2.     def findKthLargest(self, nums: List[int], k: int) -> int:
   
3.         heap = []
   
4. 
   
5.         for num in nums:
   
6.             heapq.heappush(heap, num)
   
7.             if len(heap) > k:
   
8.                 heapq.heappop(heap)
   
9.         
   
10.         return heap[0]

复制代码

复杂度

时间：O(n log k)

空间：O(k)

另外一种解法，quickSort way

核心想法

每次选一个 pivot，把数组分成：

> pivot | pivot | < pivot


然后：

如果 pivot 正好是第 k 大 → 返回

否则只递归 一边

👉 不需要完全排好序

为什么比排序快？

排序：左右都递归 → O(n log n)

Quickselect：只递归一边 → 平均 O(n)

1. import random
   
2. 
   
3. class Solution:
   
4.     def findKthLargest(self, nums, k):
   
5.         k = len(nums) - k  # 转成第 k 小
   
6. 
   
7.         def quickselect(l, r):
   
8.             pivot = nums[random.randint(l, r)]
   
9.             i, j = l, r
   
10.             while i <= j:
    
11.                 while nums[i] < pivot:
    
12.                     i += 1
    
13.                 while nums[j] > pivot:
    
14.                     j -= 1
    
15.                 if i <= j:
    
16.                     nums[i], nums[j] = nums[j], nums[i]
    
17.                     i += 1
    
18.                     j -= 1
    
19. 
    
20.             if k <= j:
    
21.                 return quickselect(l, j)
    
22.             if k >= i:
    
23.                 return quickselect(i, r)
    
24.             return nums[k]
    
25. 
    
26.         return quickselect(0, len(nums) - 1)
    

复制代码

我们来 逐行拆解这个 Quickselect 函数，我保证你理解每一步在干什么。

1️⃣ 函数定义
def quickselect(l, r):


l、r：当前正在处理的数组范围 [l, r]

我们要在这个范围里找 第 k 小元素（注意，外面调用时已经把第 k 大转成第 k 小了：k = len(nums) - k）

2️⃣ 选 pivot（随机化）
pivot = nums[random.randint(l, r)]


在 [l, r] 范围随机选一个数作为 pivot

随机化可以避免最坏情况 O(n²)

pivot 的作用：把数组分成 小于 pivot / 大于 pivot / 等于 pivot

3️⃣ 初始化双指针
i, j = l, r


i 从左往右走

j 从右往左走

双指针用来 partition（把小的放左边，大的放右边）

4️⃣ Partition 循环
while i <= j:
    while nums[i] < pivot:
        i += 1
    while nums[j] > pivot:
        j -= 1
    if i <= j:
        nums[i], nums[j] = nums[j], nums[i]
        i += 1
        j -= 1

拆解：

while nums[i] < pivot: i += 1

找到左边 第一个 ≥ pivot 的元素

while nums[j] > pivot: j -= 1

找到右边 第一个 ≤ pivot 的元素

if i <= j:

如果 i <= j，说明这两个元素需要交换，让小的在左，大的在右

交换完，指针各自移动一位

循环直到 i > j

i、j 分开

左边全 ≤ pivot，右边全 ≥ pivot（pivot 在中间）

5️⃣ 递归选择
if k <= j:
    return quickselect(l, j)
if k >= i:
    return quickselect(i, r)
return nums[k]


解释：

k：我们要找的第 k 小元素的索引

Partition 完成后：

[l..j]：全部 ≤ pivot

[i..r]：全部 ≥ pivot

三种情况：

k <= j

第 k 小在 左半边

递归 quickselect(l, j)

k >= i

第 k 小在 右半边

递归 quickselect(i, r)

否则：

第 k 小就在 pivot 中间（i > k > j）

直接返回 nums[k]

🔑 核心理解

Quickselect = 快速找第 k 小，而不完全排序

Partition 就像快速排序的一步

每次递归只处理 可能存在答案的那一半 → 平均 O(n)

随机 pivot 避免了最坏情况（完全倒序）

LC 680. Valid Palindrome II

好的，我帮你把这道 **“Valid Palindrome II”** 的核心点总结成 **面试/分享可用的精华要点**，清晰易懂：

---

## **Valid Palindrome II 核心要点总结**

### 1️⃣ 问题本质

* 给定字符串 `s`，允许 **删除最多一个字符**，判断是否可以变成回文。
* 回文判断 = **双指针左右扫描**。

---

### 2️⃣ 核心思路

1. 用 **双指针 `left`、`right`** 从两端扫描：

   * 相等 → 指针靠近
   * 不等 → **第一次遇到 mismatch**
2. 当遇到 mismatch：

   * **尝试删除左边字符** → 检查剩余子串是否回文
   * **尝试删除右边字符** → 检查剩余子串是否回文
   * **只要一种成功 → True**
3. **两边都不成立 → False**

> 核心技巧：**删除左/右尝试必须独立**，不能直接移动指针去假设成功。

---

### 3️⃣ 为什么不能简单移动指针

* 原来的做法：`if left+1==right` / `elif right-1==left`
* 问题：

  1. **短路了另一种可能**（if/elif）
  2. **删除后没有验证剩余子串是否回文**
* 结果：某些中间复杂情况会返回错误。

---

### 4️⃣ 时间/空间复杂度

* **时间复杂度**：O(n)

  * 每个字符最多访问两次（主循环 + 删除尝试）
* **空间复杂度**：O(1)

  * 只用常量指针，不开递归/额外数组

---

### 5️⃣ 面试可讲的模板语言

> “我用双指针扫描字符串，遇到第一次不匹配时，尝试删除左边或右边字符，验证剩余子串是否回文。只要一种可行，就返回 True。每个字符最多访问两次，时间复杂度 O(n)，空间复杂度 O(1)。”

---

### 6️⃣ 核心实现技巧

* 双指针扫描 → O(n)
* 删除尝试 → 局部循环验证子串
* 删除左/右尝试 **必须独立**，不要修改原始指针
* **无需额外函数或递归**，更面试友好

1. class Solution:
   
2.     def validPalindrome(self, s: str) -> bool:
   
3.         left, right = 0, len(s) - 1
   
4. 
   
5.         while left < right:
   
6.             if s[left] == s[right]:
   
7.                 left += 1
   
8.                 right -= 1
   
9.             else:
   
10.                 # 尝试删除左边
    
11.                 l, r = left + 1, right
    
12.                 good_left = True
    
13.                 while l < r:
    
14.                     if s[l] != s[r]:
    
15.                         good_left = False
    
16.                         break
    
17.                     l += 1
    
18.                     r -= 1
    
19. 
    
20.                 # 尝试删除右边
    
21.                 l, r = left, right - 1
    
22.                 good_right = True
    
23.                 while l < r:
    
24.                     if s[l] != s[r]:
    
25.                         good_right = False
    
26.                         break
    
27.                     l += 1
    
28.                     r -= 1
    
29. 
    
30.                 return good_left or good_right
    
31. 
    
32.         return True

复制代码

LC 2965. Find Missing and Repeated Values

1. class Solution:
   
2.     def findMissingAndRepeatedValues(self, grid: List[List[int]]) -> List[int]:
   
3.         freq = defaultdict(int)
   
4.         ans = [-1, -1]
   
5.         for i in range(len(grid)):
   
6.             for j in range(len(grid[0])):
   
7.                 freq[ grid[i][j] ] += 1
   
8.                 if freq[ grid[i][j] ] == 2: ans[0] = grid[i][j]
   
9.         for i in range(len(grid)**2):
   
10.             if i+1 not in freq: ans[1] = i + 1
    
11. 
    
12.         return ans

复制代码

也可以用数学公式做，我记得做过类似的，还是 sum 和 sum^2，利用 x-y and x^2-y^2 的数学公式计算。

Approach 2: Math
Intuition
At first glance, this problem might seem to require tracking frequencies, but there's a more elegant mathematical approach. In a perfect sequence from 1 to n
2
, every number appears exactly once. However, in our given sequence, one number appears twice, and another number is missing. Let’s define the repeated number as x and the missing number as y.

Instead of explicitly counting occurrences, we can leverage basic mathematical properties of numbers. The sum of all numbers in a proper sequence from 1 to n
2
  can be computed using the formula:

perfectSum=
2
n
2
⋅(n
2
+1)
​

​

Similarly, the sum of the squares of these numbers follows this formula:

perfectSqrSum=
6
n
2
⋅(n
2
+1)⋅(2n
2
+1)
​

​

Now, if we compute the sum of numbers in our given grid (sum) and compare it with perfectSum, we can express their relationship as:

sum=perfectSum+x−y
​

This tells us that the difference between the actual sum and the perfect sum gives us:

sumDiff=x−y
​

Similarly, if we compute the sum of squares from our grid (sqrSum) and compare it with perfectSqrSum, we get:

sqrDiff=x
2
−y
2

​

Now, we recall a fundamental algebraic identity:

x
2
−y
2
=(x+y)⋅(x−y)
​

Since we already know x−y from sumDiff, we can substitute it into the equation:

sqrDiff=(x+y)⋅sumDiff
​

Rearranging this equation, we can solve for x+y:

x+y=
sumDiff
sqrDiff
​

​

Now, we have two simple equations:

x−y=sumDiff
​

x+y=
sumDiff
sqrDiff
​

​

Solving for x and y:

x=
2
sqrDiff/sumDiff+sumDiff
​

​

y=
2
sqrDiff/sumDiff−sumDiff
​

​

This mathematical derivation translates directly into our code. We first calculate the actual sums from our grid and then compute the perfect sums using the formulas. The differences between these give us sumDiff and squareDifference, which we can plug into our final formulas to get the repeating and missing numbers.

Note: One important implementation detail is the use of long instead of int for our calculations. This is crucial because when we're dealing with squares of numbers, we can easily exceed the integer range.

Algorithm
Initialize variables:
sum and sqrSum to 0 to store the actual sums from the grid.
n to store the length of the grid.
Initialize a variable total to n * n to store the total number of elements.
For each row in the grid:
For each col in the grid:
Add the current element to sum.
Add the square of the current element to sqrSum.
Calculate the sumDiff by subtracting the expected sum (total * (total + 1) / 2) from the actual sum.
Calculate the sqrDiff by subtracting the expected square sum (total * (total + 1) * (2 * total + 1) / 6) from the actual sqrSum.
Calculate repeat using the formula (sqrDiff / sumDiff + sumDiff) / 2.
Calculate missing using the formula (sqrDiff / sumDiff - sumDiff) / 2.
Return an array containing repeat and missing numbers.
Implementation

Complexity Analysis
Let n be the side length of the grid.

Time complexity: O(n
2
)

The algorithm iterates through each cell in the n×n grid exactly once using two nested loops. All other operations (calculating sums, differences, and the final values) are constant time operations. Therefore, the total time complexity is O(n
2
).

Space complexity: O(1)

The algorithm only uses a constant amount of extra space to store variables (sum, sqrSum, n, total, sumDiff, sqrDiff) regardless of the input size. Therefore, the space complexity is O(1).

1. class Solution:
   
2.     def findMissingAndRepeatedValues(self, grid: List[List[int]]) -> List[int]:
   
3.         # Get grid dimensions
   
4.         n = len(grid)
   
5.         total = n * n
   
6. 
   
7.         # Calculate actual sums from grid
   
8.         sum_val = sum(num for row in grid for num in row)
   
9.         sqr_sum = sum(num * num for row in grid for num in row)
   
10. 
    
11.         # Calculate differences from expected sums
    
12.         # Expected sum: n(n+1)/2, Expected square sum: n(n+1)(2n+1)/6
    
13.         sum_diff = sum_val - total * (total + 1) // 2
    
14.         sqr_diff = sqr_sum - total * (total + 1) * (2 * total + 1) // 6
    
15. 
    
16.         # Using math: If x is repeated and y is missing
    
17.         # sum_diff = x - y
    
18.         # sqr_diff = x² - y²
    
19.         repeat = (sqr_diff // sum_diff + sum_diff) // 2
    
20.         missing = (sqr_diff // sum_diff - sum_diff) // 2
    
21. 
    
22.         return [repeat, missing]

复制代码

LC 3010. Divide an Array Into Subarrays With Minimum Cost I

Using Heap to save the minimum 2 values of an array

1. class Solution:
   
2.     def minimumCost(self, nums: List[int]) -> int:
   
3.         # nums[0] must in answers
   
4.         ans = nums[0]
   
5.         # divide into 3 disjoint contiguous subarrays means
   
6.         # find i, j between 1 ~ n-1
   
7.         # sum is the smallest
   
8.         # using heap
   
9.         heap = []
   
10.         for num in nums[1:]:
    
11.             heapq.heappush(heap, num)
    
12.         ans += heapq.heappop(heap)
    
13.         ans += heapq.heappop(heap)
    
14.         return ans
    
15.         

复制代码

LC

1. SELECT
   
2.     (SELECT DISTINCT
   
3.             Salary
   
4.         FROM
   
5.             Employee
   
6.         ORDER BY Salary DESC
   
7.         LIMIT 1 OFFSET 1) AS SecondHighestSalary
   
8. ;

复制代码

1. import pandas as pd
   
2. 
   
3. def second_highest_salary(employee: pd.DataFrame) -> pd.DataFrame:
   
4.     # 1. drop any duplicate salaries.
   
5.     employee = employee.drop_duplicates(["salary"])
   
6.    
   
7.     # 2. If there are less than two unique salaries, return `np.NaN`.
   
8.     if len(employee["salary"].unique()) < 2:
   
9.         return pd.DataFrame({"SecondHighestSalary": [np.NaN]})
   
10.    
    
11.     # 3. Sort the table by `salary` in descending order.
    
12.     employee = employee.sort_values("salary", ascending=False)
    
13.    
    
14.     # 4. Drop the `id` column.
    
15.     employee.drop("id", axis=1, inplace=True)
    
16.    
    
17.     # 5. Rename the `salary` column.
    
18.     employee.rename({"salary": "SecondHighestSalary"}, axis=1, inplace=True)
    
19.    
    
20.     # 6, 7. Return the second highest salary.
    
21.     return employee.head(2).tail(1)

复制代码

LC 73. Set Matrix Zeroes

1. class Solution:
   
2.     def setZeroes(self, matrix: List[List[int]]) -> None:
   
3.         """
   
4.         Do not return anything, modify matrix in-place instead.
   
5.         """
   
6.         n_rows = len(matrix)
   
7.         n_cols = len(matrix[0])
   
8.         visited = set()
   
9. 
   
10.         for i in range(n_rows):
    
11.             for j in range(n_cols):
    
12.                 if (i,j) not in visited:
    
13.                     if matrix[i][j] == 0:
    
14.                         # set row to zero
    
15.                         r, c = i, j
    
16.                         while r-1>= 0:
    
17.                             if (r-1, c) not in visited:
    
18.                                 if matrix[r-1][c] != 0:
    
19.                                     matrix[r-1][c] = 0
    
20.                                     visited.add((r-1, c))
    
21.                             r -= 1
    
22.                         r, c = i, j
    
23.                         while r+1 < n_rows:
    
24.                             if (r+1, c) not in visited:
    
25.                                 if matrix[r+1][c] != 0:
    
26.                                     matrix[r+1][c] = 0
    
27.                                     visited.add((r+1, c))
    
28.                             r += 1
    
29.                         # set cols to zero
    
30.                         r, c = i, j
    
31.                         while c-1 >= 0:
    
32.                             if (r, c-1) not in visited:
    
33.                                 if matrix[r][c-1] != 0:
    
34.                                     matrix[r][c-1] = 0
    
35.                                     visited.add((r, c-1))
    
36.                             c -= 1
    
37.                         r, c = i, j
    
38.                         while c+1 < n_cols:
    
39.                             if (r, c+1) not in visited:
    
40.                                 if matrix[r][c+1] != 0:
    
41.                                     matrix[r][c+1] = 0
    
42.                                     visited.add((r, c+1))
    
43.                             c += 1                        

复制代码

可以用所有行的第一列，和所有列的第一行来标记，如果右下方矩阵有 0， 那可以用来标记

LC 55. Jump Game

最远的 cell 只需要考虑 farthest cell 可以 reach。在每一个新的 i 判断，之前 cell 的最远 farthest 是不是可以到达这个 index。

1. class Solution:
   
2.     def canJump(self, nums: List[int]) -> bool:
   
3.         n = len(nums)
   
4.         farthest = 0
   
5. 
   
6.         for i in range(n):
   
7.             if i > farthest: return False
   
8.             farthest = max(farthest, i+nums[i])
   
9.         return True
   
10.             
    
11.         

复制代码

LC 45. Jump Game II

Jump Game II 的贪心不是选择某个点跳，
而是选择 一整层区间，
在这层区间里找能让下一层最远的扩展

1. class Solution:
   
2.     def jump(self, nums: List[int]) -> int:
   
3.         # Greedy
   
4.         """
   
5.         for each i
   
6.             farthest: farthest index we can reach with one more jump from anywhere inside the current boundary, i to end
   
7.             end: the farthest index we can reach using the current number of jumps
   
8.         """
   
9.         n = len(nums)
   
10.         farthest = 0
    
11.         jumps = 0
    
12.         end = 0
    
13. 
    
14.         for i in range(n-1):
    
15.             farthest = max(farthest, i + nums[i])
    
16. 
    
17.             if i == end:
    
18.                 jumps += 1
    
19.                 # We only update end when i == end because that is the moment we have
    
20.                 # finished considering all possible positions reachable with the current number of jumps.
    
21.                 end = farthest
    
22.         return jumps
    
23.         

复制代码