刷题记录帖子

Myron2017

877. Stone Game
Solved
Medium
Topics
conpanies icon
Companies
Alice and Bob play a game with piles of stones. There are an even number of piles arranged in a row, and each pile has a positive integer number of stones piles[i].

The objective of the game is to end with the most stones. The total number of stones across all the piles is odd, so there are no ties.

Alice and Bob take turns, with Alice starting first. Each turn, a player takes the entire pile of stones either from the beginning or from the end of the row. This continues until there are no more piles left, at which point the person with the most stones wins.

Assuming Alice and Bob play optimally, return true if Alice wins the game, or false if Bob wins.

Example 1:

Input: piles = [5,3,4,5]
Output: true
Explanation:
Alice starts first, and can only take the first 5 or the last 5.
Say she takes the first 5, so that the row becomes [3, 4, 5].
If Bob takes 3, then the board is [4, 5], and Alice takes 5 to win with 10 points.
If Bob takes the last 5, then the board is [3, 4], and Alice takes 4 to win with 9 points.
This demonstrated that taking the first 5 was a winning move for Alice, so we return true.
Example 2:

Input: piles = [3,7,2,3]
Output: true

Constraints:

2 <= piles.length <= 500
piles.length is even.
1 <= piles[i] <= 500
sum(piles[i]) is odd.

如果你尝试用动态规划 (DP) 去解，你会写出 $O(n^2)$ 的代码并顺利通过；但如果你看穿了这道题的本质，你会发现它的答案永远是 return True。这又是数学思维对暴力模拟的一次“降维打击”。1. 核心前提（三个关键点）题目给出了三个至关重要的限制条件：石子堆的总数是偶数（piles.length is even）。石子的总数是奇数（sum(piles) is odd），这意味着不可能平局。Alice 先手。2. Alice 的“必胜策略”：奇偶位选择权因为总堆数是偶数，我们可以把这些堆按索引分为奇数位和偶数位。假设 piles = [5, 3, 4, 5]：偶数位（索引 0, 2）：5, 4，总和为 $9$。奇数位（索引 1, 3）：3, 5，总和为 $8$。Alice 作为先手，可以控制自己拿走所有的偶数位，或者所有的奇数位！她是怎么做到的？想拿全部偶数位：Alice 先拿 piles[0]（偶数位）。剩下的数组两端就变成了索引 1 和索引 $n-1$（都是奇数位）。无论 Bob 拿哪一头，他都只能拿走一个奇数位。Bob 拿完后，数组的两端又会露出一堆偶数位供 Alice 选择。想拿全部奇数位：Alice 先拿 piles[n-1]（最后一个，索引是奇数）。同理，她可以迫使 Bob 只能接触偶数位，而自己把奇数位全卷走。3. 为什么 Alice 必胜？既然 Alice 可以计算出“奇数位总和”与“偶数位总和”哪个更大，而总数又是奇数（保证了两者一定不相等），那么：如果偶数位总和 > 奇数位总和，Alice 就全程只拿偶数位。如果奇数位总和 > 偶数位总和，Alice 就全程只拿奇数位。结论：只要 Alice 足够聪明（Optimal Play），她从第一步开始就已经锁定了胜局。

Myron2017

LC 1022. Sum of Root To Leaf Binary Numbers

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

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

注意

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

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

复制代码

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

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

class Solution:
def sumRootToLeaf(self, root: TreeNode) -> int:
self.res = 0
self.DFS(root, 0)
return self.res
def DFS(self, node, curr_sum):
if not node:
return
# 计算当前路径到达当前节点时的数值
# (curr_sum << 1) | node.val 也是一样的效果
current = curr_sum * 2 + node.val
# 如果是叶子节点，累加结果并直接返回，不再向下递归
if not node.left and not node.right:
self.res += current
return
# 如果不是叶子节点，继续向下探索
self.DFS(node.left, current)
self.DFS(node.right, current)

复制代码

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

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

复制代码

Myron2017

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

class Solution:
def sortByBits(self, arr: List[int]) -> List[int]:
ans = []
for num in arr:
bin_num = bin(num)[2:]
freq = Counter(bin_num)
ans.append((freq['1'], num))
ans.sort()
return [x[1] for x in ans]

复制代码

更加 Python 的代码

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

复制代码

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

Myron2017

LC.461. Hamming Distance

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

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

复制代码

Myron2017

LC 2220. Minimum Bit Flips to Convert Number

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

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

复制代码

Myron2017

LC. 191. Number of 1 Bits

OR. int.bit_count()

Brian Kernighan 算法

class Solution:
def hammingWeight(self, n: int) -> int:
count = 0
while n:
n &= (n-1)
count += 1
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

二、关键性质

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

Myron2017

LC. 338. Counting Bits

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

复制代码

Myron2017

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

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

class Solution:
def numSteps(self, s: str) -> int:
n = int(s, 2)
count = 0
while n != 1:
if n % 2 == 0:
n = n//2
else:
n += 1
count += 1
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（奇数），我们就必须执行加法，这会产生一个持续的“进位”，直到字符串结束。

class Solution:
def numSteps(self, s: str) -> int:
steps = 0
carry = 0
# 从右向左遍历，不处理最左边的第一位 s[0]
# 因为最终目标是让数字变成 1（即二进制的 "1"）
for i in range(len(s) - 1, 0, -1):
# 当前位的值 = 字符值 + 进位
current_val = int(s[i]) + carry
if current_val == 1:
# 情况 A: 1 + 0 (奇数) 或 0 + 1 (奇数)
# 奇数需要：加 1 (step+1) 再除以 2 (step+1)，并产生进位
steps += 2
carry = 1
elif current_val == 0:
# 情况 B: 0 + 0 (偶数)
# 直接除以 2 (step+1)
steps += 1
carry = 0
elif current_val == 2:
# 情况 C: 1 + 1 (偶数，但由于进位变成了 2)
# 已经是偶数，直接除以 2 (step+1)，进位保持 1
steps += 1
carry = 1
# 最后处理最左边的位 s[0] 和最后的进位 carry
# 如果有进位，说明 "1" 变成了 "10"，需要额外一步除法变回 "1"
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”这一步动作即可。

Myron2017

LC. 2000. Reverse Prefix of Word

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

复制代码

Myron2017

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.

# Write your MySQL query statement below
# 1. 计算每个员工在其分组内（Senior/Junior）按薪水升序的累积薪水
WITH RunningSalary AS (
SELECT
employee_id,
experience,
salary,
SUM(salary) OVER(PARTITION BY experience ORDER BY salary, employee_id) AS cum_sum
FROM Candidates
),
# 2. 找出能入职的 Senior
SeniorsHired AS (
SELECT * FROM RunningSalary
WHERE experience = 'Senior' AND cum_sum <= 70000
),
# 3. 计算招完 Senior 后剩下的钱 (注意如果没有 Senior 能入职，剩余还是 70000)
LeftoverBudget AS (
SELECT 70000 - IFNULL(MAX(cum_sum), 0) AS budget
FROM SeniorsHired
),
# 4. 找出能入职的 Junior
JuniorsHired AS (
SELECT *
FROM RunningSalary
WHERE experience = 'Junior'
AND cum_sum <= (SELECT budget FROM LeftoverBudget)
)
# 5. 汇总结果，UNION 保证没有人的分类也会出现 0
SELECT 'Senior' AS experience, COUNT(*) AS accepted_candidates FROM SeniorsHired
UNION ALL
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，这种写法也能确保它出现在结果中。

刷题记录帖子

浏览过的版块