本文最后更新于 2 分钟前，文中所描述的信息可能已发生改变。
Q1. 删除后的最大子数组元素和
解题思路
暴力
优化，贪心，只取正值，如果没有正值，返回最大值
示例代码
python
class Solution:
def maxSum(self, nums: List[int]) -> int:
nums = list(set(nums))
n = len(nums)
ans = -inf
nums.sort()
pre = list(accumulate(nums, initial=0))
for i in range(1, n + 1):
for j in range(n - i + 1):
ans = max(ans, pre[i + j] - pre[j])
return anspython
class Solution:
def maxSum(self, nums: List[int]) -> int:
s = sum(x for x in set(nums) if x > 0)
return s if s else max(nums)Q2. 距离最小相等元素查询
解题思路
搜集相同元素的有序集合，二分查找，特判边界
示例代码
python
class Solution:
def solveQueries(self, nums: List[int], queries: List[int]) -> List[int]:
n = len(nums)
m = len(queries)
d = defaultdict(list)
ans = [-1] * m
for i, x in enumerate(nums):
d[x].append(i)
for i, x in enumerate(queries):
y = nums[x]
if len(d[y]) <= 1:
continue
idx = bisect_left(d[y], x)
if idx == 0:
a = n - d[y][-1] + x
else:
a = x - d[y][idx - 1]
if idx == len(d[y]) - 1:
b = n - x + d[y][0]
else:
b = d[y][idx + 1] - x
ans[i] = min(a, b)
return ansQ3. 零数组变换 IV
解题思路
对每个元素进行背包 DP
示例代码
python
class Solution:
def minZeroArray(self, nums: List[int], queries: List[List[int]]) -> int:
n, m = len(nums), len(queries)
d = [[0] * m for _ in range(n)]
for i, (l, r, val) in enumerate(queries):
for j in range(l, r + 1):
d[j][i] = val
ans = [inf] * n
for i, (x, row) in enumerate(zip(nums, d)):
f = [0] + [inf] * x
for j, y in enumerate(row, 1):
if y == 0: continue
for k in range(x, -1, -1):
if k + y > x or f[k] == inf: continue
f[k + y] = min(f[k + y], j)
ans[i] = f[-1]
mx = max(ans)
return mx if mx < inf else -1Q4. 统计美丽整数的数目
解题思路
数位 DP，套用灵神数位 DP 模板，增加两个字段记录乘积和求和
示例代码
python
class Solution:
def beautifulNumbers(self, l: int, r: int) -> int:
low, high = str(l), str(r)
n = len(high)
diff = n - len(low)
low = '0' * diff + low
@lru_cache(None)
def dfs(i: int, limit_low: bool, limit_high: bool, is_num: bool, s: int, mul: int) -> int:
if i == len(high):
return int(mul % s == 0)
res = 0
if i < diff and not is_num:
res += dfs(i + 1, True, False, False, s, mul)
lo = int(low[i]) if limit_low else 0
hi = int(high[i]) if limit_high else 9
for d in range(max(lo, 1 - is_num), hi + 1):
res += dfs(i + 1, limit_low and d == lo, limit_high and d == hi, True, s + d, mul * d)
return res
ans = dfs(0, True, True, False, 0, 1)
dfs.cache_clear()
return anspy
from functools import lru_cache
class DigitDynamicProgramming:
def count_numbers(self, num: int) -> int:
nums = list(map(int, str(num)))
@lru_cache(None)
def dfs(i: int, mask: int, is_limit: bool, is_num: bool) -> int:
if i == len(nums):
return is_num
res = 0
if not is_num:
res = dfs(i + 1, mask, False, False)
lo = 0 if is_num else 1
hi = nums[i] if is_limit else 9
for d in range(lo, hi + 1):
if (mask >> d & 1) == 0:
res += dfs(i + 1, mask | (1 << d), is_limit and d == hi, True)
return res
ans = dfs(0, 0, True, False)
dfs.cache_clear()
return ans
def count_numbers_in_range(self, low: int, high: int) -> int:
n = len(str(high))
high = list(map(int, str(high)))
low = list(map(int, str(low).zfill(n)))
diff = n - len(low)
@lru_cache(None)
def dfs(i: int, limit_low: bool, limit_high: bool, is_num: bool) -> int:
if i == len(high):
return int(is_num)
res = 0
if i < diff and not is_num:
res += dfs(i + 1, True, False, False)
lo = low[i] if limit_low else 0
hi = high[i] if limit_high else 9
for d in range(max(lo, 1 - is_num), hi + 1):
res += dfs(i + 1, limit_low and d == lo, limit_high and d == hi, True)
return res
ans = dfs(0, True, True, False)
dfs.cache_clear()
return ans