刷题记录帖子

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

复制代码

2010. The Number of Seniors and Juniors to Join the Company II
Solved
Hard
Topics
SQL Schema
Pandas Schema
Table: Candidates

+-------------+------+
| 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) of types ('Senior', 'Junior').
Each row of this table indicates the id of a candidate, their monthly salary, and their experience.
The salary of each candidate is guaranteed to be unique.


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

Keep hiring the senior with the smallest salary until you cannot hire any more seniors.
Use the remaining budget to hire the junior with the smallest salary.
Keep hiring the junior with the smallest salary until you cannot hire any more juniors.
Write a solution to find the ids 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     | 15000  |
| 2           | Senior     | 20000  |
| 11          | Senior     | 16000  |
| 13          | Senior     | 50000  |
| 4           | Junior     | 40000  |
+-------------+------------+--------+
Output:
+-------------+
| employee_id |
+-------------+
| 11          |
| 2           |
| 1           |
| 9           |
+-------------+
Explanation:
We can hire 2 seniors with IDs (11, 2). Since the budget is $70000 and the sum of their salaries is $36000, we still have $34000 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 $34000 and the sum of their salaries is $25000, we still have $9000 but they are not enough to hire the junior candidate with ID 4.
Example 2:

Input:
Candidates table:
+-------------+------------+--------+
| employee_id | experience | salary |
+-------------+------------+--------+
| 1           | Junior     | 25000  |
| 9           | Junior     | 10000  |
| 2           | Senior     | 85000  |
| 11          | Senior     | 80000  |
| 13          | Senior     | 90000  |
| 4           | Junior     | 30000  |
+-------------+------------+--------+
Output:
+-------------+
| employee_id |
+-------------+
| 9           |
| 1           |
| 4           |
+-------------+
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. # 1. 计算每个员工在自己等级（Senior/Junior）里的累积薪水
   
2. WITH RunningTotals AS (
   
3.     SELECT
   
4.         employee_id,
   
5.         experience,
   
6.         salary,
   
7.         SUM(salary) OVER(PARTITION BY experience ORDER BY salary) AS cum_salary
   
8.     FROM Candidates
   
9. ),
   
10. 
    
11. # 2. 找出能入职的 Senior
    
12. SeniorsHired AS (
    
13.     SELECT employee_id, salary, cum_salary
    
14.     FROM RunningTotals
    
15.     WHERE experience = 'Senior' AND cum_salary <= 70000
    
16. ),
    
17. 
    
18. # 3. 算出招完 Senior 后剩多少钱
    
19. # 使用 COALESCE 处理没有 Senior 能入职的情况，保证预算还是 70000
    
20. BudgetLeft AS (
    
21.     SELECT 70000 - COALESCE(SUM(salary), 0) AS remaining
    
22.     FROM SeniorsHired
    
23. )
    
24. 
    
25. # 4. 找出能入职的 Junior 并与 Senior 的 ID 合并
    
26. SELECT employee_id
    
27. FROM SeniorsHired
    
28. 
    
29. UNION ALL
    
30. 
    
31. SELECT employee_id
    
32. FROM RunningTotals
    
33. WHERE experience = 'Junior'
    
34.   AND cum_salary <= (SELECT remaining FROM BudgetLeft);

复制代码

补充内容 (2026-02-26 12:02 +08:00):
Leetcode 刷题伴侣
Custom Gem
Leetcode 刷题伴侣 said
看来你已经成功闯到了 LC 2004 的“进化版”！
这道题（LC 2010）和上一题的核心逻辑几乎一模一样，唯一的区别在于：上一题要的是“数量（Count）”，这一题要的是“具体的 ID”。
这其实让题目变得简单了一点点，因为我们不需要最后去处理

1. UNION ALL

复制代码

补

1. 0

复制代码

的问题了，直接把筛选出来的

1. employee_id

复制代码

吐出来就行。
1. 题意拆解

• 贪心策略不变：依然是薪水越低越优先。
• 依赖关系不变：Junior 能买多少人，取决于 Senior 剩下的钱。
• 输出要求变了：只输出一列
  1. employee_id

  复制代码
  。
• 关键点：你需要记录下招募 Senior 到底花掉多少钱，这个数字是 Junior 准入的“门槛”。

2. 核心思路：双重过滤

• 第一步：计算流水账。使用窗口函数
  1. SUM() OVER()

  复制代码
  为 Senior 和 Junior 分别计算累积薪水。
• 第二步：锁定 Senior。找出所有累积薪水 ≤70000 的 Senior。
• 第三步：精确计算余额。算出这些选中的 Senior 总共花了多少钱。
• 第四步：筛选 Junior。找出累积薪水 ≤(70000−Senior花费) 的 Junior。
• 第五步：合并 ID。把两拨人的 ID 拼在一起。

3. SQL 代码实现 (MySQL)
SQL
# 1. 计算每个员工在自己等级（Senior/Junior）里的累积薪水
WITH RunningTotals AS (
    SELECT
        employee_id,
        experience,
        salary,
        SUM(salary) OVER(PARTITION BY experience ORDER BY salary) AS cum_salary
    FROM Candidates
),

# 2. 找出能入职的 Senior
SeniorsHired AS (
    SELECT employee_id, salary, cum_salary
    FROM RunningTotals
    WHERE experience = 'Senior' AND cum_salary <= 70000
),

# 3. 算出招完 Senior 后剩多少钱
# 使用 COALESCE 处理没有 Senior 能入职的情况，保证预算还是 70000
BudgetLeft AS (
    SELECT 70000 - COALESCE(SUM(salary), 0) AS remaining
    FROM SeniorsHired
)

# 4. 找出能入职的 Junior 并与 Senior 的 ID 合并
SELECT employee_id
FROM SeniorsHired

UNION ALL

SELECT employee_id
FROM RunningTotals
WHERE experience = 'Junior'
  AND cum_salary <= (SELECT remaining FROM BudgetLeft);
4. 关键点剖析

• 1. SUM(salary) OVER(PARTITION BY experience ORDER BY salary)

  复制代码
  :
  这是解题的灵魂。它为每个员工建立了一个“排队位次”。比如 Junior A 薪水 1w，其
  1. cum_salary

  复制代码
  是 1w；Junior B 薪水 1.5w，其
  1. cum_salary

  复制代码
  就是 2.5w。
• 余额传递:
  在
  1. SeniorsHired

  复制代码
  中，我们不仅选出了 ID，还保留了这些人的薪水。在
  1. BudgetLeft

  复制代码
  里通过
  1. SUM(salary)

  复制代码
  算出总支出。

  注意：这里也可以用

  1. MAX(cum_salary)

  复制代码

  ，效果是一样的，因为最后一个人对应的累积薪水就是总花费。

• 1. COALESCE(..., 0)

  复制代码
  :
  这是一个防御性编程的好习惯。如果公司预算太低，一个 Senior 都招不起，
  1. SUM

  复制代码
  会返回
  1. NULL

  复制代码
  。用了
  1. COALESCE

  复制代码
  就能确保 Junior 依然有 70,000 可以挥霍。

LC. 2011. Final Value of Variable After Performing Operations

1. class Solution:
   
2.     def finalValueAfterOperations(self, operations: List[str]) -> int:
   
3.         ans = 0
   
4.         for s in operations:
   
5.             if s in ['++X', 'X++']: ans += 1
   
6.             else:
   
7.                 ans -= 1
   
8.         return ans
   
9.         

复制代码

LC. 1680. Concatenation of Consecutive Binary Numbers

1. class Solution:
   
2.     def concatenatedBinary(self, n: int) -> int:
   
3.         mod = 10**9 + 7
   
4.         ans = 1
   
5.         if n == 1: return 1
   
6.         for i in range(2, n + 1):
   
7.             bin_n = bin(i)[2:]
   
8.             ans = ((ans * (2 ** len(bin_n)) )+ i) % mod
   
9.         return ans % mod

复制代码

进阶优化建议我们可以通过位运算来彻底干掉字符串操作和幂运算。A. 使用位移运算符 (<<)与其计算 $2^L$，不如直接使用位移操作。在计算机底层，ans << L 的效率远高于 ans * (2**L)。B. 动态维护二进制长度观察规律：只有当 $i$ 是 2 的幂（如 2, 4, 8, 16...）时，它的二进制位数才会增加。$i = 1$ ($1_2$) -> 1位$i = 2$ ($10_2$) -> 2位$i = 4$ ($100_2$) -> 3位我们可以用一个变量 bit_len 来记录当前长度，当 (i & (i - 1)) == 0 时，说明 $i$ 是 2 的幂，此时 bit_len 加 1。

1. class Solution:
   
2.     def concatenatedBinary(self, n: int) -> int:
   
3.         MOD = 10**9 + 7
   
4.         ans = 0
   
5.         bit_len = 0
   
6.         
   
7.         for i in range(1, n + 1):
   
8.             # 当 i 是 2 的幂时，二进制长度增加 1
   
9.             # 例如：i=2 (10), i=4 (100), i=8 (1000)
   
10.             if i & (i - 1) == 0:
    
11.                 bit_len += 1
    
12.             
    
13.             # 1. ans 左移 bit_len 位，腾出空间
    
14.             # 2. 加上当前的 i
    
15.             # 3. 取模
    
16.             ans = ((ans << bit_len) | i) % MOD
    
17.             
    
18.         return ans

复制代码

如果在面试中，你可以提到以下两点，面试官会非常欣赏：

位运算效率：提到 (i & (i - 1)) == 0 是判断 2 的幂的经典技巧，比调用数学库快。

大数处理：Python 自动处理大整数，但在 C++/Java 中需要注意 ans << bit_len 可能会在取模前溢出，所以必须使用 long 类型。

补充内容 (2026-02-28 10:50 +08:00):
这里的

1. |

复制代码

是 按位或 (Bitwise OR) 运算符。
在你的原始代码中，你使用的是

1. + i

复制代码

。在位运算的语境下，

1. | i

复制代码

和

1. + i

复制代码

在这里达到了同样的效果，但

1. |

复制代码

更符合底层逻辑。
1. 为什么可以用

1. |

复制代码

代替

1. +

复制代码

？
当我们执行

1. ans << bit_len

复制代码

时，

1. ans

复制代码

的二进制表示向左移动了

1. bit_len

复制代码

位，低位补了全 0。
例如，当

1. ans = 3

复制代码

($11_2$)，我们要拼接

1. i = 2

复制代码

($10_2$)：

• 左移：
  1. ans << 2

  复制代码
  得到 $1100_2$ (十进制 12)。
• 此时低两位全是 0。
• 合并：将 $1100_2$ 与 $10_2$ 进行
  1. |

  复制代码
  (或) 运算：
• • $1100$
  • $0010$ (这是 $i$)
  • 1. ----

    复制代码
  • $1110$ (结果)

因为左移后低位是干净的（全是 0），所以

1. OR

复制代码

运算在这里等同于加法，但它在逻辑上更强调“填充”这些空位。
2. 运算符对比表
在处理二进制拼接时，这两者经常互换，但有细微差别：

运算符	名称	逻辑	在本题中的意义
`	`	按位或	只要有一个为 1，结果就为 1
+ 复制代码	加法	正常的算术求和	同样能把 $i$ 加进去，但如果位移没留够空间，会产生进位。

补充内容 (2026-02-28 10:52 +08:00):
2. 核心逻辑

• 2 的幂的特征：在二进制中，2 的幂有且仅有一个位是
  1. 1

  复制代码
  ，其余全是
  1. 0

  复制代码
  （例如 $8 = 1000_2$）。
• 减 1 的效果：当你把一个 2 的幂减去 1 时，原本唯一的那个
  1. 1

  复制代码
  会变成
  1. 0

  复制代码
  ，而它右边所有的
  1. 0

  复制代码
  都会变成
  1. 1

  复制代码
  （例如 $8 - 1 = 7$，二进制从
  1. 1000

  复制代码
  变成
  1. 0111

  复制代码
  ）。
• 按位与 (&) 的结果：
• • 1. i

    复制代码
    的
    1. 1

    复制代码
    在高位。
  • 1. i - 1

    复制代码
    的
    1. 1

    复制代码
    全在低位。
  • 它们没有任何一个位置同时为
    1. 1

    复制代码
    。
  • 因此，
    1. i & (i - 1)

    复制代码
    的结果必然是 0。

3. 如果不是 2 的幂呢？
如果一个数不是 2 的幂（且不为 0），它的二进制中至少有两个

1. 1

复制代码

。

• 例如 $i = 6$ ($110_2$)
• $i - 1 = 5$ ($101_2$)
• $6 \text{ \& } 5 = 110 \text{ \& } 101 = 100_2$ (结果是 4，不等于 0)

结论：

1. i & (i - 1)

复制代码

实际上会消除二进制表示中最右边的那个

1. 1

复制代码

。如果消除掉唯一的那个

1. 1

复制代码

后变成了 0，那这个数原本就是 2 的幂。
4. 注意一个小坑
在实际编程中，如果 $i = 0$：

• $0 \text{ \& } (0 - 1)$ 在很多语言里也会返回 0，但 0 并不是 2 的幂。
• 所以严谨的判断通常写成：
  1. i > 0 and (i & (i - 1)) == 0

  复制代码
  。

LC. 43. Multiply Strings

核心思路：模拟竖式乘法
我们要模拟小学数学里的竖式计算，但为了代码实现方便，可以做一个关键优化：

准备一个数组：创建一个长度为 len(num1) + len(num2) 的数组 res，初始化为 0，用来存储每一位的计算结果。

双循环遍历：从右往左（低位到高位）遍历 num1 和 num2。

索引定位（最关键）：

num1[i] 和 num2[j] 相乘的结果，其低位会落在 res 的 i + j + 1 位置。

其进位会累加到 res 的 i + j 位置。

1. 为什么结果数组长度是 $m + n$？假设 $num1 = "123"$ ($m=3$), $num2 = "456"$ ($n=3$)。最大的三位数相乘：$999 \times 999 = 998,001$（6位，即 $3+3$）。最小的三位数相乘：$100 \times 100 = 10,000$（5位）。所以，结果数组 res 的长度定为 $m+n=6$ 绝对能装下所有的位数。

总结口诀两个索引 $i$ 和 $j$ 的数相乘。右边那个坑位（个位）是 $i+j+1$。左边那个坑位（进位）是 $i+j$。

1. class Solution:
   
2.     def multiply(self, num1: str, num2: str) -> str:
   
3.         if num1 == '0' or num2 == '0':
   
4.             return '0'
   
5.         n1 = len(num1)
   
6.         n2 = len(num2)
   
7.         res = [0] * (n1+n2)
   
8. 
   
9.         for i in range(n1-1, -1, -1):
   
10.             for j in range(n2-1, -1, -1):
    
11.                 curr = int(num1[i]) * int(num2[j])
    
12.                 p1 = i+j
    
13.                 p2 = i+j+1
    
14. 
    
15.                 curr += res[p2]
    
16.                 res[p2] = curr % 10
    
17.                 res[p1] += curr // 10
    
18. 
    
19.         start = 0
    
20.         while start < (n1+n2) and res[start] == 0:
    
21.             start += 1
    
22. 
    
23.         return "".join(map(str, res[start:]))        
    
24. 
    
25.         

复制代码

补充内容 (2026-03-01 03:00 +08:00):

LC. 1689. Partitioning Into Minimum Number Of Deci-Binary Numbers
Solved
Medium
Topics
conpanies icon
Companies
Hint
A decimal number is called deci-binary if each of its digits is either 0 or 1 without any leading zeros. For example, 101 and 1100 are deci-binary, while 112 and 3001 are not.

Given a string n that represents a positive decimal integer, return the minimum number of positive deci-binary numbers needed so that they sum up to n.



Example 1:

Input: n = "32"
Output: 3
Explanation: 10 + 11 + 11 = 32
Example 2:

Input: n = "82734"
Output: 8
Example 3:

Input: n = "27346209830709182346"
Output: 9


Constraints:

1 <= n.length <= 105
n consists of only digits.
n does not contain any leading zeros and represents a positive integer.

1. class Solution:
   
2.     def minPartitions(self, n: str) -> int:
   
3.         freq = Counter(n)
   
4. 
   
5.         return max([int(ch) for ch in freq.keys()])
   
6.         

复制代码

好吧，发现 Python max 可以直接作用于 string

1. class Solution:
   
2.     def minPartitions(self, n: str) -> int:
   
3.         # 直接利用字符串的 max()，它会按字符的 ASCII 码找最大的
   
4.         # 然后转换为整数返回
   
5.         return int(max(n))

复制代码

LC. 219. Contains Duplicate II

1. class Solution:
   
2.     def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
   
3.         val_ind_dict = defaultdict(int)
   
4.         for i in range(len(nums)):
   
5.             if nums[i] in val_ind_dict:
   
6.                 if (i - val_ind_dict[nums[i]]) <= k:
   
7.                     return True
   
8.             val_ind_dict[nums[i]] = i
   
9.         return False

复制代码

LC. 1667. Fix Names in a Table
Easy
Topics
conpanies icon
Companies
SQL Schema
Pandas Schema
Table: Users

+----------------+---------+
| Column Name    | Type    |
+----------------+---------+
| user_id        | int     |
| name           | varchar |
+----------------+---------+
user_id is the primary key (column with unique values) for this table.
This table contains the ID and the name of the user. The name consists of only lowercase and uppercase characters.


Write a solution to fix the names so that only the first character is uppercase and the rest are lowercase.

Return the result table ordered by user_id.

The result format is in the following example.



Example 1:

Input:
Users table:
+---------+-------+
| user_id | name  |
+---------+-------+
| 1       | aLice |
| 2       | bOB   |
+---------+-------+
Output:
+---------+-------+
| user_id | name  |
+---------+-------+
| 1       | Alice |
| 2       | Bob   |
+---------+-------+

1. import pandas as pd
   
2. 
   
3. def fix_names(users: pd.DataFrame) -> pd.DataFrame:
   
4.     # 1. 直接调用 .str.capitalize() 处理 name 列
   
5.     users['name'] = users['name'].str.capitalize()
   
6.    
   
7.     # 2. 根据 user_id 进行升序排序
   
8.     # 这是题目要求的 "Return the result table ordered by user_id"
   
9.     result = users.sort_values(by='user_id')
   
10.    
    
11.     return result

复制代码

SQL 代码

1. # Write your MySQL query statement below
   
2. SELECT
   
3.     user_id,
   
4.     CONCAT(
   
5.         UPPER(LEFT(name, 1)),
   
6.         LOWER(SUBSTRING(name, 2))
   
7.     ) AS name
   
8. FROM Users
   
9. ORDER BY user_id;

复制代码

LC. 1545. Find Kth Bit in Nth Binary String

很有意思的一道题，我一开始是直接模拟，比较简单容易想 。

但是这道题目其实更加本质的问题，是这是一个 二分法的变体！

说实话，这个是可以想到的，但是我没有想到。


还是刷题的敏锐度问题，或者说还是没有刷题的感觉！keep 刷题！

<code>
class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        # 递归终止条件
        if n == 1:
            return "0"
        
        # 计算当前 Sn 的长度
        length = (1 << n) - 1
        mid = (length // 2) + 1
        
        if k == mid:
            return "1"
        elif k < mid:
            # 在左半部分，等同于在 Sn-1 中找第 k 位
            return self.findKthBit(n - 1, k)
        else:
            # 在右半部分，对应 Sn-1 翻转取反后的位置
            # 找到对应于 Sn-1 中的位置：mid - (k - mid) = 2*mid - k
            res = self.findKthBit(n - 1, 2 * mid - k)
            # 取反操作
            return "1" if res == "0" else "0"
"""
class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        
        def reverse_invert(s):
            res = deque([])
            for ch in s:
                if ch == '0': res.appendleft('1')
                else:
                    res.appendleft('0')
            return "".join(res)
        
        ans = "0"
        for i in range(1, n):
            ans = ans+"1"+reverse_invert(ans)
        
        return ans[k-1]
"""
</code>

1582. Special Positions in a Binary Matrix

暴力解法不太高效，完全可以先统计，后查表。

1. class Solution:
   
2.     def numSpecial(self, mat: List[List[int]]) -> int:
   
3.         ans = 0
   
4. 
   
5.         for i in range(len(mat)):
   
6.             for j in range(len(mat[0])):
   
7.                 if mat[i][j] == 1:
   
8.                     if sum(mat[i]) == 1 and sum( [mat[x][j] for x in range(len(mat))] ) == 1:
   
9.                         ans += 1
   
10.         return ans
    
11.         

复制代码

既然我们要频繁知道“某一行有几个 $1$”和“某一列有几个 $1$”，为什么不先数一遍存起来呢？优化思路：第一遍扫描：统计每行 $1$ 的个数，存在数组 row_count 中；统计每列 $1$ 的个数，存在 col_count 中。第二遍扫描：遍历矩阵，如果 mat[i][j] == 1 且 row_count[i] == 1 且 col_count[j] == 1，这就是我们要找的特殊位置。

1. class Solution:
   
2.     def numSpecial(self, mat: List[List[int]]) -> int:
   
3.         m, n = len(mat), len(mat[0])
   
4.         
   
5.         # 1. 预处理：统计每行和每列 1 的个数
   
6.         # 时间复杂度 O(M*N)
   
7.         row_count = [0] * m
   
8.         col_count = [0] * n
   
9.         
   
10.         for r in range(m):
    
11.             for c in range(n):
    
12.                 if mat[r][c] == 1:
    
13.                     row_count[r] += 1
    
14.                     col_count[c] += 1
    
15.         
    
16.         # 2. 二次遍历：寻找符合条件的特殊位置
    
17.         # 时间复杂度 O(M*N)
    
18.         ans = 0
    
19.         for r in range(m):
    
20.             # 剪枝优化：如果这一行本来就没有 1 或者不止一个 1，直接跳过这一行
    
21.             if row_count[r] != 1:
    
22.                 continue
    
23.             for c in range(n):
    
24.                 if mat[r][c] == 1:
    
25.                     # 此时已经确定 row_count[r] == 1，只需要检查列
    
26.                     if col_count[c] == 1:
    
27.                         ans += 1
    
28.         
    
29.         return ans

复制代码