一、学生分数的最小差值
class Solution:
def minimumDifference(self, nums: List[int], k: int) -> int:
nums.sort()
res = float('inf')
for i in range(len(nums)-k+1):
res = min(res, nums[i+k-1]-nums[i])
return res
二、找出数组中的第 K 大整数
class Solution:
def kthLargestNumber(self, nums: List[str], k: int) -> str:
arr = [int(i) for i in nums]
arr.sort()
return str(arr[-k])
三、完成任务的最少工作时间段
输入：tasks = [1,2,3], sessionTime = 3
输出：2
解释：你可以在两个工作时间段内完成所有任务。
- 第一个工作时间段：完成第一和第二个任务，花费 1 + 2 = 3 小时。
- 第二个工作时间段：完成第三个任务，花费 3 小时。
输入：tasks = [3,1,3,1,1], sessionTime = 8
输出：2
解释：你可以在两个工作时间段内完成所有任务。
- 第一个工作时间段：完成除了最后一个任务以外的所有任务，花费 3 + 1 + 3 + 1 = 8 小时。
- 第二个工作时间段，完成最后一个任务，花费 1 小时。
最开始的做法，看到 1 <= n <= 14，以为能够暴力回溯，超时了…
class Solution:
def minSessions(self, tasks: List[int], t: int) -> int:
n = len(tasks)
tasks.sort(reverse = True)
res = n #最多需要 n 个桶
def dfs(arr, tasks):
#print(arr)
nonlocal res
flag = True
if not tasks:
res = min(res, len(arr))
return
for i,task in enumerate(tasks):
for j,val in enumerate(arr):
if task <= val:
flag = False
arr[j] -= task
dfs(arr,tasks[:i]+tasks[i+1:])
arr[j] += task
if flag: #放不下，加桶
arr.append(t)
dfs(arr, tasks)
dfs([t], tasks) #最少一个桶
return res
正确做法：记忆化 + 状态压缩 + dfs，还是个暴力。。。
class Solution:
def minSessions(self, tasks: List[int], sessionTime: int) -> int:
n = len(tasks)
tasks.sort()
@lru_cache(None)
def dfs(mask, r):
if mask == (1<<n) -1: return 1 #所有task都做了
ans = float("inf")
for i in range(n):
if (mask >> i) & 1: #第 i 个 task 做了
continue
if tasks[i] <= r:
ans = min(ans, dfs(mask | 1 << i, r - tasks[i]))
else:
ans = min(ans, dfs(mask | 1 << i, sessionTime - tasks[i]) + 1)
return ans
return dfs(0, sessionTime)
好吧，现在再练一下状态压缩 + 记忆化 + bfs，参考每日一题8月（847.访问所有节点的最短路径）
class Solution:
def minSessions(self, tasks: List[int], sessionTime: int) -> int:
n = len(tasks)
tasks.sort()
q = deque([(0, sessionTime, 1)])
vis = set((0, sessionTime, 1))
ans = float('inf')
while q:
mask, r, res = q.popleft()
if mask == (1<<n)-1:
ans = min(ans, res)
continue
for i,val in enumerate(tasks):
if mask>>i&1:
continue
mask_v = mask | (1<<i)
# 不开桶
if val <= r and (mask_v, r-val, res) not in vis:
vis.add((mask_v, r-val, res))
q.append((mask_v, r-val, res))
# 开桶
if (mask_v, sessionTime-val,res+1) not in vis:
vis.add((mask_v, sessionTime-val,res+1))
q.append((mask_v, sessionTime-val, res+1))
return ans
# 还是超时了，第72个用例，总共75个
# vis 不加第三个参数的话会出错
# 算了，这个模板练习一下，就赚了
四、不同的好子序列数目
输入：binary = "001"
输出：2
解释：好的二进制子序列为 ["0", "0", "1"] 。
不同的好子序列为 "0" 和 "1" 。
输入：binary = "101"
输出：5
解释：好的二进制子序列为 ["1", "0", "1", "10", "11", "101"] 。
不同的好子序列为 "0" ，"1" ，"10" ，"11" 和 "101" 。
参过过来的代码：发现是 有限状态自动机 + 特殊处理，大佬 wa 了一次
class Solution:
def numberOfUniqueGoodSubsequences(self, binary: str) -> int:
n = len(binary)
cnt = binary.count('1')
if cnt == n: return n
if cnt == 0: return 1
su = [0, 0]
mod = 10**9+7
for c in binary:
i = int(c)
if i == 1:
su[1] = (su[1] + 1 + su[0]) % mod
else:
su[0] = (su[0] + su[1]) % mod
print(su)
return (sum(su) + 1) % mod
自己重新写的：主要是理清楚状态，可理清状态好难….
# 状态a: 好子序列以 0 结尾
# 转移方程： a += (a+b-a)
# => a += b
# 说明：a,b集中的好子序列都加个后缀0，重复了 a 个
#
# 状态b: 好子序列以 1 结尾
# 转移方程： b += (a+b-b+1)
# => b += (a+1)
# 说明：a,b集中的好子序列都加个后缀1，重复了 b-1 个（1 可作为单独的好子序列）。
#
# 输出的结果多了个"0"？
# ：因为在题目中"0"被算作有效子序列，可状态机不能把它算进去
class Solution:
def numberOfUniqueGoodSubsequences(self, binary: str) -> int:
a, b = 0, 0
mod = 10**9+7
for c in map(int, binary):
if c == 1:
b += (a+1)
b %= mod
else:
a += b
a %= mod
return (a+b+ ("0" in binary))%mod
相似题目：940. 不同的子序列 II
小结
6分钟做了两道题。😀
