刷题记录帖子

Myron2017

LC. 3978. Unique Middle Element

我的解法

class Solution:
def isMiddleElementUnique(self, nums: list[int]) -> bool:
freq = Counter(nums)
return freq[nums[len(nums)// 2]] == 1

复制代码

可以优化的地方，

我们真的需要统计所有元素的频率吗？其实不需要。我们只关心中间那个元素出现了几次。因此，我们可以先找出中间元素的值，然后再遍历一次数组，只数这一个值的出现次数。

class Solution:
def isMiddleElementUnique(self, nums: list[int]) -> bool:
# 1. 找到中间元素的值
mid_val = nums[len(nums) // 2]
# 2. 统计这个值在数组中出现的次数
return nums.count(mid_val) == 1

复制代码

不用内置函数，注意可以提前截断。

class Solution:
def isMiddleElementUnique(self, nums: list[int]) -> bool:
mid_val = nums[len(nums) // 2]
count = 0
for num in nums:
if num == mid_val:
count += 1
# 剪枝小技巧：如果发现次数已经大于1了，直接返回 False 即可，没必要看完
if count > 1:
return False
return count == 1

复制代码

Myron2017

LC. 3982. Sum of Integers with Maximum Digit Range

我的解法

class Solution:
def maxDigitRange(self, nums: list[int]) -> int:
digitRange = defaultdict(list)
max_dr = -1
for n in nums:
strn = [int(x) for x in str(n)]
dr = max(strn) - min(strn)
digitRange[dr].append(n)
max_dr = max(dr, max_dr)
return sum(digitRange[max_dr])

复制代码

优化

核心思路：
我们其实并不关心那些较小的 Digit Range 对应的数字是什么。我们可以像“打擂台”一样，在遍历数组的时候，只维护两个变量：

历史最大的 max_dr。

这个 max_dr 对应的累加和 ans_sum。

如果遇到了更大的 dr，就清空之前的和，重新开始累加；如果遇到了相等的 dr，就加到当前的和里。

class Solution:
def maxDigitRange(self, nums: list[int]) -> int:
max_dr = -1
ans_sum = 0
for n in nums:
# 技巧 1：转成字符串
s = str(n)
# 技巧 2：直接用 max() 和 min() 获取最大最小字符，再转回 int 计算
dr = int(max(s)) - int(min(s))
if dr > max_dr:
# 遇到新的更大范围，刷新 max_dr，并重置当前求和
max_dr = dr
ans_sum = n
elif dr == max_dr:
# 遇到一样的最大范围，累加进结果里
ans_sum += n
return ans_sum

复制代码

Myron2017

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

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

复制代码

Myron2017

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)

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

class Solution:
def sumOfGoodNumbers(self, nums: List[int], k: int) -> int:
ans = 0
n = len(nums)
for i in range(n):
if i-k < 0 and i+k >= n:
ans += nums[i]
else:
n1, n2 = 1001, 1001
if i-k >= 0: n1 = nums[i-k]
if i+k < n: n2 = nums[i+k]
if n1 == 1001 and n2 < nums[i]:
ans += nums[i]
if n2 == 1001 and n1 < nums[i]:
ans += nums[i]
if n1 < nums[i] and n2 < nums[i]:
ans += nums[i]
return ans

复制代码

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

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

复制代码

Myron2017

LC. 1979. Find Greatest Common Divisor of Array

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

class Solution:
def findGCD(self, nums: List[int]) -> int:
#return math.gcd(max(nums), min(nums))
n_max, n_min = max(nums), min(nums)
while n_min != 0:
n_max, n_min = n_min, n_max % n_min
return n_max

复制代码

Myron2017

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

我的解法

class Solution:
def rearrangeString(self, s: str, x: str, y: str) -> str:
freq = Counter(s)
ans = []
ans += (freq[y] * [y])
for n in freq:
if n != y:
ans += (freq[n] * [n])
return "".join(ans)

复制代码

优化下

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

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

复制代码

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

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

复制代码

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

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

复制代码

Myron2017

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

简单题

class Solution:
def findClosest(self, x: int, y: int, z: int) -> int:
s1 = abs(x - z)
s2 = abs(y - z)
if s1 < s2:
return 1
elif s1 > s2:
return 2
else:
return 0

复制代码

Myron2017

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.

所以我的解法

class Solution:
def minCuttingCost(self, n: int, m: int, k: int) -> int:
cost = 0
while n > k:
cost += (k * (n-k))
n -= k
while m > k:
cost += (k * (m-k))
m -= k
return cost

复制代码

循环只进入一次。

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

复制代码

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

Myron2017

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

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

Myron2017

升级题目是

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

直接给出结论：数学底层逻辑完全没变——我们依然要追求“让最终切出来的木头碎块平方和 $\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

刷题记录帖子

浏览过的版块