刷题记录帖子

LC 1022. Sum of Root To Leaf Binary Numbers

这道题目做过但是我还是犯错了，还是需要保持手感刷题。

首先是 DFS，带着 path 的正统 DFS。

注意

判断是否结束，不结束进场，操作返回，递归，回溯

1. class Solution:
   
2.     def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:
   
3.         ans = 0  # 最终结果
   
4. 
   
5.         def dfs(node, path):
   
6.             nonlocal ans  # 必须声明，否则内部无法修改外部变量
   
7.             
   
8.             if not node:
   
9.                 return
   
10. 
    
11.             # 1. 进场：先把当前节点值放入路径
    
12.             path.append(node.val)
    
13. 
    
14.             # 2. 判断是否为叶子节点
    
15.             if not node.left and not node.right:
    
16.                 # 将 [1, 0, 1] 这种列表转为字符串 "101"，再转为 2 进制整数
    
17.                 bstring = "".join(map(str, path))
    
18.                 ans += int(bstring, 2)
    
19.             else:
    
20.                 # 3. 递归：分别走左右子树
    
21.                 if node.left:
    
22.                     dfs(node.left, path)
    
23.                 if node.right:
    
24.                     dfs(node.right, path)
    
25. 
    
26.             # 4. 离场：回溯，弹出当前节点值，保证不影响父节点的其他分支
    
27.             path.pop()
    
28. 
    
29.         dfs(root, [])
    
30.         return ans

复制代码

第二个解法，不需要 path， 因为二进制而且需要的是和，不是具体的各条路径。

之前的路径和 x 2 + 当前节点值就是当前路径和。

1. class Solution:
   
2.     def sumRootToLeaf(self, root: TreeNode) -> int:
   
3.         self.res = 0
   
4.         self.DFS(root, 0)
   
5.         return self.res
   
6.    
   
7.     def DFS(self, node, curr_sum):
   
8.         if not node:
   
9.             return
   
10. 
    
11.         # 计算当前路径到达当前节点时的数值
    
12.         # (curr_sum << 1) | node.val 也是一样的效果
    
13.         current = curr_sum * 2 + node.val
    
14. 
    
15.         # 如果是叶子节点，累加结果并直接返回，不再向下递归
    
16.         if not node.left and not node.right:
    
17.             self.res += current
    
18.             return
    
19.             
    
20.         # 如果不是叶子节点，继续向下探索
    
21.         self.DFS(node.left, current)
    
22.         self.DFS(node.right, current)

复制代码

第三种解法，完全递归型。注意，这里就必须要返回 0 或者具体的值了，因为你不是用 self.res 全局变量来计算。

1. def sumRootToLeaf(self, root: TreeNode) -> int:
   
2.     return self.DFS(root, 0)
   
3. 
   
4. def DFS(self, node, curr_sum):
   
5.     if not node: return 0 # 必须返回0，否则相加会报错 (None + int)
   
6.    
   
7.     current = curr_sum * 2 + node.val
   
8.    
   
9.     if not node.left and not node.right:
   
10.         return current # 叶子节点返回自己的值
    
11.    
    
12.     # 结果 = 左子树的路径和 + 右子树的路径和
    
13.     return self.DFS(node.left, current) + self.DFS(node.right, current)

复制代码

LC。 1356. Sort Integers by The Number of 1 Bits

1. class Solution:
   
2.     def sortByBits(self, arr: List[int]) -> List[int]:
   
3.         ans = []
   
4.         for num in arr:
   
5.             bin_num = bin(num)[2:]
   
6.             freq = Counter(bin_num)
   
7.             ans.append((freq['1'], num))
   
8.         ans.sort()
   
9. 
   
10.         return [x[1] for x in ans]
    
11.         

复制代码

更加 Python 的代码

1. class Solution:
   
2.     def sortByBits(self, arr: List[int]) -> List[int]:
   
3.         return sorted(arr, key=lambda x: (x.bit_count(), x))

复制代码

Python 的 int.bin_count() 用了 CPU 的指令，会更快！

LC.461. Hamming Distance

函数调用的优先级 > 位运算

1. class Solution:
   
2.     def hammingDistance(self, x: int, y: int) -> int:
   
3.         return (x^y).bit_count()

复制代码

LC 2220. Minimum Bit Flips to Convert Number

the minimum number of bit flips to convert start to goal. 其实就是 bit 位有多少位不一样，类似 Hammning Distance。

1. class Solution:
   
2.     def minBitFlips(self, start: int, goal: int) -> int:
   
3.         return (start ^ goal).bit_count()
   
4.         

复制代码

LC. 191. Number of 1 Bits

OR. int.bit_count()

Brian Kernighan 算法

1. class Solution:
   
2.     def hammingWeight(self, n: int) -> int:
   
3.         count = 0
   
4.         while n:
   
5.             n &= (n-1)
   
6.             count += 1
   
7.         return count

复制代码

补充内容 (2026-02-25 10:58 +08:00):
Brian Kernighan 算法为什么是 O(1 的个数)，我们一步一步拆开讲。


一、算法本身
经典写法：
count = 0
while x:
    x &= x - 1
    count += 1核心语句只有一行：
x &= x - 1

二、关键性质

1. x & (x - 1)

复制代码

会删除 x 的最低位 1

这是整个算法的核心。


三、为什么能删除最低位 1？
举例：
假设：
x =  1011000先算：
x - 1 = 1010111观察变化：

• 最低位的 1 变成 0
• 它右边的 0 全变成 1

然后做 AND：
  1011000
& 1010111
---------
  1010000最低位的 1 被消掉了。


四、每次循环发生什么？
每执行一次：
x &= x - 1就会：

删除一个 1

不会删除 0
不会多删
只删一个


五、所以循环次数等于什么？
等于：

x 中 1 的个数

设：

• 二进制长度 = k
• 1 的个数 = m

则：

方法	时间复杂度
逐位右移	O(k)
Kernighan	O(m)

六、为什么这是巨大优化？
举例：
x = 10000000000000000000000000000000只有 1 个 1。

• 普通遍历 → 32 次
• Kernighan → 1 次

再看：
x = 11111111111111111111111111111111有 32 个 1。

• 普通遍历 → 32 次
• Kernighan → 32 次

最坏情况一样
但平均情况更快


七、为什么说是 O(1 的个数)？
因为循环条件是：
while x:而 x 每次都会少一个 1。
假设：
m = bit_count(x)那么循环精确执行：
m 次所以时间复杂度：
O(m)

八、数学理解
把整数看作：
x = sum(2^pi)每次操作：
x ← x - lowest_power_of_2也就是：
x ← x - 2^k每次消去一个 2 的幂项。


九、对比 popcount 指令
现代 CPU：
POPCNT一次硬件指令完成统计。
但在没有硬件支持时：

Kernighan 是最优软件实现之一

十、为什么它比逐位右移快？
普通做法：
while x:
    count += x & 1
    x >>= 1循环次数 = 位数 k
Kernighan：
循环次数 = 1 的个数 m
如果 m ≪ k：
巨大优化。


十一、复杂度总结
设：

• k = 二进制位数
• m = 1 的个数

方法	复杂度
逐位检查	O(k)
Kernighan	O(m)
CPU popcount	O(1)（硬件级）

十二、面试深度理解点
如果面试官问：

为什么 x & (x-1) 能删除最低位 1？

你可以回答：
因为：

• x-1 会把最低位 1 变成 0
• 并把其右侧 0 全部变成 1
• AND 运算会清除那一位

这说明你真正理解了。

补充内容 (2026-02-25 11:00 +08:00):
八、和 Kernighan 算法的关系
Kernighan：
x &= x - 1是：

删除最低位 1

而：
x & -x

LC. 338. Counting Bits

1. class Solution:
   
2.     def countBits(self, n: int) -> List[int]:
   
3.         ans = []
   
4.         for x in range(n+1):
   
5.             ans.append(x.bit_count())
   
6.         return ans
   
7.         

复制代码

LC 1404. Number of Steps to Reduce a Number in Binary Representation to One

Python 解法直接模拟，但是这个不是面试官想要的。。。

1. class Solution:
   
2.     def numSteps(self, s: str) -> int:
   
3.         n = int(s, 2)
   
4.         count = 0
   
5.         while n != 1:
   
6.             if n % 2 == 0:
   
7.                 n = n//2
   
8.             else:
   
9.                 n += 1
   
10.             count += 1
    
11.         return count

复制代码

面试想考察的是位运算的理解，对于二进制，除 2 ，就是右移一位，去掉最右那个0；加 1，其实就是最右 1 + 1 变成 偶数，这个时候，因为我们不想再处理，所以必须 +2，这包含了 +1 变 偶数，再除以2，去掉这位的两步。

在二进制下，我们要处理的位（bit）只有 0 或 1。当我们从右往左（从低位到高位）遍历时，目标是把每一位都通过操作“抵消”掉，直到剩下最左边的 1。

1. 为什么是 +2 步？
当我们遇到一个奇数位（当前位是 1，或者因为进位变成了 1）时，根据规则：

第一步（加 1）： 奇数 + 1 变成偶数。在二进制里，这一位从 1 变成 0，并向高位产生一个进位（Carry）。

第二步（除以 2）： 偶数除以 2。在二进制里，这相当于向右移位，也就是把末尾那个刚刚生成的 0 删掉。

总结：
为了“处理掉”这个 1 并移动到下一位，你必须先把它变成 0（步数+1），然后再把它移走（步数+1）。所以总共是 2 步。

从后往前遍历字符串，模拟这个过程。

核心逻辑：
从右往左看：

如果当前位是 0 且没有进位，直接右移（操作数 +1）。

如果当前位是 1，说明是奇数，需要加 1（变偶数再右移，共操作 +2）。

进位状态（Carry）：一旦我们遇到一个 1（奇数），我们就必须执行加法，这会产生一个持续的“进位”，直到字符串结束。

1. class Solution:
   
2.     def numSteps(self, s: str) -> int:
   
3.         steps = 0
   
4.         carry = 0
   
5.         
   
6.         # 从右向左遍历，不处理最左边的第一位 s[0]
   
7.         # 因为最终目标是让数字变成 1（即二进制的 "1"）
   
8.         for i in range(len(s) - 1, 0, -1):
   
9.             # 当前位的值 = 字符值 + 进位
   
10.             current_val = int(s[i]) + carry
    
11.             
    
12.             if current_val == 1:
    
13.                 # 情况 A: 1 + 0 (奇数) 或 0 + 1 (奇数)
    
14.                 # 奇数需要：加 1 (step+1) 再除以 2 (step+1)，并产生进位
    
15.                 steps += 2
    
16.                 carry = 1
    
17.             elif current_val == 0:
    
18.                 # 情况 B: 0 + 0 (偶数)
    
19.                 # 直接除以 2 (step+1)
    
20.                 steps += 1
    
21.                 carry = 0
    
22.             elif current_val == 2:
    
23.                 # 情况 C: 1 + 1 (偶数，但由于进位变成了 2)
    
24.                 # 已经是偶数，直接除以 2 (step+1)，进位保持 1
    
25.                 steps += 1
    
26.                 carry = 1
    
27.                
    
28.         # 最后处理最左边的位 s[0] 和最后的进位 carry
    
29.         # 如果有进位，说明 "1" 变成了 "10"，需要额外一步除法变回 "1"
    
30.         return steps + carry

复制代码

为什么 current_val == 2 时只增加 1 步，我们需要回归到二进制加法的本质。1. 场景还原假设我们处理到字符串的某一位，原字符是 '1'，而前一位计算后传过来的进位 carry 也是 1。此时：current_val = 1 (原本位) + 1 (进位) = 2。在二进制中，数字 2 写作 10。2. 为什么只加 1 步？根据题目规则：判定奇偶： 二进制的 10 末尾是 0，所以它是偶数。执行操作： 偶数必须除以 2。结果： 10 除以 2 变成 1。动作分解：我们只做了一个动作：右移一位（除以 2）。所以 steps += 1。虽然这一位被移走了，但由于 1 + 1 产生了进位，这个 1 会被传递到更高的一位去。所以 carry 依然保持为 1。3. 直观对比：情况 A vs 情况 C我们可以把“这一位加上进位后的结果”看作一个临时的二进制数：情况current_val (十进制)二进制表现奇偶性对应操作步数变化下一轮进位情况 A101奇数+1 (变 10) 再 /2+2carry = 1情况 C210偶数直接 /2+1carry = 14. 深度思考：为什么不加 1？你可能会想：“它不是变成 2 了吗？不需要先加 1 吗？”不需要。 规则是根据“当前数值”来定的。如果是 1（奇数），规则强制你先 +1 变成 2（即 10），再 /2 变成 1。这费了 2 步。如果是 2（即 10），它本身就是偶数，规则强制你直接 /2 变成 1。这只费 1 步。总结在 current_val == 2 的情况下，进位 carry 实际上帮你完成了“变成偶数”的任务，你只需要负责“除以 2”这一步动作即可。

LC. 2000. Reverse Prefix of Word

1. class Solution:
   
2.     def reversePrefix(self, word: str, ch: str) -> str:
   
3.         stack = []
   
4.         for i, char in enumerate(word):
   
5.             stack.append(char)
   
6.             if char == ch:
   
7.                 # 找到目标，开始反转并拼接
   
8.                 # "".join(stack[::-1]) 快速将栈内元素反转并转为字符串
   
9.                 return "".join(stack[::-1]) + word[i+1:]
   
10.         
    
11.         # 循环结束还没 return，说明没找到
    
12.         return word

复制代码

LC 2004. The Number of Seniors and Juniors to Join the Company
Hard

+-------------+------+
| Column Name | Type |
+-------------+------+
| employee_id | int  |
| experience  | enum |
| salary      | int  |
+-------------+------+
employee_id is the column with unique values for this table.
experience is an ENUM (category) type of values ('Senior', 'Junior').
Each row of this table indicates the id of a candidate, their monthly salary, and their experience.


A company wants to hire new employees. The budget of the company for the salaries is $70000. The company's criteria for hiring are:

Hiring the largest number of seniors.
After hiring the maximum number of seniors, use the remaining budget to hire the largest number of juniors.
Write a solution to find the number of seniors and juniors hired under the mentioned criteria.

Return the result table in any order.

The result format is in the following example.



Example 1:

Input:
Candidates table:
+-------------+------------+--------+
| employee_id | experience | salary |
+-------------+------------+--------+
| 1           | Junior     | 10000  |
| 9           | Junior     | 10000  |
| 2           | Senior     | 20000  |
| 11          | Senior     | 20000  |
| 13          | Senior     | 50000  |
| 4           | Junior     | 40000  |
+-------------+------------+--------+
Output:
+------------+---------------------+
| experience | accepted_candidates |
+------------+---------------------+
| Senior     | 2                   |
| Junior     | 2                   |
+------------+---------------------+
Explanation:
We can hire 2 seniors with IDs (2, 11). Since the budget is $70000 and the sum of their salaries is $40000, we still have $30000 but they are not enough to hire the senior candidate with ID 13.
We can hire 2 juniors with IDs (1, 9). Since the remaining budget is $30000 and the sum of their salaries is $20000, we still have $10000 but they are not enough to hire the junior candidate with ID 4.
Example 2:

Input:
Candidates table:
+-------------+------------+--------+
| employee_id | experience | salary |
+-------------+------------+--------+
| 1           | Junior     | 10000  |
| 9           | Junior     | 10000  |
| 2           | Senior     | 80000  |
| 11          | Senior     | 80000  |
| 13          | Senior     | 80000  |
| 4           | Junior     | 40000  |
+-------------+------------+--------+
Output:
+------------+---------------------+
| experience | accepted_candidates |
+------------+---------------------+
| Senior     | 0                   |
| Junior     | 3                   |
+------------+---------------------+
Explanation:
We cannot hire any seniors with the current budget as we need at least $80000 to hire one senior.
We can hire all three juniors with the remaining budget.

1. # Write your MySQL query statement below
   
2. # 1. 计算每个员工在其分组内（Senior/Junior）按薪水升序的累积薪水
   
3. WITH RunningSalary AS (
   
4.     SELECT
   
5.         employee_id,
   
6.         experience,
   
7.         salary,
   
8.         SUM(salary) OVER(PARTITION BY experience ORDER BY salary, employee_id) AS cum_sum
   
9.     FROM Candidates
   
10. ),
    
11. 
    
12. # 2. 找出能入职的 Senior
    
13. SeniorsHired AS (
    
14.     SELECT * FROM RunningSalary
    
15.     WHERE experience = 'Senior' AND cum_sum <= 70000
    
16. ),
    
17. 
    
18. # 3. 计算招完 Senior 后剩下的钱 (注意如果没有 Senior 能入职，剩余还是 70000)
    
19. LeftoverBudget AS (
    
20.     SELECT 70000 - IFNULL(MAX(cum_sum), 0) AS budget
    
21.     FROM SeniorsHired
    
22. ),
    
23. 
    
24. # 4. 找出能入职的 Junior
    
25. JuniorsHired AS (
    
26.     SELECT *
    
27.     FROM RunningSalary
    
28.     WHERE experience = 'Junior'
    
29.     AND cum_sum <= (SELECT budget FROM LeftoverBudget)
    
30. )
    
31. 
    
32. # 5. 汇总结果，UNION 保证没有人的分类也会出现 0
    
33. SELECT 'Senior' AS experience, COUNT(*) AS accepted_candidates FROM SeniorsHired
    
34. UNION ALL
    
35. SELECT 'Junior' AS experience, COUNT(*) AS accepted_candidates FROM JuniorsHired;

复制代码

4. 关键技术点解析
SUM(salary) OVER(PARTITION BY ... ORDER BY ...)：
这是 SQL 里的“神技”。它不是简单的求和，而是按顺序累加。通过 PARTITION BY experience，我们将 Senior 和 Junior 的账本分开算；通过 ORDER BY salary，我们确保是先算便宜的员工，实现贪心策略。

IFNULL(MAX(cum_sum), 0)：
计算已入职 Senior 的总花费时，如果没有一个 Senior 能入职，MAX(cum_sum) 会返回 NULL。用 IFNULL 把它变成 0，确保 Junior 还能拿到 70,000 的完整预算。

UNION ALL：
题目要求输出结果表包含 Senior 和 Junior 两个固定行。即便某个类别的 COUNT 为 0，这种写法也能确保它出现在结果中。

2006. Count Number of Pairs With Absolute Difference K

要想到 这是 Two Sum 的变体！

为什么只看 $x + k$ 就能避免重复？在暴力解法中，我们会纠结 $i < j$ 的索引顺序。但在统计频率后，我们只需要保证不重复统计同一对数字。如果我们遍历每一个存在的数字 $x$：如果我们既看 $x + k$ 又看 $x - k$，那么当你处理数字 2 时，你会找到 3（$2+1$）；等你处理到数字 3 时，你又会回头找到 2（$3-1$）。这一对就被算了两遍。如果我们约定只往大了找（即只找 $x + k$），那么 2 和 3 这对组合，只会在我们遍历到 2 的时候被计算一次。

总结一下暴力法：你是考官，让学生们站成一排，一个一个去比身高。哈希表法（前一解法）：你让学生一个一个进教室，进门时看一眼本子上有没有匹配的人。频率统计法（本解法）：你让学生先按身高排队集合，身高 $160$ 的站一块，身高 $165$ 的站一块，然后直接把两拨人的人数相乘。

1. from collections import Counter
   
2. 
   
3. class Solution:
   
4.     def countKDifference(self, nums: List[int], k: int) -> int:
   
5.         # 第一步：统计频率，比如 {2: 3, 3: 2, 1: 4}
   
6.         freq = Counter(nums)
   
7.         ans = 0
   
8.         
   
9.         # 第二步：遍历频率字典里的每一个数字 x
   
10.         for x in freq:
    
11.             # 只往大了找，看 x + k 是否也在字典里
    
12.             if x + k in freq:
    
13.                 # 乘法原理：x 的个数 * (x+k) 的个数
    
14.                 ans += freq[x] * freq[x + k]
    
15.                
    
16.         return ans

复制代码