刷题记录帖子

简单题目，但是也挺有意思，如果我是考官，我会出这个题目热热身。

暴力 simulation 的做法

class Solution:
    def tictactoe(self, moves: List[List[int]]) -> str:
        grid = [['', '', ''] for _ in range(3)]

        for ind, move in enumerate(moves):
            row, col = move
            if ind % 2 == 0:
                grid[row][col] = 'X'
            else:
                grid[row][col] = 'O'
        print(grid)
        print(set([grid[0][0], grid[1][1], grid[2][2]]) == set('X'))
        # check
        def checkWin(player, ch):
            for i in range(3):
                if set(grid[i]) == set(ch):
                    return player
            for i in range(3):
                if set([grid[0][i], grid[1][i], grid[2][i]]) == set(ch):
                    return player
            if set([grid[0][0], grid[1][1], grid[2][2]]) == set(ch):
                return player
            if set([grid[0][2], grid[1][1], grid[2][0]]) == set(ch):
                return player
        
        res_a = checkWin('A', 'X')
        if res_a: # 如果 res_a 不是 None，说明 A 赢了
            return res_a

        res_b = checkWin('B', 'O')
        if res_b: # 如果 res_b 不是 None，说明 B 赢了
            return res_b
        # draw
        if len(moves) == 9: return 'Draw'
        # pending
        return 'Pending'


更好的解法
class Solution:
    def tictactoe(self, moves: list[list[int]]) -> str:
        # 8 条线的得分统计：3行 + 3列 + 2对角线
        rows, cols = [0] * 3, [0] * 3
        diag1 = diag2 = 0
        
        for i, (r, c) in enumerate(moves):
            # A 为 1分，B 为 -1分
            score = 1 if i % 2 == 0 else -1
            
            rows[r] += score
            cols[c] += score
            if r == c: diag1 += score
            if r + c == 2: diag2 += score
            
            # 检查是否有人达到 3 分（A赢）或 -3 分（B赢）
            if 3 in (rows[r], cols[c], diag1, diag2): return "A"
            if -3 in (rows[r], cols[c], diag1, diag2): return "B"
            
        return "Draw" if len(moves) == 9 else "Pending"

1009. Complement of Base 10 Integer
Solved
Easy
Topics
conpanies icon
Companies
Hint
The complement of an integer is the integer you get when you flip all the 0's to 1's and all the 1's to 0's in its binary representation.

For example, The integer 5 is "101" in binary and its complement is "010" which is the integer 2.
Given an integer n, return its complement.



Example 1:

Input: n = 5
Output: 2
Explanation: 5 is "101" in binary, with complement "010" in binary, which is 2 in base-10.
Example 2:

Input: n = 7
Output: 0
Explanation: 7 is "111" in binary, with complement "000" in binary, which is 0 in base-10.
Example 3:

Input: n = 10
Output: 5
Explanation: 10 is "1010" in binary, with complement "0101" in binary, which is 5 in base-10.


Constraints:

0 <= n < 109

OR 直接字符串操作

1. class Solution:
   
2.     def bitwiseComplement(self, n: int) -> int:
   
3.         str_n = bin(n)[2:]
   
4.         ans = ""
   
5.         for ch in str_n:
   
6.             if ch == '1':
   
7.                 ans += '0'
   
8.             else:
   
9.                 ans += '1'
   
10.         return int(ans, 2)

复制代码

LC. 177. Nth Highest Salary
Medium
Topics
conpanies icon
Companies
SQL Schema
Pandas Schema
Table: Employee

+-------------+------+
| Column Name | Type |
+-------------+------+
| id          | int  |
| salary      | int  |
+-------------+------+
id is the primary key (column with unique values) for this table.
Each row of this table contains information about the salary of an employee.


Write a solution to find the nth highest distinct salary from the Employee table. If there are less than n distinct salaries, return null.

The result format is in the following example.

1. import pandas as pd
   
2. 
   
3. def nth_highest_salary(employee: pd.DataFrame, N: int) -> pd.DataFrame:
   
4.     # 1. 去重：只保留唯一的工资
   
5.     unique_salaries = employee['salary'].drop_duplicates()
   
6.    
   
7.     # 2. 排序：按工资降序排列 (ascending=False)
   
8.     # sort_values 返回的是 Series，我们依然可以对其进行操作
   
9.     sorted_salaries = unique_salaries.sort_values(ascending=False)
   
10.    
    
11.     # 3. 处理边界情况：如果 N 无效（负数或 0）或者 N 超过了现有的唯一工资数
    
12.     if N <= 0 or N > len(sorted_salaries):
    
13.         # 题目要求返回一个 DataFrame，列名为 "getNthHighestSalary(N)"，值为 None
    
14.         return pd.DataFrame({f'getNthHighestSalary({N})': [None]})
    
15.    
    
16.     # 4. 提取第 N 高：索引为 N-1
    
17.     # .iloc[N-1] 拿到具体数值
    
18.     res = sorted_salaries.iloc[N-1]
    
19.    
    
20.     return pd.DataFrame({f'getNthHighestSalary({N})': [res]})

复制代码

LC. 180. Consecutive Numbers
Solved
Medium
Topics
conpanies icon
Companies
SQL Schema
Pandas Schema
Table: Logs

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| id          | int     |
| num         | varchar |
+-------------+---------+
In SQL, id is the primary key for this table.
id is an autoincrement column starting from 1.


Find all numbers that appear at least three times consecutively.

Return the result table in any order.

The result format is in the following example.



Example 1:

Input:
Logs table:
+----+-----+
| id | num |
+----+-----+
| 1  | 1   |
| 2  | 1   |
| 3  | 1   |
| 4  | 2   |
| 5  | 1   |
| 6  | 2   |
| 7  | 2   |
+----+-----+
Output:
+-----------------+
| ConsecutiveNums |
+-----------------+
| 1               |
+-----------------+
Explanation: 1 is the only number that appears consecutively for at least three times.

1. SELECT DISTINCT num AS ConsecutiveNums
   
2. FROM (
   
3.     SELECT num,
   
4.            LEAD(num, 1) OVER (ORDER BY id) AS next_1,
   
5.            LEAD(num, 2) OVER (ORDER BY id) AS next_2
   
6.     FROM Logs
   
7. ) AS temp
   
8. WHERE num = next_1 AND num = next_2;

复制代码

LC. 182. Duplicate Emails
Easy
Topics
conpanies icon
Companies
SQL Schema
Pandas Schema
Table: Person

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| id          | int     |
| email       | varchar |
+-------------+---------+
id is the primary key (column with unique values) for this table.
Each row of this table contains an email. The emails will not contain uppercase letters.


Write a solution to report all the duplicate emails. Note that it's guaranteed that the email field is not NULL.

Return the result table in any order.

The result format is in the following example.



Example 1:

Input:
Person table:
+----+---------+
| id | email   |
+----+---------+
| 1  | a@b.com |
| 2  | c@d.com |
| 3  | a@b.com |
+----+---------+
Output:
+---------+
| Email   |
+---------+
| a@b.com |
+---------+
Explanation: a@b.com is repeated two times.

1. SELECT email AS Email
   
2. FROM Person
   
3. GROUP BY email
   
4. HAVING COUNT(email) > 1;

复制代码

3296. Minimum Number of Seconds to Make Mountain Height Zero

You are given an integer mountainHeight denoting the height of a mountain.

You are also given an integer array workerTimes representing the work time of workers in seconds.

The workers work simultaneously to reduce the height of the mountain. For worker i:

To decrease the mountain's height by x, it takes workerTimes[i] + workerTimes[i] * 2 + ... + workerTimes[i] * x seconds. For example:
To reduce the height of the mountain by 1, it takes workerTimes[i] seconds.
To reduce the height of the mountain by 2, it takes workerTimes[i] + workerTimes[i] * 2 seconds, and so on.
Return an integer representing the minimum number of seconds required for the workers to make the height of the mountain 0.



Example 1:

Input: mountainHeight = 4, workerTimes = [2,1,1]

Output: 3

Explanation:

One way the height of the mountain can be reduced to 0 is:

Worker 0 reduces the height by 1, taking workerTimes[0] = 2 seconds.
Worker 1 reduces the height by 2, taking workerTimes[1] + workerTimes[1] * 2 = 3 seconds.
Worker 2 reduces the height by 1, taking workerTimes[2] = 1 second.
Since they work simultaneously, the minimum time needed is max(2, 3, 1) = 3 seconds.

Example 2:

Input: mountainHeight = 10, workerTimes = [3,2,2,4]

Output: 12

Explanation:

Worker 0 reduces the height by 2, taking workerTimes[0] + workerTimes[0] * 2 = 9 seconds.
Worker 1 reduces the height by 3, taking workerTimes[1] + workerTimes[1] * 2 + workerTimes[1] * 3 = 12 seconds.
Worker 2 reduces the height by 3, taking workerTimes[2] + workerTimes[2] * 2 + workerTimes[2] * 3 = 12 seconds.
Worker 3 reduces the height by 2, taking workerTimes[3] + workerTimes[3] * 2 = 12 seconds.
The number of seconds needed is max(9, 12, 12, 12) = 12 seconds.

Example 3:

Input: mountainHeight = 5, workerTimes = [1]

Output: 15

Explanation:

There is only one worker in this example, so the answer is workerTimes[0] + workerTimes[0] * 2 + workerTimes[0] * 3 + workerTimes[0] * 4 + workerTimes[0] * 5 = 15.



Constraints:

1 <= mountainHeight <= 105
1 <= workerTimes.length <= 104
1 <= workerTimes[i] <= 106

1. 识别“二分答案”的信号灯这是本题最重要的直觉。当你看到以下特征时，大脑应立刻闪现“二分”：求最值：题目问的是“最小的时间”、“最大的距离”、“最少的开销”。单调性：随着变量（时间）的增加，结果（总高度）一定是非递减的。Check 容易，直接求难：直接计算“$T$ 时间内能降多少高度”很简单（数学公式），但反过来问“降 $H$ 高度最少要多少秒”却很难直接分配任务。2. 数学公式的推导与陷阱在面试中，数学推导一定要在草稿纸上写清楚，不要只在大脑里模拟：等差数列求和：熟练掌握 $\sum_{i=1}^{x} i = \frac{x(x+1)}{2}$。一元二次方程求根：$ax^2 + bx + c = 0$ 的根为 $x = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$。精度与整数：在 Python 中，int(math.sqrt(...)) 之后要小心，如果数值极大（超过 $10^{15}$），浮点数可能会有微小误差。稳妥方案：如果担心精度，check 函数内部也可以用一个小二分来找每个工人的 $x$。3. 二分查找的“防坑”三板斧为了避免死循环和边界错误，请记住这套标准模板：确定边界：l 取最小值（1），r 取一个绝对能完成的最大值（例如最慢工人做完全部）。循环条件：统一使用 while l <= r。更新逻辑：满足条件：记录答案 ans = mid，尝试更小 r = mid - 1。不满足条件：尝试更大 l = mid + 1。教训：永远不要写 l = mid 或 r = mid，这在 l=5, r=6 时极易导致死循环。4. 性能优化意识（面试加分项）早停（Early Exit）：在 check 函数中，如果当前的 total_height 已经大于等于目标高度，直接 return True。没必要算出所有工人的贡献，这能显著降低运行时间。选择合适的边界：右边界 r 设得越准，二分次数越少。比如取 min(workerTimes) * H * (H+1) // 2 比随便给个 $10^{18}$ 要专业得多。5. 扩展思考：如果二分失效怎么办？如果这道题的高度 $H$ 特别小（比如 $H=100$），但工人特别多，那么用**优先队列（最小堆）**模拟每一秒的过程可能更直观。教训：不要只会一种方法。二分适合“大高度、大时间”；堆适合“小高度、动态决策”。

1. class Solution:
   
2.     def minNumberOfSeconds(self, mountainHeight: int, workerTimes: List[int]) -> int:
   
3.         # hard to aggrange each worker working time length
   
4.         # easy to get total work done for all works at time T
   
5. 
   
6.         def check(T):
   
7.             total = 0
   
8.             # for worker w
   
9.             # Assume it can reduce height x in time T
   
10.             # w * 1 + w * 2 + ... + w * x <= T
    
11.             # == > x(x+1) * w <= T
    
12.             # == > x^2 + x - 2T/w <= 0
    
13.             # == > x >= (sqrt(8 * T / w + 1) -1 ) /2, negative x is not right
    
14.             for w in workerTimes:
    
15.                 total += int((math.sqrt( 8 * T // w + 1 ) -1 ) / 2)
    
16.                 if total >= mountainHeight:
    
17.                     return True
    
18.             return total >= mountainHeight
    
19. 
    
20.         # binary serach
    
21.         l = 1
    
22.         r = (mountainHeight + 1) * mountainHeight * min(workerTimes) // 2
    
23.         
    
24.         ans = r
    
25.         while l <= r:
    
26.             mid = (l + r) // 2
    
27.             if check(mid):
    
28.                 r = mid - 1
    
29.                 ans = mid
    
30.             else:
    
31.                 l = mid + 1
    
32.         return ans

复制代码

LC 2187. Minimum Time to Complete Trips

类似思路题目，这题的 check 还更加简单。

但是需要注意识别题目 pattern。

这种题目的“长相” (Pattern Recognition)当你看到题目具备以下三个特征时，基本可以锁定这个模式：

求最值：问题通常以“最小化最大值” (Minimize the maximum...) 或 “最大化最小值” (Maximize the minimum...) 的形式出现。本题是“最小化完成任务的时间”。


答案范围确定：虽然你不知道精确答案，但你能确定答案一定在 [min_possible, max_possible] 之间。


关键特征——单调性 (Monotonicity)：这是最核心的。如果 $T$ 秒能完成任务，那么 $T+1$ 秒一定也能完成；如果 $T$ 秒不能完成，那么 $T-1$ 秒更不可能。只要满足这种“行 -> 不行”的转折点关系，就能二分。

. 识别特征 (Pattern Recognition)

关键字：最小化最大值、最大化最小值、最少时间、最短距离。

单调性：若 $x$ 满足条件，则 $x+1$ 必然满足（或必然不满足）。

Check 函数：给定一个固定的值 $T$，能够在线性时间 $O(N)$ 或常数时间内验证其是否可行。

1. def solve(tasks, target):
   
2.     # 1. 确定搜索范围
   
3.     low = min_possible_bound
   
4.     high = max_possible_bound
   
5.     ans = high
   
6.    
   
7.     # 2. 判定函数 (核心：给定一个答案，问是否可行)
   
8.     def check(mid):
   
9.         # 这里的逻辑通常是 O(N) 的贪心或数学计算
   
10.         # 计算在 mid 限制下，能完成的总量是否 >= target
    
11.         ...
    
12.         return count >= target
    
13. 
    
14.     # 3. 标准二分框架
    
15.     while low <= high:
    
16.         mid = (low + high) // 2
    
17.         if check(mid):
    
18.             ans = mid      # 记录可能的结果
    
19.             high = mid - 1 # 尝试更小（求最小化时）
    
20.         else:
    
21.             low = mid + 1  # 必须增大范围
    
22.     return ans

复制代码

解题代码

1. class Solution:
   
2.     def minimumTime(self, time: List[int], totalTrips: int) -> int:
   
3.         # binary serach
   
4.         def check(T):
   
5.             total = 0
   
6.             for t in time:
   
7.                 total += T // t
   
8.                 if total >= totalTrips:
   
9.                     return True
   
10.             return total >= totalTrips
    
11. 
    
12.         l = 1
    
13.         r = min(time) * totalTrips
    
14.         ans = r
    
15. 
    
16.         while l <= r:
    
17.             mid = (l + r) // 2
    
18.             if check(mid):
    
19.                 ans = mid
    
20.                 r = mid - 1
    
21.             else:
    
22.                 l = mid + 1
    
23.         return ans

复制代码

LC .3838. Weighted Word Mapping

1. class Solution:
   
2.     def mapWordWeights(self, words: List[str], weights: List[int]) -> str:
   
3.         ans = []
   
4. 
   
5.         for w in words:
   
6.             w_sum = 0
   
7.             for ch in w:
   
8.                 w_sum += weights[ord(ch) - ord('a')]
   
9.             
   
10.             ans.append(chr((ord('z') - (w_sum % 26))))
    
11.         return "".join(ans)

复制代码

LC. 3827. Count Monobit Integers

1. class Solution:
   
2.     def countMonobit(self, n: int) -> int:
   
3.         return int(math.log(n+1, 2)) + 1

复制代码

LC. 3823. Reverse Letters Then Special Characters in a String

优化就是 stack 如何反转，其实直接 pop 就行，不需要 revese + pop(0)

在 Python 中，list.pop(0) 会导致后续所有元素向前移动，这是一个 O(N) 的操作。如果字符串很长，整个循环就会变成 O(N^2)。

1. class Solution:
   
2.     def reverseByType(self, s: str) -> str:
   
3.         letters = []
   
4.         special = []
   
5. 
   
6.         for ch in s:
   
7.             if ch.isalpha():
   
8.                 letters.append(ch)
   
9.             else:
   
10.                 special.append(ch)
    
11.         #letters.reverse()
    
12.         #special.reverse()
    
13.         ans = []
    
14. 
    
15.         for ch in s:
    
16.             if ch.isalpha():
    
17.                 ans.append(letters.pop())
    
18.             else:
    
19.                 ans.append(special.pop())
    
20.         
    
21.         return "".join(ans)

复制代码

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

我们依然保持思路的清晰性，但通过从后弹出（

1. pop()

复制代码

）来保证 $O(1)$ 的处理效率。