刷题记录帖子

Myron2017

本帖最后由 Myron2017 于 2026-2-3 14:39 编辑

299. Bulls and Cows
Solved
Medium
Topics
conpanies icon
Companies
You are playing the Bulls and Cows game with your friend.

You write down a secret number and ask your friend to guess what the number is. When your friend makes a guess, you provide a hint with the following info:

The number of "bulls", which are digits in the guess that are in the correct position.
The number of "cows", which are digits in the guess that are in your secret number but are located in the wrong position. Specifically, the non-bull digits in the guess that could be rearranged such that they become bulls.
Given the secret number secret and your friend's guess guess, return the hint for your friend's guess.

The hint should be formatted as "xAyB", where x is the number of bulls and y is the number of cows. Note that both secret and guess may contain duplicate digits.

Example 1:

Input: secret = "1807", guess = "7810"
Output: "1A3B"
Explanation: Bulls are connected with a '|' and cows are underlined:
"1807"
|
"7810"

这个利用总配对数目减去 Bulls 的方法很妙

这是一个非常棒的问题！理解这一行代码的关键在于 Python 中 `collections.Counter` 对象的 **`&`（交集）运算符** 是如何定义的。

---

### 1. `&` 运算符在 Counter 中的定义

在 Python 的 `Counter` 中，两个计数器进行 `&` 运算时，它会取两个集合中**共有元素**的**最小频率**。

### 2. 为什么“最小值”等于“总配对数”？

我们可以把 `secret` 看作“供应方”，把 `guess` 看作“需求方”。

假设数字 `1`：

* 在 `secret` 中出现了 **3 次**（供应了 3 个 `1`）。
* 在 `guess` 中出现了 **5 次**（索要了 5 个 `1`）。

**结果：** 无论它们位置如何，你最多只能配对出 **3 个** `1`。剩下的 2 个 `1` 在 `guess` 中找不到匹配项。

### 3. 拆解示例

假设 `secret = "1122"`, `guess = "1222"`：

1. **s_count:** `{'1': 2, '2': 2}`
2. **g_count:** `{'1': 1, '2': 3}`
3. **s_count & g_count:**
* 对于 `'1'`:
* 对于 `'2'`:
* 结果为 `{'1': 1, '2': 2}`

4. **sum(...values()):** （这代表两个字符串中，数字完全相同的配对一共有 3 对）。

### 4. 为什么最后要减去 Bulls？

`total_matches` 统计的是**所有**数值匹配的数字，它包含了：

* **位置对的**（Bulls）
* **位置不对但数值对的**（Cows）

所以公式非常直观：

---

### 总结

`sum((s_count & g_count).values())` 实际上是在问：“如果不考虑位置，这两个字符串里到底有多少对数字是能对上的？” 这种写法利用了 Python 高级容器的特性，避免了手动写多层循环或判断逻辑。

这种思路在处理**字符串异位词 (Anagrams)** 相关的题目时也非常高效。需要我再举一个带重复数字的极端例子来帮你验证一下吗？

from collections import Counter
class Solution:
def getHint(self, secret: str, guess: str) -> str:
bulls = 0
# 找出所有 Bulls
for i in range(len(secret)):
if secret[i] == guess[i]:
bulls += 1
# 计算所有相同数字的总数（包括位置对的和位置不对的）
s_count = Counter(secret)
g_count = Counter(guess)
# 两个计数器的交集（取最小值）即为总匹配数
# 总匹配数 - Bulls = Cows
total_matches = sum((s_count & g_count).values())
cows = total_matches - bulls
return f"{bulls}A{cows}B"

复制代码

Myron2017

LC 3637. Trionic Array I

直接 walk along the array

class Solution:
def isTrionic(self, nums: List[int]) -> bool:
n = len(nums)
if n < 3: return False
i = 0
while i + 1 < n and nums[i+1] > nums[i]:
i += 1
# i does not move or i goes to the end
if i == 0 or i == n-1: return False
# check q
p = i
while i + 1 < n and nums[i+1] < nums[i]:
i += 1
# i does not move or i goes to the end
if i == p or i == n-1: return False
# check k
while i + 1 < n and nums[i+1] > nums[i]:
i += 1
# i does not reach the end of array
if i != n-1: return False
return True

复制代码

3640. Trionic Array II

class Solution:
def maxSumTrionic(self, nums: List[int]) -> int:
n = len(nums)
# 初始化为极小值
# s1: 严格递增段
# s2: 严格递增 + 严格递减
# s3: 严格递增 + 严格递减 + 严格递增 (最终目标)
s1 = s2 = s3 = -float('inf')
max_total = -float('inf')
for i in range(1, n):
curr = nums[i]
prev = nums[i-1]
# 准备当前步的状态
next_s1 = next_s2 = next_s3 = -float('inf')
# --- 阶段 1: 严格递增 (l...p) ---
if curr > prev:
# 或者是延续之前的 s1，或者是新起头 (prev, curr) 组成第一对
next_s1 = max(prev + curr, s1 + curr)
# --- 阶段 2: 严格递减 (p...q) ---
if curr < prev:
# 必须接在已经合法的 s1 后面，或者延续 s2
next_s2 = max(s1 + curr, s2 + curr)
# --- 阶段 3: 严格递增 (q...r) ---
if curr > prev:
# 必须接在已经合法的 s2 后面，或者延续 s3
next_s3 = max(s2 + curr, s3 + curr)
# 状态滚动更新
s1, s2, s3 = next_s1, next_s2, next_s3
max_total = max(max_total, s3)
return max_total

复制代码

Myron2017

本帖最后由 Myron2017 于 2026-2-3 16:29 编辑

LC 330. Patching Array

本质是最快的速度填补缺口。

结论是：在没有任何现有数字（即 nums 为空）的情况下，为了最快覆盖区间，我们补充的确实是 2 的次方。但如果有现有数字存在，补丁数就不一定是 2 的幂了。

我们可以从以下两个层面来理解：

1. 为什么是“2 的次方”？（二进制原理）
如果你手里有这些数字，你能组合出范围内的所有整数。这就是二进制的本质：任何正整数都可以表示为 2 的幂之和。

要填补，补 ()
要填补，补 ()
要填补，补 ()
... 依此类推。
在这种情况下，每补一个数，你的覆盖范围就翻倍。这是扩张速度最快的方式。

2. 当 nums 中有其他数字时，情况会改变
如果 nums 里原本就有数字，补丁就会和这些数字“合力”扩张，导致补丁不一定是 2 的幂。

**例子：nums = [1, 5], n = 20**

初始 miss = 1。看到 nums[0] = 1，匹配。miss 变为。
现在 miss = 2。下一个数 nums[1] = 5，太大（），断档了。
打补丁：补上当前的 miss，即 2。
现在的 miss 变为。
再看 nums[1] = 5。依然太大（），又断档了。
打补丁：补上当前的 miss，即 4。
现在的 miss 变为。
再看 nums[1] = 5。现在满足了！
miss 变为。
分析：在这个过程中，我们补了 2 和 4。但如果 nums 里原本有个 3，补丁序列就会完全不同。

3. 贪心算法的核心：补上“缺口”本身
这个算法之所以被称为“贪心”，是因为：每当我们发现无法覆盖 miss 时，我们就补上 miss 本身。

为什么补 miss？因为它是你能补的最大且合法的数字。
如果你补一个比 miss 大的数（比如 miss+1），那 miss 这个位置依然是空的，没解决问题。
如果你补一个比 miss 小的数，虽然能解决 miss 的缺口，但它能帮你推到的新边界（miss + 小数）不如补上 miss 推得远（miss + miss）。
总结
如果没有 nums 的干扰，补丁序列就是：（2 的幂）。
如果有 nums 的干扰，补丁序列是：当时的 miss 值。
这种“缺啥补啥，且补最大”的策略，保证了用最少的补丁数量达到目标。

你可以把这看作是“动态的二进制”：我们在不断地利用手头已有的数字，通过补上当前的“边界值”来实现范围的倍增。

我们要证明的是：如果 [1, miss - 1] 已经全覆盖，且 nums[i] <= miss，那么加入 nums[i] 后，[1, miss + nums[i] - 1] 也能全覆盖。

1. 场景设定
已知：我们已经可以用已有的数字，组合出 1, 2, 3, ..., 直到 (miss - 1)。

新数字： x = nums[i]。

条件： x <= miss。

2. 论证过程（区间合并）
我们可以把加入 x 后能表示的所有数字分成两组来看：

第一组：旧有的表达能力由于前提已知，我们可以表示出这个范围内的每一个数： [1, 2, 3, ..., miss - 1]

第二组：新数字 x 带来的新能力我们拿这个新数字 x，去加上第一组里的每一个数：

x + 1

x + 2

x + 3

...

x + (miss - 1) 这一组能表示的范围是：[x + 1, x + miss - 1]

3. 核心：为什么没有缝隙（Gap）？
我们要看第一组的终点和第二组的起点能不能连上。

第一组结束于：miss - 1

第二组开始于：x（注：x 本身也可以由新数字直接表示，如果 x 还没在第一组里的话）

连接点分析：只要第二组的起点 x 小于或等于第一组终点的下一位（也就是 miss），这两段数字序列就一定会重叠或者无缝相接。

因为题目条件规定了 x <= miss：

情况 A：如果 x = miss 第一组：[1, ..., miss-1] 第二组：[miss, ..., miss + miss - 1] (注：x + 0, x + 1...) 结果：刚好在 miss 这个点接上，覆盖范围变成 [1, 2 * miss - 1]。

情况 B：如果 x < miss 第一组：[1, ..., 5, 6, 7, 8, 9] (假设 miss=10) 第二组：[x, ..., x + 9] (假设 x=6) 结果：第二组从 6 就开始了，而第一组到 9 才结束。两组在 [6, 7, 8, 9] 这段区域重叠了。重叠意味着连接非常牢固，没有缝隙。

class Solution:
def minPatches(self, nums: List[int], n: int) -> int:
patches = 0
miss = 1 # 当前缺少的最小数字，即范围是 [1, miss)
i = 0 # 遍历 nums 的索引
while miss <= n:
if i < len(nums) and nums[i] <= miss:
# 现有数字可以帮我们扩展范围
miss += nums[i]
i += 1
else:
# 现有数字帮不上忙，必须打补丁
# 贪心地补上 miss 本身，使范围扩展最快
miss += miss
patches += 1
return patches

复制代码

Myron2017

3 SUM

class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort() # 1. 排序
n = len(nums)
ans = []
for i in range(n - 2):
# 优化 1：如果当前数字 > 0，后面都是正数，和不可能为 0
if nums[i] > 0:
break
# 优化 2：去重。如果这个数字和前一个一样，直接跳过
if i > 0 and nums[i] == nums[i - 1]:
continue
# 双指针部分
left = i + 1
right = n - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total < 0:
left += 1
elif total > 0:
right -= 1
else:
# 找到了！
ans.append([nums[i], nums[left], nums[right]])
# 关键：找到一组解后，left 和 right 都要跳过重复项
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
# 移动到下一个不同的数字
left += 1
right -= 1
return ans

复制代码

将 3Sum 的逻辑扩展到 4Sum 其实是一个非常规律的过程。你可以把它想象成一个“套娃”：

3Sum 是固定一个数，用双指针找剩下的两个数（）。
4Sum 就是固定两个数，用双指针找剩下的两个数（）。
以此类推，-Sum 的通用解法时间复杂度就是。

🛠️ 4Sum 的核心逻辑
我们设定四个指针：i（第一个数）、j（第二个数）、left（第三个数）、right（第四个数）。

排序是前提。
外层两层循环：固定 i 和 j。
内层双指针：在 j + 1 到 n - 1 的范围内寻找满足 nums[i] + nums[j] + nums[left] + nums[right] == target 的组合。
🐍 Python 实现（带极致剪枝）
由于在时计算量已经达到八百万次，所以**剪枝（Pruning）**在 4Sum 中不仅是优化，更是为了防止在某些极端测试用例下超时。

class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
      nums.sort()
      n = len(nums)
      ans = []

      for i in range(n - 3):
         # 1. 第一个数去重
         if i > 0 and nums[i] == nums[i - 1]:
            continue

         # --- 极致剪枝 ---
         # 如果当前最小的四个数相加都大于目标，后面不用看了
         if nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target:
            break
         # 如果当前数加上最大的三个数都够不到目标，尝试下一个 i
         if nums[i] + nums[n-3] + nums[n-2] + nums[n-1] < target:
            continue

         for j in range(i + 1, n - 2):
            # 2. 第二个数去重
            if j > i + 1 and nums[j] == nums[j - 1]:
                  continue

            # --- 极致剪枝（针对 j） ---
            if nums[i] + nums[j] + nums[j+1] + nums[j+2] > target:
                  break
            if nums[i] + nums[j] + nums[n-2] + nums[n-1] < target:
                  continue

            # 3. 双指针找剩下两个
            left, right = j + 1, n - 1
            while left < right:
                  curr_sum = nums[i] + nums[j] + nums[left] + nums[right]
                  if curr_sum == target:
                     ans.append([nums[i], nums[j], nums[left], nums[right]])
                     # 找到后移动并去重
                     left += 1
                     while left < right and nums[left] == nums[left - 1]:
                        left += 1
                     right -= 1
                     while left < right and nums[right] == nums[right + 1]:
                        right -= 1
                  elif curr_sum < target:
                     left += 1
                  else:
                     right -= 1
      return ans

🧠 为什么 4Sum 比 3Sum 难？
并不是逻辑更难，而是细节和边界处理变得更多：

去重逻辑的范围：j 的去重判断必须是 j > i + 1，这是为了保证在 i 固定时，j 可以取 i 之后的第一个数，但不能取两个相同的 j。
溢出风险：在一些编程语言（如 Java/C++）中，四个整数相加可能会超出 int 的范围（题目约束是级别），Python 虽然处理了大整数，但在其他语言中需要用 long。
剪枝的必要性：4Sum 的面对大规模数据时比较吃力，上面的“最大值/最小值”剪枝能让代码提速 10 倍以上。
💡 延伸：如何写出通用的 k-Sum？
如果你掌握了这种递归的思想，你可以写出一个函数来处理任意的情况：

Base Case: 时，使用双指针。
Recursive Step: 对于，循环固定当前的第一个数，然后递归调用 -Sum。
你会发现这是一种非常高级的编程思维：将一个复杂的高维问题，不断降维打击，最后变成最基础的双指针。

Myron2017

LC 4. Median of Two Sorted Arrays

class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
# 确保 nums1 是较短的数组，这样二分查找更快，且 j 不会变成负数
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
low, high = 0, m
half_len = (m + n + 1) // 2
while low <= high:
i = (low + high) // 2 # nums1 的切口
j = half_len - i # nums2 的切口
# 边界处理：如果切口在最左或最右，用正负无穷表示
nums1_left_max = nums1[i-1] if i > 0 else float('-inf')
nums1_right_min = nums1[i] if i < m else float('inf')
nums2_left_max = nums2[j-1] if j > 0 else float('-inf')
nums2_right_min = nums2[j] if j < n else float('inf')
# 检查是否满足交叉小于等于条件
if nums1_left_max <= nums2_right_min and nums2_left_max <= nums1_right_min:
# 找到了完美切口！
if (m + n) % 2 == 1:
# 奇数情况：左半部分的最大值就是中位数
return max(nums1_left_max, nums2_left_max)
else:
# 偶数情况：(左半最大 + 右半最小) / 2
return (max(nums1_left_max, nums2_left_max) +
min(nums1_right_min, nums2_right_min)) / 2.0
elif nums1_left_max > nums2_right_min:
# nums1 的左边太大，切口往左移
high = i - 1
else:
# nums1 的左边太小，切口往右移
low = i + 1

复制代码

这是一个非常精妙的数学细节，主要为了统一处理奇数和偶数的情况，让代码逻辑更简洁。我们可以从以下两个维度来拆解这个公式：1. 为什么有个 + 1？这个 + 1 的核心作用是：当总长度为奇数时，让左半部分比右半部分多出一个元素。偶数情况 ($m+n=4$)：$(4 + 1) // 2 = 2$。左半部分有 2 个元素，右半部分有 2 个元素。完美平分。奇数情况 ($m+n=5$)：$(5 + 1) // 2 = 3$。左半部分有 3 个元素，右半部分有 2 个元素。为什么要让左边多一个？因为这样规定后，如果总数是奇数，中位数就一定会落在左半部分的最大值中（即 max(nums1_left_max, nums2_left_max)）。如果不加这个 1，中位数可能会跑到右边，或者你需要写两套逻辑来判断中位数在哪。2. 为什么用 // 2 而不是具体的索引？在二分查找中，i 是我们在 nums1 中划下的“刀口”位置：i 代表 nums1 中被分到左半部分的元素个数。j 代表 nums2 中被分到左半部分的元素个数。为了保证总的左半部分长度等于 half_len，必须满足：i + j = half_len所以我们可以直接推导出 j = half_len - i。3. 实例对比（直观感受）假设有两个数组，总长度 $L = m + n$。总长度 L公式 (L+1)//2左半部分长度右半部分长度说明4 (偶)$(4+1)//2 = 2$22左右均等，中位数取 (左max + 右min)/25 (奇)$(5+1)//2 = 3$32左边多1个，中位数就是左max1 (奇)$(1+1)//2 = 1$10左边就是那个唯一的数，即中位数4. 这种写法带来的代码优势如果不使用 (m + n + 1) // 2，你的代码可能会变成这样：Pythonif total_len % 2 == 1:
half_len = total_len // 2
# 后面还要处理中位数是在右边最小还是左边最大...
else:
half_len = total_len // 2
而有了这个公式，无论奇偶，你只需要在最后 return 时判断一下：奇数：直接返回左边最大的。偶数：返回 (左边最大 + 右边最小) / 2。一句话总结：这个 + 1 是一个“占位符”，它强制让奇数情况下的中位数归入左侧，从而消灭了复杂的条件判断。

整体思路

这道题是 LeetCode 中最著名的 **Hard** 题之一。它最难的地方在于：**合并两个有序数组很简单，但题目要求时间复杂度必须是。**

这意味着你**不能遍历**整个数组（），必须使用类似**二分查找**的思路。

---

### 1. 直观理解：中位数的本质是什么？

中位数的任务是把一个集合划分为**长度相等**的左右两部分，且**左边的所有数  右边的所有数**。

对于两个数组  (长度 ) 和  (长度 )，我们要在  中切一刀，在  中也切一刀：

*  被切成  和
*  被切成  和

我们将  和  组合成“大左半部分”，将  和  组合成“大右半部分”。

### 2. 我们要找的“完美切口”

要让这两个切口正好定位到中位数，必须满足两个条件：

1. **左右数量相等**：

（如果总数是奇数，左边比右边多一个）。
2. **交叉小于等于**（关键点）：
*  （左边最大的数  右边最小的数）
*  （左边最大的数  右边最小的数）

因为  和  本身是有序的，所以只要满足这两个**交叉条件**，就能保证“大左半部分”的所有数都小于等于“大右半部分”。

---

### 3. 为什么是？

由于两个数组的总长度是固定的，所以**只要  数组的切口  确定了，数组的切口  也就自动确定了**。
公式：

我们可以只在**较短的那个数组**上进行二分查找。

* 如果，说明  的切口太靠右了，往左移。
* 如果，说明  的切口太靠左了，往右移。

---

### 4. 🐍 Python 代码实现

```python
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
      # 确保 nums1 是较短的数组，这样二分查找更快，且 j 不会变成负数
      if len(nums1) > len(nums2):
         nums1, nums2 = nums2, nums1

      m, n = len(nums1), len(nums2)
      low, high = 0, m
      half_len = (m + n + 1) // 2

      while low <= high:
         i = (low + high) // 2  # nums1 的切口
         j = half_len - i    # nums2 的切口

         # 边界处理：如果切口在最左或最右，用正负无穷表示
         nums1_left_max = nums1[i-1] if i > 0 else float('-inf')
         nums1_right_min = nums1[i] if i < m else float('inf')
         nums2_left_max = nums2[j-1] if j > 0 else float('-inf')
         nums2_right_min = nums2[j] if j < n else float('inf')

         # 检查是否满足交叉小于等于条件
         if nums1_left_max <= nums2_right_min and nums2_left_max <= nums1_right_min:
            # 找到了完美切口！
            if (m + n) % 2 == 1:
                  # 奇数情况：左半部分的最大值就是中位数
                  return max(nums1_left_max, nums2_left_max)
            else:
                  # 偶数情况：(左半最大 + 右半最小) / 2
                  return (max(nums1_left_max, nums2_left_max) +
                        min(nums1_right_min, nums2_right_min)) / 2.0

         elif nums1_left_max > nums2_right_min:
            # nums1 的左边太大，切口往左移
            high = i - 1
         else:
            # nums1 的左边太小，切口往右移
            low = i + 1

```

---

### 5. 理解难点：边界处理

在代码中，你会看到 `float('-inf')` 和 `float('inf')`。

* **为什么？** 当切口  时，表示  数组全部被划到了右半部分。此时  没有元素，为了不影响 `max` 的比较，我们假装左边有一个无穷小的数。
* 反之，当  时，表示  全部在左边，我们假装右边有一个无穷大的数。

### 总结

1. **核心思想**：通过二分查找在一个数组中寻找切口，利用两个数组的比例关系自动确定另一个切口。
2. **关键条件**：确保切口两端的四个数满足交叉递增关系。
3. **效率**：因为只对短数组进行二分，复杂度是，完全符合题目要求。

这道题是“二分思想”的最高级应用之一。你觉得这个“切蛋糕”的逻辑，是否比直接合并数组要清晰一些？如果有具体的边界情况（比如一个数组为空）想不通，我们可以代入一组数据跑一遍。

Myron2017

LC 56. Merge Intervals

class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals = sorted(intervals, key = lambda x: (x[0]))
merged = []
for interval in intervals:
if not merged or merged[-1][1] < interval[0]:
# process empty merged and non-overlapping cases
merged.append(interval)
else:
merged[-1][1] = max(merged[-1][1], interval[1])
return merged

复制代码

核心思想就是：把有重叠的小区间“粘”在一起，变成一个大区间。

为了理解这道题，我们可以把它想象成在一根数轴上画线段。

💡 解题核心思路：排序是关键
如果这些区间是乱序的（比如 Example 3），我们很难一眼看出谁该和谁合并。所以，第一步永远是按起始位置（start）从小到大排序。

排序后，合并的逻辑就变得非常简单：

初始化：创建一个空的结果列表 merged。

遍历：按顺序检查每一个区间。

如果不重叠：如果当前区间的 start 大于结果列表中最后一个区间的 end，说明它们没法连上。直接把当前区间加入结果列表。

如果重叠：如果当前区间的 start 小于或等于结果列表中最后一个区间的 end，说明它们连在一起了。这时，我们更新结果列表中最后一个区间的 end，取它自己和当前区间 end 的最大值。

在遍历原始 intervals 列表的过程中，我们只观察 merged 列表中的最后一个元素。

你可以把 merged 想象成一个栈（Stack）：我们始终只拿当前的区间和栈顶（最新的合并结果）进行比对。

🧐 为什么不需要遍历整个 merged？
这正是排序（Sort）的威力所在。

有序性：因为我们已经按 start 排序了，所以对于任何新进来的区间 intervals[i]，它的起点一定大于或等于 merged 中所有区间的起点。

邻接性：如果 intervals[i] 会和前面的区间产生重叠，它只会和 merged 中最后一个区间产生重叠。它不可能跨过最后一个区间去和更前面的区间重叠，而又不与最后一个重叠。

形象的比喻：
想象你在排队领礼品，每个人手里拿一段绳子。

因为大家按“绳子起点”排好了队。

你进来时，只需要看你手里绳子的开头，能不能接上排在你前面那个人的绳子尾部。

你不需要去问队伍最前面的那个人，因为如果你的绳子能连上最前面的人，那么你中间的所有人肯定早就已经连在一起了。

请看这个判断条件：

Python
if not merged or merged[-1][1] < interval[0]:
merged.append(interval)
else:
merged[-1][1] = max(merged[-1][1], interval[1])
这里的 or 是有**短路效应（Short-circuiting）**的：

第一次循环时：merged 是空的，not merged 为 True。

短路发生：由于 True or ... 永远是 True，程序不会去计算 or 后面的 merged[-1][1]。

安全执行：程序直接跳到 merged.append(interval)，把第一个区间存进去。

后续循环：此时 merged 不再为空，not merged 为 False，程序才会去检查 merged[-1][1]。

Myron2017

3314. Construct the Minimum Bitwise Array I
3315. Construct the Minimum Bitwise Array II

class Solution:
def minBitwiseArray(self, nums: List[int]) -> List[int]:
for i in range(len(nums)):
res = -1
d = 1
while (nums[i] & d) != 0:
res = nums[i] - d
d <<= 1
nums[i] = res
return nums

复制代码

核心逻辑拆解位运算规律 $x \text{ OR } (x + 1)$ 的效果实际上是：将数字 $x$ 二进制表示中最右边（低位）的第一个 0 变成 1。比如：如果 $x = 1010_2$ (10)，那么 $x+1 = 1011_2$，结果是 $1011_2$ (11)。如果 $x = 1011_2$ (11)，那么 $x+1 = 1100_2$，结果是 $1111_2$ (15)。代码的工作流程：遍历数组：对每个 nums[i] 进行处理。寻找最低位的连续 1：res = -1: 默认值。如果 nums[i] 是偶数（二进制末尾是 0），循环不会执行，直接返回 -1。因为偶数不可能由 $x \text{ OR } (x + 1)$ 得到（结果一定是奇数）。while (nums[i] & d) != 0: 这个循环在检查 nums[i] 的二进制位，从右往左看，直到遇到第一个 0。res = nums[i] - d: 这里的 d 代表当前位的值（1, 2, 4, 8...）。每遇到一个末尾的连续 1，就尝试把这个位置变为 0。d <<= 1: d 左移一位，继续检查更高位。

Myron2017

2446. Determine if Two Events Have Conflict

class Solution:
def haveConflict(self, event1: List[str], event2: List[str]) -> bool:
if event1[0] > event2[0]:
event1, event2 = event2, event1
# so event1 starts early
# we only need to check event2
if event2[0] >= event1[0] and event2[0] <= event1[1]:
return True
else:
return False

复制代码

Myron2017

LC 3323. Minimize Connected Groups by Inserting Interval

You are given a 2D array intervals, where intervals[i] = [starti, endi] represents the start and the end of interval i. You are also given an integer k.

You must add exactly one new interval [startnew, endnew] to the array such that:

The length of the new interval, endnew - startnew, is at most k.
After adding, the number of connected groups in intervals is minimized.
A connected group of intervals is a maximal collection of intervals that, when considered together, cover a continuous range from the smallest point to the largest point with no gaps between them. Here are some examples:

A group of intervals [[1, 2], [2, 5], [3, 3]] is connected because together they cover the range from 1 to 5 without any gaps.
However, a group of intervals [[1, 2], [3, 4]] is not connected because the segment (2, 3) is not covered.
Return the minimum number of connected groups after adding exactly one new interval to the array.

Example 1:

Input: intervals = [[1,3],[5,6],[8,10]], k = 3

Output: 2

Explanation:

After adding the interval [3, 5], we have two connected groups: [[1, 3], [3, 5], [5, 6]] and [[8, 10]].

Example 2:

Input: intervals = [[5,10],[1,1],[3,3]], k = 1

Output: 3

Explanation:

After adding the interval [1, 1], we have three connected groups: [[1, 1], [1, 1]], [[3, 3]], and [[5, 10]].

Constraints:

1 <= intervals.length <= 105
intervals[i] == [starti, endi]
1 <= starti <= endi <= 109
1 <= k <= 109

class Solution:
def minConnectedGroups(self, intervals: List[List[int]], k: int) -> int:
# sort intervals
intervals = sorted(intervals, key = lambda x: x[0])
# merge all existing connected intervals since they do not need to be connected
merged = []
for interval in intervals:
if not merged or interval[0] > merged[-1][1]:
# safe to add, not merged --> empty list at begining, and gapped intervals
merged.append(interval)
else:
# merge connected intervals
merged[-1][1] = max(merged[-1][1], interval[1])
# check intervals can be linked by k
ans = len(merged) # worset case no new connecte groups, like gap too wide
n = len(merged)
l = 0
r = l + 1
while l < n:
while r < n and (merged[r][0] - merged[l][1] <= k):
ans = min(ans, n - (r-l))
r += 1
l += 1
return ans

复制代码

原始代码超时， TLE，因为内部两层嵌套，

while l < n:
r = l + 1
while r < n and (merged[r][0] - merged[l][1] <= k):
ans = min(ans, n - (r - l)) # 这里的 r 每次都从 l+1 开始重扫
r += 1
l += 1

复制代码

即使你的逻辑对，但如果 $k$ 很大，内部的 while r < n 可能会运行成千上万次。对于每一个 l，你都让 r 重新出发，这在计算机看来太累了。优化方案：滑动窗口 (Sliding Window)其实 r 并不需要每次都回到 l + 1。由于 merged 数组已经是按顺序排好的，当 l 向右移动时，merged[l][1] 也会变大。这意味着原本能被 l 覆盖到的 r，肯定也能被 l+1 覆盖到。因此，r 只需要一路向右，永不回头。这样复杂度就降到了 $O(N)$。

改动一行代码即可，把 r = l + 1 挪到 while l 的循环外即可。

Myron2017

LC 76. Minimum Window Substring

这题的“记忆口诀”

右扩找合法，左缩求最短
频次刚好等，valid 才变化

你以后只要看到：

最短 / 覆盖

字符频次

子串问题

第一反应就应该是：76 号题的这个模板

class Solution:
def minWindow(self, s: str, t: str) -> str:
freq_t = Counter(t)
freq_current_window = defaultdict(int)
is_valid = 0
l, r = 0, 0
min_len = float('inf')
ans = ""
n = len(s)
while r < n:
# processing right end char
ch = s[r]
# update current window statistics
freq_current_window[ch] += 1
if ch in freq_t:
# if ch makes valid string
if freq_current_window[ch] == freq_t[ch]:
is_valid += 1
# check if found all char in t
while is_valid == len(freq_t):
# update min substring len
# substring starts at l
# and keep moving l to left to see if we can reduce string length more
curr_window_length = r - l + 1
if curr_window_length < min_len:
min_len = curr_window_length
ans = s[l:r+1]
# move l to l+1
ch_left = s[l]
if ch_left in freq_t and freq_current_window[ch_left] == freq_t[ch_left]:
# only reduce is_valid if this is a critical char
is_valid -= 1
freq_current_window[ch_left] -= 1
l += 1
# update right point
r +=1
return ans

复制代码

一、题目核心思路（一句话版）

用滑动窗口在 s 中找一个最短子串，使其“完全覆盖” t 中所有字符及其出现次数。

关键词只有三个：

覆盖（不是包含子序列）

最短

字符有重复

二、正确的算法模型（这是关键）
1️⃣ 滑动窗口 + 频次统计

这是一个「可扩展、可收缩」的窗口问题：

右指针 r：负责把字符「放进窗口」

左指针 l：在满足条件后，尽量「缩小窗口」

2️⃣ 维护两个核心统计量
（1）需求表 freq_t
freq_t = Counter(t)

表示：

每个字符在窗口中至少需要出现多少次

（2）窗口表 freq_window
freq_window = defaultdict(int)

表示：

当前窗口内，每个字符出现了多少次

3️⃣ 一个非常关键的变量：is_valid
is_valid = 当前“满足需求”的字符种类数

规则：

当某个字符 c：

freq_window[c] == freq_t[c]

才算这个字符达标

每个字符只在“第一次达标”时 +1

终止条件：

is_valid == len(freq_t)

👉 表示所有字符都已经满足

三、算法执行流程（标准模板）
Step 1：右指针扩张窗口

加入 s[r]

更新频次

如果刚好满足某字符需求 → is_valid += 1

Step 2：窗口满足条件 → 左指针收缩

当：

is_valid == len(freq_t)

做三件事：

更新最短答案

尝试缩小窗口（l += 1）

如果移除的是“关键字符”，让窗口失效

Step 3：继续向右探索

直到遍历完整个 s

刷题记录帖子

浏览过的版块