刷题记录帖子

LC 1004. Max Consecutive Ones III

和上一道题目是类似的解法。

1. class Solution:
   
2.     def longestOnes(self, nums: List[int], k: int) -> int:
   
3.         count_w = [0, 0]
   
4.         left, right = 0, 0
   
5.         max_len = 0
   
6. 
   
7.         while right < len(nums):
   
8.             count_w[nums[right]] += 1
   
9.             len_w = right - left + 1
   
10.             changes = len_w - count_w[1] # how many zeros needs to be changed
    
11. 
    
12.             if changes <= k:
    
13.                 # valid window, update max_len
    
14.                 max_len = max(max_len, len_w)
    
15.                 right += 1 # expand window
    
16.             else:
    
17.                 # invalid window, move window to right
    
18.                 count_w[nums[left]] -= 1
    
19.                 left += 1
    
20.                 right += 1
    
21.         return max_len
    
22. 
    
23. 
    
24.         

复制代码

LC 3634. Minimum Removals to Balance Array

删除最少 = 保留最多
目标：max ≤ k × min
转化：找最长的满足条件的子数组


一句话总结
排序 + 滑动窗口找最长满足 max ≤ k×min 的子数组，删除数 = n - 最长长度

1. class Solution:
   
2.     def minRemoval(self, nums: List[int], k: int) -> int:
   
3.         n = len(nums)
   
4.         if n == 1:
   
5.             return 0
   
6.         
   
7.         nums.sort()
   
8.         
   
9.         left = 0
   
10.         max_len = 0
    
11.         
    
12.         for right in range(n):
    
13.             # 不合法时收缩：max > k × min
    
14.             while left <= right and nums[right] > k * nums[left]:
    
15.                 left += 1
    
16.             
    
17.             # 窗口合法
    
18.             if left <= right:
    
19.                 max_len = max(max_len, right - left + 1)
    
20.         
    
21.         return n - max_len

复制代码

LC 1482. Minimum Number of Days to Make m Bouquets核心思路

单调性 → 二分搜索天数 → 每次检查能否做出 m 个花束

二分搜索天数，每次检查该天能否凑出 m 个 k 朵连续花的花束，关键是遇到未开的花要重置连续计数。

1. class Solution:
   
2.     def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
   
3.         n = len(bloomDay)
   
4.         
   
5.         # 不可能的情况
   
6.         if m * k > n: return -1
   
7.         
   
8.         # 二分搜索天数
   
9.         left, right = min(bloomDay), max(bloomDay)
   
10.         
    
11.         while left < right:
    
12.             mid = (left + right) // 2
    
13.             
    
14.             if self.canMake(bloomDay, mid, m, k):
    
15.                 right = mid  # 可以做出，尝试更少天数
    
16.             else:
    
17.                 left = mid + 1  # 需要更多天数
    
18.         
    
19.         return left
    
20.    
    
21.     def canMake(self, bloomDay: List[int], day: int, m: int, k: int) -> bool:
    
22.         """检查第 day 天能否做出 m 个花束"""
    
23.         bouquets = 0
    
24.         flowers = 0
    
25.         
    
26.         for bloom in bloomDay:
    
27.             if bloom <= day:
    
28.                 flowers += 1
    
29.                 if flowers == k:
    
30.                     bouquets += 1
    
31.                     flowers = 0
    
32.                     if bouquets >= m:  # 提前返回优化
    
33.                         return True
    
34.             else:
    
35.                 flowers = 0
    
36.         
    
37.         return bouquets >= m

复制代码

LC 1011. Capacity To Ship Packages Within D Days

这道题用二分搜索船的最小容量。
下界是 max(weights)，上界是 sum(weights)。


因为每个包裹不能给拆分了，所以船最小必须比最大的包裹大！

对每个容量，用贪心模拟装货，统计需要多少天，判断是否 ≤ days。

1. class Solution:
   
2.     def shipWithinDays(self, weights: List[int], days: int) -> int:
   
3. 
   
4. 
   
5.         def canShipWithinDays(capacity):
   
6.             used_days = 0
   
7.             curr_sum_weight = 0
   
8.             for w in weights:
   
9.                 curr_sum_weight += w
   
10.                 if curr_sum_weight > capacity:
    
11.                     used_days += 1
    
12.                     if used_days > days: return False
    
13.                     curr_sum_weight = w
    
14.             used_days += 1 # update 1 due to remaining packages
    
15.             return used_days <= days
    
16.         
    
17.         left, right = max(weights), sum(weights)
    
18. 
    
19.         while left < right:
    
20.             mid = (left + right) // 2
    
21.             if canShipWithinDays(mid):
    
22.                 right = mid
    
23.             else:
    
24.                 left = mid + 1
    
25.         
    
26.         return left
    
27. 
    
28. 
    
29.         

复制代码

LC 1283. Find the Smallest Divisor Given a Threshold

1. class Solution:
   
2.     def smallestDivisor(self, nums: List[int], threshold: int) -> int:
   
3. 
   
4.         def isSumUnderThreshold(divisor):
   
5.             res = 0
   
6.             for num in nums:
   
7.                 res += math.ceil(num / divisor)
   
8.             return res <= threshold
   
9. 
   
10.         left, right = 1, max(nums)
    
11. 
    
12.         while left < right:
    
13.             mid = (left + right) // 2
    
14.             if isSumUnderThreshold(mid):
    
15.                 right = mid
    
16.             else:
    
17.                 left = mid + 1
    
18.         return left
    
19. 
    
20.         

复制代码

LC 1552. Magnetic Force Between Two Balls

三句话总结（1552 Magnetic Force）

1️⃣ 这道题是最大化最小值问题，可以转化为：给定最小距离 d，是否能放下 m 个球。
2️⃣ 因为 d 越小越容易、越大越困难，check(d) 具有单调性，所以可以对答案进行二分搜索。
3️⃣ 在 check 中用贪心策略：始终把球放在能放的最左位置，并且每次都与上一次放球的真实坐标比较距离。

1. class Solution:
   
2.     def maxDistance(self, position: List[int], m: int) -> int:
   
3.         """
   
4.         整体思路：
   
5.         1. 这是一道「最大化最小值」的问题，答案是最小磁力 d
   
6.         2. 固定一个 d，可以用贪心判断是否能放下 m 个球（check(d)）
   
7.         3. 因为 d 越小越容易、d 越大越困难，check(d) 具有单调性
   
8.         4. 对 d 进行二分搜索，找最大的可行 d
   
9.         """
   
10. 
    
11.         # 先排序，方便从左到右贪心放球
    
12.         position.sort()
    
13.         n = len(position)
    
14. 
    
15.         def isDPossibleForMBall(d):
    
16.             """
    
17.             判断是否能保证任意两个球之间的距离 >= d
    
18.             贪心策略：始终把球放在「能放的最左位置」
    
19.             """
    
20.             # 第一个球放在最左边的篮子
    
21.             last_pos = position[0]
    
22.             curr_ball_put = 1
    
23. 
    
24.             # 从第二个篮子开始尝试放球
    
25.             for i in range(1, n):
    
26.                 # 当前位置和上一次放球的位置距离是否满足 d
    
27.                 if position[i] - last_pos >= d:
    
28.                     curr_ball_put += 1
    
29.                     # 更新上一次放球的“坐标值”（不是索引）
    
30.                     last_pos = position[i]
    
31. 
    
32.                     # 已经放下 m 个球，提前返回
    
33.                     if curr_ball_put >= m:
    
34.                         return True
    
35. 
    
36.             return False
    
37. 
    
38.         # d 的搜索范围：
    
39.         # 最小为 1，最大为最右和最左篮子的距离
    
40.         left, right = 1, position[-1] - position[0]
    
41. 
    
42.         # 二分查找「最大的可行 d」
    
43.         while left < right:
    
44.             # 取上中位数，避免死循环
    
45.             mid = (left + right + 1) // 2
    
46. 
    
47.             if isDPossibleForMBall(mid):
    
48.                 # mid 可行，尝试更大的最小距离
    
49.                 left = mid
    
50.             else:
    
51.                 # mid 不可行，缩小右边界
    
52.                 right = mid - 1
    
53. 
    
54.         return left
    

复制代码

LC. 1891. Cutting Ribbons

类似上一题思路，还是最大可行值。

注意排除下，完全 cut 不出来彩带的情况！

You are given an integer array ribbons, where ribbons[i] represents the length of the ith ribbon, and an integer k. You may cut any of the ribbons into any number of segments of positive integer lengths, or perform no cuts at all.

For example, if you have a ribbon of length 4, you can:
Keep the ribbon of length 4,
Cut it into one ribbon of length 3 and one ribbon of length 1,
Cut it into two ribbons of length 2,
Cut it into one ribbon of length 2 and two ribbons of length 1, or
Cut it into four ribbons of length 1.
Your task is to determine the maximum length of ribbon, x, that allows you to cut at least k ribbons, each of length x. You can discard any leftover ribbon from the cuts. If it is impossible to cut k ribbons of the same length, return 0.



Example 1:

Input: ribbons = [9,7,5], k = 3
Output: 5
Explanation:
- Cut the first ribbon to two ribbons, one of length 5 and one of length 4.
- Cut the second ribbon to two ribbons, one of length 5 and one of length 2.
- Keep the third ribbon as it is.
Now you have 3 ribbons of length 5.
Example 2:

Input: ribbons = [7,5,9], k = 4
Output: 4
Explanation:
- Cut the first ribbon to two ribbons, one of length 4 and one of length 3.
- Cut the second ribbon to two ribbons, one of length 4 and one of length 1.
- Cut the third ribbon to three ribbons, two of length 4 and one of length 1.
Now you have 4 ribbons of length 4.
Example 3:

Input: ribbons = [5,7,9], k = 22
Output: 0
Explanation: You cannot obtain k ribbons of the same positive integer length.


Constraints:

1 <= ribbons.length <= 105
1 <= ribbons[i] <= 105
1 <= k <= 109

1. class Solution:
   
2.     def maxLength(self, ribbons: List[int], k: int) -> int:
   
3.         """
   
4.         if X is very samll, True
   
5.         so X has a limit, X max is max(ribbons)
   
6.         check(x): for each robion, cut to x as much as possible, and then see if k ribbons satisfiy with length x
   
7.         """
   
8.         if sum(ribbons) < k: return 0
   
9. 
   
10.         def isKRibbonsPossible(x):
    
11.             curr_x_ribbons = 0
    
12.             for r in ribbons:
    
13.                 if r >= x:
    
14.                     curr_x_ribbons += r//x
    
15.                 if curr_x_ribbons >= k: return True
    
16.             return False
    
17.         
    
18.         left, right = 1, max(ribbons)
    
19.         while left < right:
    
20.             mid = (left + right + 1) // 2
    
21.             if isKRibbonsPossible(mid):
    
22.                 left = mid
    
23.             else:
    
24.                 right = mid - 1
    
25.         return left

复制代码

LC. 2226. Maximum Candies Allocated to K Children

Same questions

1. class Solution:
   
2.     def maximumCandies(self, candies: List[int], k: int) -> int:
   
3.         if sum(candies) < k: return 0
   
4. 
   
5.         """
   
6. 
   
7.         Assume each child get d candies
   
8. 
   
9.         then for each pile of candies, arrange it into subpiles of d candies
   
10.         compare with k
    
11. 
    
12.         binary search for largest possible d
    
13. 
    
14.         """
    
15. 
    
16.         def isPossible(d):
    
17.             curr_sub_piles = 0
    
18.             for c in candies:
    
19.                 if c >= d:
    
20.                     curr_sub_piles += c//d
    
21.                 if curr_sub_piles >= k: return True
    
22.             return False
    
23.         
    
24.         left, right = 1, max(candies)
    
25. 
    
26.         while left < right:
    
27.             mid = (left + right + 1) // 2
    
28.             if isPossible(mid):
    
29.                 left = mid
    
30.             else:
    
31.                 right = mid - 1
    
32.         return left
    
33.         
    
34. 
    
35.         

复制代码

LC 410. Split Array Largest Sum

✅ 总结经验

本题核心思想

题目要求把数组分成 k 段，使得每段的和的 最大值最小化 → 这是一个典型的 二分答案（binary search on answer）问题。

核心是定义一个 check 函数：给定一个候选最大段和 d，判断能否把数组切成 ≤ k 段，每段和 ≤ d。

check 函数设计

从左往右累加数组元素，如果当前段加上新元素超过 d，则开新段。

如果最终段数 ≤ k，则 d 是可行的；否则 d 太小，不可行。

二分思路

左边界 left = max(nums)：最小可行的 d 不可能小于数组最大元素。

右边界 right = sum(nums)：最大可行的 d 不可能超过整个数组和。

每次取 mid = (left + right) // 2，判断 mid 是否可行：

可行 → 尝试更小的 d → right = mid

不可行 → d 太小 → left = mid + 1

返回 left，就是最小的可行最大段和。

边界注意点

数组只有一个元素或 k = 1 的特殊情况直接返回。

check 函数计数从 1 开始，因为至少有一段。

1. class Solution:
   
2.     def splitArray(self, nums: List[int], k: int) -> int:
   
3.         """
   
4.         思路：
   
5.         - 我们要找到数组分成 k 段时，最大段和的最小值。
   
6.         - 使用二分答案法：二分搜索最大段和 d 的最小可行值。
   
7.         - check(d) 函数判断能否把数组切成 <= k 段，每段和 <= d。
   
8.         """
   
9. 
   
10.         # 边界情况
    
11.         if k == 1:  # 只能一段，最大段和就是数组总和
    
12.             return sum(nums)
    
13.         if len(nums) == 1:  # 数组只有一个元素，直接返回它
    
14.             return nums[0]
    
15. 
    
16.         def check(d: int) -> bool:
    
17.             """
    
18.             判断是否存在 <= k 段，使得每段和 <= d
    
19.             """
    
20.             count_subarr = 1  # 当前已经使用的段数，从 1 开始
    
21.             curr_subarry_sum = 0  # 当前段的累加和
    
22.             for num in nums:
    
23.                 if curr_subarry_sum + num > d:
    
24.                     # 超过当前最大段和，开新段
    
25.                     count_subarr += 1
    
26.                     curr_subarry_sum = num  # 新段初始值为当前元素
    
27.                 else:
    
28.                     curr_subarry_sum += num
    
29.                 if count_subarr > k:  # 已经超过 k 段 → d 不可行
    
30.                     return False
    
31.             return True  # 能在 k 段内完成 → d 可行
    
32. 
    
33.         # 二分搜索最大段和的最小可行值
    
34.         left = max(nums)   # d 最小不能小于数组最大元素
    
35.         right = sum(nums)  # d 最大不会超过整个数组和
    
36. 
    
37.         while left < right:
    
38.             mid = (left + right) // 2  # 候选最大段和
    
39.             if check(mid):
    
40.                 right = mid  # mid 可行，尝试更小的 d
    
41.             else:
    
42.                 left = mid + 1  # mid 不可行，d 太小
    
43. 
    
44.         return left  # 最小可行的最大段和
    

复制代码

LC 2943. Maximize Area of Square Hole in Grid

这道题目，其实说穿了很简单。 题目说得需要理解，面试的时候可以多问问面试官。

当然了，这个我也能理解，就是在考察所谓的 Problem Solving Ability，不过这太无语了。

移除 k 条连续的条 → 形成 k+1 的间隙 → 正方形取两个方向的 min！