刷题记录帖子

LC. 3986. Number of Elapsed Seconds Between Two Times

You are given two valid times startTime and endTime, each represented as a string in the format "HH:MM:SS".

Return the number of seconds that have elapsed from startTime to endTime.



Example 1:

Input: startTime = "01:00:00", endTime = "01:00:25"

Output: 25

Explanation:

endTime is 25 seconds ahead of startTime.
Example 2:

Input: startTime = "12:34:56", endTime = "13:00:00"

Output: 1504

Explanation:

endTime is 25 minutes and 4 seconds ahead of startTime, which equals 1504 seconds.



Constraints:

startTime.length == 8
endTime.length == 8
startTime and endTime are valid times in the format "HH:MM:SS"
00 <= HH <= 23
00 <= MM <= 59
00 <= SS <= 59
endTime is not earlier than startTime

我的解法

class Solution:
    def secondsBetweenTimes(self, startTime: str, endTime: str) -> int:
        start_seconds = 3600 * (10 * int(startTime[0]) + int(startTime[1])) + 60 * (10 * int(startTime[3]) + int(startTime[4])) + (10* int(startTime[6]) + int(startTime[7]))
        end_seconds = 3600 * (10 * int(endTime[0]) + int(endTime[1])) + 60 * (10 * int(endTime[3]) + int(endTime[4])) + (10* int(endTime[6]) + int(endTime[7]))

        return end_seconds -  start_seconds

一个优化点，可以用 map 来分割字符。

同时

在 Python 中，int() 函数对字符串转换非常“宽容”，它会自动忽略前面的前导零。

你可以放心地看这几个例子：

Python
int('01')    # 返回: 1
int('007')   # 返回: 7
int('0000')  # 返回: 0

1. class Solution:
   
2.     def secondsBetweenTimes(self, startTime: str, endTime: str) -> int:
   
3.         # 定义一个辅助函数，专门负责把 "HH:MM:SS" 转成总秒数
   
4.         def get_seconds(time_str: str) -> int:
   
5.             h, m, s = map(int, time_str.split(':'))
   
6.             return h * 3600 + m * 60 + s
   
7.             
   
8.         return get_seconds(endTime) - get_seconds(startTime)

复制代码

LC. 3452. Sum of Good Numbers

Hint
Given an array of integers nums and an integer k, an element nums[i] is considered good if it is strictly greater than the elements at indices i - k and i + k (if those indices exist). If neither of these indices exists, nums[i] is still considered good.

Return the sum of all the good elements in the array.



Example 1:

Input: nums = [1,3,2,1,5,4], k = 2

Output: 12

Explanation:

The good numbers are nums[1] = 3, nums[4] = 5, and nums[5] = 4 because they are strictly greater than the numbers at indices i - k and i + k.

Example 2:

Input: nums = [2,1], k = 1

Output: 2

Explanation:

The only good number is nums[0] = 2 because it is strictly greater than nums[1].



Constraints:

2 <= nums.length <= 100
1 <= nums[i] <= 1000
1 <= k <= floor(nums.length / 2)

我的解法，其实我写的时候就感觉写复杂了，不过没想清楚怎么简化，就先通过再说了。

1. class Solution:
   
2.     def sumOfGoodNumbers(self, nums: List[int], k: int) -> int:
   
3.         ans = 0
   
4.         n = len(nums)
   
5. 
   
6.         for i in range(n):
   
7.             
   
8.             if i-k < 0 and i+k >= n:
   
9.                 ans += nums[i]
   
10.             else:
    
11.                 n1, n2 = 1001, 1001
    
12.                 if i-k >= 0: n1 = nums[i-k]
    
13.                 if i+k < n:  n2 = nums[i+k]
    
14.                 if n1 == 1001 and n2 < nums[i]:
    
15.                     ans += nums[i]
    
16.                 if n2 == 1001 and n1 < nums[i]:
    
17.                     ans += nums[i]
    
18.                 if n1 < nums[i] and n2 < nums[i]:
    
19.                     ans += nums[i]
    
20.             
    
21.         return ans
    
22.         

复制代码

优化，主要是两个一个是边界条件合并，巧妙利用 Python 条件判断，A or B 如果 A 为 True 会短路 B；另一个是取消 magic number 1001.

1. class Solution:
   
2.     def sumOfGoodNumbers(self, nums: List[int], k: int) -> int:
   
3.         ans = 0
   
4.         n = len(nums)
   
5.         
   
6.         for i in range(n):
   
7.             # 检查左边：要么索引越界（天然满足），要么当前元素严格大于左边元素
   
8.             left_ok = (i - k < 0) or (nums[i] > nums[i - k])
   
9.             
   
10.             # 检查右边：要么索引越界（天然满足），要么当前元素严格大于右边元素
    
11.             right_ok = (i + k >= n) or (nums[i] > nums[i + k])
    
12.             
    
13.             # 只有两边都满足，才加到结果里
    
14.             if left_ok and right_ok:
    
15.                 ans += nums[i]
    
16.                
    
17.         return ans

复制代码

LC. 1979. Find Greatest Common Divisor of Array

好久不碰了，辗转相除法都忘了。。。

1. class Solution:
   
2.     def findGCD(self, nums: List[int]) -> int:
   
3.         #return math.gcd(max(nums), min(nums))
   
4. 
   
5.         n_max, n_min = max(nums), min(nums)
   
6. 
   
7.         while n_min != 0:
   
8.             n_max, n_min  = n_min, n_max % n_min
   
9.         
   
10.         return n_max
    
11.         

复制代码

LC. 3992. Rearrange String to Avoid Character Pair

You are given a string s and two distinct lowercase English letters x and y.

Rearrange the characters of s to construct a new string t such that:

t is a permutation of s.
Every occurrence of y appears before every occurrence of x in t.
Return any valid string t.



Example 1:

Input: s = "aabc", x = "a", y = "c"

Output: "cbaa"

Explanation:

The string "cbaa" is a permutation of "aabc", and every occurrence of 'c' appears before every occurrence of 'a'.

Example 2:

Input: s = "dcab", x = "d", y = "b"

Output: "cabd"

Explanation:

The string "cabd" is a permutation of "dcab", and every occurrence of 'b' appears before every occurrence of 'd'.

Example 3:

Input: s = "axe", x = "o", y = "x"

Output: "axe"

Explanation:

The string "axe" is already valid. Since 'o' does not occur in the string, the required condition is automatically satisfied.



Constraints:

1 <= s.length <= 100
s consists of lowercase English letters.
x and y are lowercase English letters.
x != y

我的解法

1. class Solution:
   
2.     def rearrangeString(self, s: str, x: str, y: str) -> str:
   
3.         freq = Counter(s)
   
4.         ans = []
   
5.         ans += (freq[y] * [y])
   
6.         for n in freq:
   
7.             if n != y:
   
8.                 ans += (freq[n] * [n])
   
9. 
   
10.         return "".join(ans)
    
11.         

复制代码

优化下

列表乘法的开销：freq[y] * [y] 会生成一个类似 ['y', 'y', 'y'] 的列表。既然最终我们只需要字符串，其实可以直接用字符串相乘 "y" * freq[y] 会更轻量。

1. from collections import Counter
   
2. 
   
3. class Solution:
   
4.     def rearrangeString(self, s: str, x: str, y: str) -> str:
   
5.         freq = Counter(s)
   
6.         # 直接用字符串拼接，省去 list 转 string 的开销
   
7.         ans = y * freq[y]
   
8.         for char, count in freq.items():
   
9.             if char != y:
   
10.                 ans += char * count
    
11.         return ans

复制代码

解法一：极致简洁 API 魔法（推荐 ⭐⭐⭐⭐⭐）
利用 Python 底层 C 语言优化过的字符串方法 count() 和 replace()，直接一行搞定：

1. class Solution:
   
2.     def rearrangeString(self, s: str, x: str, y: str) -> str:
   
3.         # y * 频次 + s中剔除掉y之后剩下的部分
   
4.         return y * s.count(y) + s.replace(y, "")

复制代码

解法二：双指针 / 列表推导式 (体现基础扎实)
如果你碰到的面试官比较严格，不让你用内置的 replace 方法，可以用列表推导式写出一次遍历拼接的感觉：

1. class Solution:
   
2.     def rearrangeString(self, s: str, x: str, y: str) -> str:
   
3.         # 扫描两遍：第一遍拿出所有的 y，第二遍拿出所有非 y 的字符
   
4.         return "".join([c for c in s if c == y] + [c for c in s if c != y])

复制代码

LC. 3516. Find Closest Person

Companies
Hint
You are given three integers x, y, and z, representing the positions of three people on a number line:

x is the position of Person 1.
y is the position of Person 2.
z is the position of Person 3, who does not move.
Both Person 1 and Person 2 move toward Person 3 at the same speed.

Determine which person reaches Person 3 first:

Return 1 if Person 1 arrives first.
Return 2 if Person 2 arrives first.
Return 0 if both arrive at the same time.
Return the result accordingly.



Example 1:

Input: x = 2, y = 7, z = 4

Output: 1

Explanation:

Person 1 is at position 2 and can reach Person 3 (at position 4) in 2 steps.
Person 2 is at position 7 and can reach Person 3 in 3 steps.
Since Person 1 reaches Person 3 first, the output is 1.

Example 2:

Input: x = 2, y = 5, z = 6

Output: 2

Explanation:

Person 1 is at position 2 and can reach Person 3 (at position 6) in 4 steps.
Person 2 is at position 5 and can reach Person 3 in 1 step.
Since Person 2 reaches Person 3 first, the output is 2.

Example 3:

Input: x = 1, y = 5, z = 3

Output: 0

Explanation:

Person 1 is at position 1 and can reach Person 3 (at position 3) in 2 steps.
Person 2 is at position 5 and can reach Person 3 in 2 steps.
Since both Person 1 and Person 2 reach Person 3 at the same time, the output is 0.



Constraints:

1 <= x, y, z <= 100

简单题

1. class Solution:
   
2.     def findClosest(self, x: int, y: int, z: int) -> int:
   
3.         s1 = abs(x - z)
   
4.         s2 = abs(y - z)
   
5. 
   
6.         if s1 < s2:
   
7.             return 1
   
8.         elif s1 > s2:
   
9.             return 2
   
10.         else:
    
11.             return 0

复制代码

3560. Find Minimum Log Transportation Cost

You are given integers n, m, and k.

There are two logs of lengths n and m units, which need to be transported in three trucks where each truck can carry one log with length at most k units.

You may cut the logs into smaller pieces, where the cost of cutting a log of length x into logs of length len1 and len2 is cost = len1 * len2 such that len1 + len2 = x.

Return the minimum total cost to distribute the logs onto the trucks. If the logs don't need to be cut, the total cost is 0.



Example 1:

Input: n = 6, m = 5, k = 5

Output: 5

Explanation:

Cut the log with length 6 into logs with length 1 and 5, at a cost equal to 1 * 5 == 5. Now the three logs of length 1, 5, and 5 can fit in one truck each.

Example 2:

Input: n = 4, m = 4, k = 6

Output: 0

Explanation:

The two logs can fit in the trucks already, hence we don't need to cut the logs.



Constraints:

2 <= k <= 105
1 <= n, m <= 2 * k
The input is generated such that it is always possible to transport the logs.

这道题目是 easy 是因为加了限制条件，两段木头，三辆车 == 》 这表示最多只能切一刀

There are two logs of lengths n and m units, which need to be transported in three trucks where each truck can carry one log with length at most k units.

所以我的解法

1. class Solution:
   
2.     def minCuttingCost(self, n: int, m: int, k: int) -> int:
   
3.         cost = 0
   
4. 
   
5.         while n > k:
   
6.             cost += (k * (n-k))
   
7.             n -= k
   
8.         
   
9.         while m > k:
   
10.             cost += (k * (m-k))
    
11.             m -= k
    
12. 
    
13.         return cost

复制代码

循环只进入一次。

1. class Solution:
   
2.     def minCuttingCost(self, n: int, m: int, k: int) -> int:
   
3.         # 因为最多有3辆车，2根木头，所以最多只会有一根木头大于 k，且最多切一刀
   
4.         if n > k:
   
5.             return k * (n - k)
   
6.         if m > k:
   
7.             return k * (m - k)
   
8.         return 0

复制代码

这个就是变成了 x * ( L - x ) 最小的问题，根据函数性质，当然是两个切割的结果差尽可能大的时候总乘积小。

但是题目的数学证明并不普通。

切割不变量定理（Cutting Invariant）。

升级题目是

题目升级：给你一整组木头（数组）和一整组不同的卡车容量， 怎么做

直接给出结论：数学底层逻辑完全没变——我们依然要追求“让最终切出来的木头碎块平方和 $\sum p_i^2$ 最大化”。但算法模型会根据卡车的容量限制是否严苛，分化为“贪心 / 双指针排序”和“状态压缩 DP”两个方向。

算法模型拆解：两种面试场景场景 A：卡车数量充足（贪心 + 双排序）—— LeetCode Medium 难度如果题目保证卡车足够多、容量也够大（只要总容量 > 总木头长度就一定能装下），这题就是一个非常优美的贪心匹配问题。核心思路为了制造出最大的碎块，我们应该把最长的木头，匹配给容量最大的卡车去装或者去切！

(1) 把 logs（木头数组）降序排序。
(2) 把 trucks（卡车容量数组）降序排序。
(3) 每次取最大的木头 L$和最大的卡车容量 C：如果 L < C：不用切，这根木头直接整根装进这个大卡车（省下最大的平方和）。如果 L > C：贪心一刀切出一个长度为 C 的碎块装进卡车，剩下 L - C 的长度放回木头数组中，继续去跟下一辆卡车匹配。

（贪心排序 + 堆/模拟）

import heapq from typing import List

class Solution: def minTotalCuttingCost(self, logs: List[int], trucks: List[int]) -> int:
    # 1. 降序排序卡车容量（最能装的卡车放前面）
    trucks.sort(reverse=True)

    # 2. 为了方便每次取出“当前最长的木头”，我们使用最大堆（Python的heapq是小顶堆，取负号模拟）
    max_heap = [-log for log in logs]
    heapq.heapify(max_heap)
   
    total_cost = 0
   
    for capacity in trucks:
        if not max_heap:
            break
            
        # 取出当前最长的一根木头
        longest_log = -heapq.heappop(max_heap)
        
        if longest_log <= capacity:
            # 能够整根放进去，不需要切割，产生 0 花费
            continue
        else:
            # 贪心：切出卡车能装下的最大长度 capacity
            # 切割花费 = 切下来的一块 * 剩下的一块
            remain = longest_log - capacity
            total_cost += capacity * remain
            
            # 把剩下的木头扔回堆里，参与后续卡车的分配
            heapq.heappush(max_heap, -remain)
            
    return total_cost

卡车数量有限且要求正好装满（状态压缩 DP / 背包问题）—— LeetCode Hard 难度

在真实的高难度面试中（比如类似 LC 698. 划分为k个相等的子集 或 LC 1723. 完成所有工作的最短时间），面试官会加一个限制：“切出来的碎块必须正好能被现有的卡车装下，不能存在剩下一小截木头找不到卡车装的死局”。

此时，单纯的贪心可能会陷入局部最优解（比如贪心切了一个最大块，导致剩下的碎片太零散，没法放进剩余的小卡车里）。

状态压缩 DP（Bitmask DP）是解决 NP-Hard 数组划分、资源分配、旅行商问题（TSP） 的终极武器。当贪心算法因为“局部最优解导致空间死锁”而失效时，位运算结合动态规划是唯一能在面试中写出绝对正确解的方法。
我们用与上一讲“卡车装木头”完美契合的经典高频面试题——LeetCode 698. 划分为k个相等的子集（Partition to K Equal Sum Subsets），来彻底讲透二进制状压 DP 的模型与标准代码。

1. 拆解题意 & 避坑指南

题目复盘（LC 698）
给你一个整数数组

1. nums

复制代码

和一个正整数

1. k

复制代码

，找出是否有可能把这个数组分成

1. k

复制代码

个非空子集，其总和都相等。
怎么看出来要用 Bitmask DP？（最强信号）
在 LeetCode 和大厂面试中，只要看到以下两个特征同时出现，100% 是状态压缩 DP 或回溯搜索：

• 数据规模极小：数组长度 N  < 20（本题 N < 16）。
• 每个元素只有“选”或“不选”两种状态，且需要做全局最优组合。

因为 2^{16} = 65536，状态数非常少，用一个 16 位的二进制整数（

1. 0

复制代码

到

1. 65535

复制代码

）就能完美记录所有数字被装入卡车（子集）的情况！

容易踩的坑

• 贪心失效：不能每次凑满一个桶再凑下一个。比如
  1. nums = [4, 3, 2, 3, 5, 2, 1], k = 4

  复制代码
  ，如果先用贪心凑
  1. 5+1=6

  复制代码
  和
  1. 4+2=6

  复制代码
  ，剩下的
  1. 3, 3, 2

  复制代码
  就彻底死锁了。必须同时维护全局组合状态。
• 位运算优先级：在 Python 中，位运算（如
  1. <<

  复制代码
  ,
  1. &

  复制代码
  ,
  1. |

  复制代码
  ）的优先级低于比较运算符（如
  1. ==

  复制代码
  ,
  1. <=

  复制代码
  ）。写代码时务必给位运算加上括号，例如
  1. (mask & (1 << i)) == 0

  复制代码
  ，否则很容易产生极难排查的 Bug。

核心算法模型与状态定义二进制如何映射数组？

假设 nums = [4, 3, 2, 3]（长度 $N=4$）：

二进制 0000（十进制 0）：代表一个数字都没拿。
二进制 0101（十进制 5）：代表拿了第 0 个和第 2 个数字（从右往左第 0 位和第 2 位是 1）。
二进制 1111（十进制 15）：代表所有数字都被装进了桶里。

状态转移方程我们不需要记录当前填到第几个桶，只需要记录“当前正在填的这个桶，已经累计了多少容量”。

定义一维数组 dp[mask]：表示在使用了组合状态为 mask 的数字后，当前未填满的那个桶里，累计的数字和是多少。

如果 dp[mask] == -1，说明这个组合状态本身是绝对不可行的（无法由前面的合法状态转移过来）。

转移逻辑：

遍历当前状态 mask 下所有还没被选择的数字 nums[i]（即 mask 的第 i 位为 0）：如果 dp[mask] + nums[i] <= target（当前桶还能装下）：

新状态 new_mask = mask | (1 << i)
dp[new_mask] = (dp[mask] + nums[i]) % target（如果正好等于 target，取模后变成 0，自动代表开始填下一个新桶）。

from typing import List

class Solution: def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:

    total_sum = sum(nums)

    # 1. 基础特判与数学剪枝
    if total_sum % k != 0:
        return False
    target = total_sum // k
   
    # 降序排序是位运算 DP 和回溯最关键的剪枝！
    # 让最大的数字先尝试装桶，如果太远超 target 可以迅速退出，大幅减少无效状态
    nums.sort(reverse=True)
    if nums[0] > target:
        return False
        
    n = len(nums)
    # 共有 2^n 种二进制状态，0 表示全不选，(1<<n)-1 表示全选
    # dp[mask] 存储当前状态下，正在填的桶已经占用的容量。-1 表示该状态不可达。
    dp = [-1] * (1 << n)
   
    # 初始状态：什么都没选，当前桶占用容量为 0
    dp[0] = 0
   
    # 2. 状态压缩 DP 核心循环
    for mask in range(1 << n):
        # 如果当前状态不可达，直接跳过
        if dp[mask] == -1:
            continue
            
        # 尝试在当前状态的基础上，再多拿一个数字 nums[i]
        for i in range(n):
            # 检查 mask 的第 i 位是否为 0 (代表 nums[i] 还没被用过)
            if not (mask & (1 << i)):
                # 如果把 nums[i] 放进当前桶不会溢出
                if dp[mask] + nums[i] <= target:
                    # 产生新的状态：利用按位或 (|) 把第 i 位置为 1
                    new_mask = mask | (1 << i)
                    
                    # 重点技巧：通过 % target，当恰好填满一个桶时，占用容量自动归零，
                    # 从而平滑地开启下一个新桶的拼接
                    dp[new_mask] = (dp[mask] + nums[i]) % target
                else:
                    # 因为 nums 已经降序排序，如果当前 nums[i] 放不下，
                    # 那么再后面的数字肯定更小，也许能放下，不能 break，要继续看下一个 i
                    pass
                    
    # 最终检查全选状态 ((1 << n) - 1) 是否可达，且最后容量归零（正好分完 k 个桶）
    return dp[(1 << n) - 1] == 0

3550. Smallest Index With Digit Sum Equal to Index

Python 解法

1. class Solution:
   
2.     def smallestIndex(self, nums: List[int]) -> int:
   
3.         def getDigitsSum(n):
   
4.             return sum(int(ch) for ch in str(n))
   
5.         
   
6.         for i in range(len(nums)):
   
7.             if i == getDigitsSum(nums[i]):
   
8.                 return i
   
9.         
   
10.         return -1
    
11.         
    

复制代码

当然纯数学的解法

1. class Solution:
   
2.     def smallestIndex(self, nums: List[int]) -> int:
   
3.         def getDigitsSum(n: int) -> int:
   
4.             if n == 0:
   
5.                 return 0
   
6.             total = 0
   
7.             while n > 0:
   
8.                 total += n % 10  # 取出当前最右边的一位（个位）
   
9.                 n //= 10         # 砍掉最右边的一位
   
10.             return total
    
11. 
    
12.         for i, num in enumerate(nums):
    
13.             if i == getDigitsSum(num):
    
14.                 return i
    
15.         return -1

复制代码