刷题记录帖子

LC. 2460. Apply Operations to an Array

1. class Solution:
   
2.     def applyOperations(self, nums: List[int]) -> List[int]:
   
3.         # do operations
   
4.         for i in range(0, len(nums)-1):
   
5.             if nums[i] == nums[i+1]:
   
6.                 nums[i] *= 2
   
7.                 nums[i+1] = 0
   
8.         # moving zero to the end
   
9.         slow = 0
   
10.         for fast in range(len(nums)):
    
11.             if nums[fast] != 0:
    
12.                 if slow != fast:
    
13.                     nums[slow], nums[fast] = nums[fast], nums[slow]
    
14.                 slow += 1
    
15.         return nums

复制代码

LC  24. Swap Nodes in Pairs

这道题要干什么？→ 两两交换相邻节点
核心技巧是什么？→ dummy 节点 + 三步指针交换
循环条件是什么？→ prev.next and prev.next.next
指针怎么移动？→ prev = first
返回什么？→ dummy.next

1. # Definition for singly-linked list.
   
2. # class ListNode:
   
3. #     def __init__(self, val=0, next=None):
   
4. #         self.val = val
   
5. #         self.next = next
   
6. 
   
7. class Solution:
   
8.     def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
   
9.         # 边界情况：空链表或只有一个节点，无需交换
   
10.         if not head or not head.next:
    
11.             return head
    
12.         
    
13.         # 创建虚拟头节点，简化头节点的处理
    
14.         dummy = ListNode(0)
    
15.         dummy.next = head
    
16.         
    
17.         # prev 始终指向当前需要交换的一对节点的前一个节点
    
18.         prev = dummy
    
19.         
    
20.         # 循环条件：确保存在完整的一对节点（prev.next 和 prev.next.next）
    
21.         while prev.next and prev.next.next:
    
22.             # 标识当前要交换的两个节点
    
23.             first = prev.next           # 第一个节点
    
24.             second = prev.next.next     # 第二个节点
    
25.             
    
26.             # 执行三步指针交换
    
27.             # 步骤1：first 跳过 second，指向 second 后面的节点
    
28.             first.next = second.next
    
29.             # 步骤2：second 指向 first，完成反转
    
30.             second.next = first
    
31.             # 步骤3：prev 指向 second，使 second 成为这对节点的新头
    
32.             prev.next = second
    
33.             
    
34.             # 移动 prev 到下一对节点的前面（即当前的 first）
    
35.             # 因为 first 现在在 second 后面了
    
36.             prev = first
    
37.         
    
38.         # 返回新的头节点
    
39.         return dummy.next

复制代码

LC 547. Number of Provinces

1. from collections import deque
   
2. 
   
3. class Solution:
   
4.     def findCircleNum(self, isConnected: List[List[int]]) -> int:
   
5.         n = len(isConnected)
   
6.         visited = [False] * n
   
7.         count = 0
   
8. 
   
9.         for i in range(n):
   
10.             if not visited[i]:
    
11.                 queue = deque([i])  # ⭐ 使用 deque
    
12.                 visited[i] = True
    
13.                
    
14.                 while queue:
    
15.                     curr = queue.popleft()  # ⭐ O(1) 出队
    
16.                     for j in range(n):
    
17.                         if isConnected[curr][j] == 1 and not visited[j]:
    
18.                             queue.append(j)
    
19.                             visited[j] = True
    
20.                
    
21.                 count += 1
    
22. 
    
23.         return count

复制代码

LC. 904. Fruit Into Baskets

💡 关键点总结

题目转化能力：水果篮 → 最多 2 种不同元素的最长子数组
滑动窗口：双指针 + 哈希表维护窗口状态
窗口收缩：当条件不满足时，移动 left 直到满足
时间优化：每个元素最多进出窗口各一次，O(n)

算法步骤

右指针不断右移，扩大窗口

用哈希表记录窗口内每种水果的数量

当窗口内水果种类 > 2 时：

左指针右移，缩小窗口

直到窗口内只有 2 种水果

记录最大窗口长度

1. class Solution:
   
2.     def totalFruit(self, fruits: List[int]) -> int:
   
3.         from collections import defaultdict
   
4.         
   
5.         # 记录窗口内每种水果的数量
   
6.         basket = defaultdict(int)
   
7.         left = 0
   
8.         max_fruits = 0
   
9.         
   
10.         for right in range(len(fruits)):
    
11.             # 右指针的水果加入窗口
    
12.             basket[fruits[right]] += 1
    
13.             
    
14.             # 当窗口内水果种类 > 2 时，收缩窗口
    
15.             while len(basket) > 2:
    
16.                 basket[fruits[left]] -= 1
    
17.                 # 如果某种水果数量变为 0，移除这个键
    
18.                 if basket[fruits[left]] == 0:
    
19.                     del basket[fruits[left]]
    
20.                 left += 1
    
21.             
    
22.             # 更新最大值
    
23.             max_fruits = max(max_fruits, right - left + 1)
    
24.         
    
25.         return max_fruits

复制代码

支持一下楼主。看到你2020年就开始刷了。
现在AI大行其道，其实这挺影响我刷题的热情的[捂脸]

夏日柠檬红茶 发表于 2026-2-12 21:35
支持一下楼主。看到你2020年就开始刷了。
现在AI大行其道，其实这挺影响我刷题的热情的[捂脸]

我也不喜欢刷题，但是没办法，面试还没改革，那就得继续刷。加油！

LC 799. Champagne Tower

一、题目本质

这是一个：

✅ 流量扩散模型
✅ 二维 DP 模拟
✅ 局部溢出向下分配问题

核心思想：

每个杯子容量 = 1

只向下传递“溢出部分”

二、核心建模思想
1️⃣ 状态定义
dp[r][c] = 流到 (r,c) 的总量


⚠️ 注意：

我们存的是“流入总量”，
而不是“当前杯子里的剩余容量”。

2️⃣ 状态转移公式

当：

dp[r][c] > 1


溢出：

overflow = dp[r][c] - 1


向下流：

dp[r+1][c]     += overflow / 2
dp[r+1][c+1]   += overflow / 2

3️⃣ 最终答案
min(1, dp[query_row][query_glass])


因为杯子最多只能装 1。

这题的结构：

(r,c) → (r+1,c) 和 (r+1,c+1)

十、记忆口诀

只传溢出，不管满杯
自顶向下，逐层推进
最后截断，min(1, ans)

1. class Solution:
   
2.     def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:
   
3.         # dp[r][c] 表示流到第 r 行第 c 个杯子的香槟总量（不是最终容量）
   
4.         # 只需要计算到 query_row 行即可
   
5.         dp = [[0.0] * (r + 1) for r in range(query_row + 1)]
   
6. 
   
7.         # 初始时，所有香槟都倒入顶部杯子
   
8.         dp[0][0] = poured
   
9. 
   
10.         # 从第 0 行开始逐层向下模拟流动
    
11.         for r in range(query_row):
    
12.             for c in range(r + 1):
    
13. 
    
14.                 # 如果当前杯子超过容量 1，才会发生溢出
    
15.                 if dp[r][c] > 1:
    
16. 
    
17.                     # 计算溢出量（超过 1 的部分）
    
18.                     overflow = dp[r][c] - 1
    
19. 
    
20.                     # 溢出部分平均分给下一层左右两个杯子
    
21.                     dp[r + 1][c]     += overflow / 2.0
    
22.                     dp[r + 1][c + 1] += overflow / 2.0
    
23. 
    
24.                     # 注意：
    
25.                     # 不需要把 dp[r][c] 截断为 1
    
26.                     # 因为后续不会再用它继续传递（只用 overflow）
    
27. 
    
28.         # 杯子最大容量为 1，因此最终结果取 min(1, 实际流入量)
    
29.         return min(1.0, dp[query_row][query_glass])
    

复制代码

LC. 66. Plus One

Easy 题，但是需要注意，进位 carry 在最后的时候需要 加上一位。

1. 
   
2. 
   
3. class Solution:
   
4.     def plusOne(self, digits: List[int]) -> List[int]:
   
5.         carry = 1  # 因为我们要 +1
   
6.         
   
7.         # 从最后一位往前处理
   
8.         for i in range(len(digits) - 1, -1, -1):
   
9.             
   
10.             digit_sum = digits[i] + carry
    
11.             
    
12.             digits[i] = digit_sum % 10
    
13.             carry = digit_sum // 10
    
14.             
    
15.             # 如果已经没有进位，可以提前结束
    
16.             if carry == 0:
    
17.                 return digits
    
18.         
    
19.         # 如果循环结束还有进位，说明最高位也进位了
    
20.         if carry:
    
21.             return [1] + digits
    
22.         
    
23.         return digits
    
24. 
    

复制代码

LC 1411. Number of Ways to Paint N × 3 Grid


一、这题本质是什么？
这是：

固定宽度（3列）的网格染色 DP
行与行之间做状态转移

关键特点：

• 行数 n 很大（5000）
• 列数固定（3）
• 每个格子 3 种颜色
• 上下左右不能相同

二、第一步：降维思想（最重要）
因为列数只有 3，
👉 每一行的合法状态是有限的（12种）
所以可以：

把二维问题压缩成“按行”的一维 DP

三、第二步：状态压缩
一行合法情况共 12 种，但可以分类：
🟢 类型1：ABA（两种颜色）
a b a
数量：
3 × 2 = 6


🔵 类型2：ABC（三种颜色）
a b c
数量：
3 × 2 × 1 = 6


所以：总 12 = 6 + 6

所以

            new_two = (three * 2 + two * 3) % MOD
            new_three = (three * 2 + two * 2) % MOD

这是系数转移矩阵


代码就比较简单了，


class Solution:
    def numOfWays(self, n: int) -> int:
        MOD = 10**9 + 7
        
        # 初始状态：第一行
        # three: 三色模式数量，two: 双色模式数量
        three = 6  # ABC, ACB, BAC, BCA, CAB, CBA
        two = 6    # ABA, BAB, ACA, CAC, BCB, CBC
        
        # 从第 2 行开始推导
        for i in range(2, n + 1):
            # 计算新的三色和双色数量
            new_two = (three * 2 + two * 3) % MOD
            new_three = (three * 2 + two * 2) % MOD
            
            
            # 更新状态
            three = new_three
            two = new_two
        
        # 答案是两种模式的总和
        return (three + two) % MOD

LC. 67. Add Binary

1. class Solution:
   
2.     def addBinary(self, a: str, b: str) -> str:
   
3.      if a == "0":
   
4.           return b
   
5.       if b == "0":
   
6.           return a
   
7.       return bin(int(a,base=2) + int(b,base=2))[2:]
   
8.                
   
9.         

复制代码

1. class Solution:
   
2.     def addBinary(self, a: str, b: str) -> str:
   
3.         n = max(len(a), len(b))
   
4.         a = a.zfill(n)
   
5.         b = b.zfill(n)
   
6. 
   
7.         carry = 0
   
8.         ans = []
   
9. 
   
10.         for i in range(n-1, -1, -1):
    
11.             if a[i] == "1":
    
12.                 carry += 1
    
13.             if b[i] == "1":
    
14.                 carry += 1
    
15. 
    
16.             if carry % 2 == 1:
    
17.                 ans.append("1")
    
18.             else:
    
19.                 ans.append("0")
    
20.             
    
21.             carry = carry // 2
    
22.         if carry == 1:
    
23.             ans.append("1")
    
24.         ans.reverse()
    
25. 
    
26.         return "".join(ans)

复制代码