本文最后更新于 1 分钟前，文中所描述的信息可能已发生改变。
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
"""
上下边界数位dp模板
limitHigh 表示当前是否受到了 finish 的约束（我们要构造的数字不能超过 finish。若为真，则第 iii 位填入的数字至多为 finish[i]，否则至多为 9，
这个数记作 hi。如果在受到约束的情况下填了 finish[i]，那么后续填入的数字仍会受到 finish 的约束。例如 finish=123，那么 i=0 填的是 1 的话，i=1 的这一位至多填 2。
limitLow 表示当前是否受到了 start 的约束（我们要构造的数字不能低于 start。若为真，则第 i 位填入的数字至少为 start[i]，否则至少为 0，这个数记作 lo。
如果在受到约束的情况下填了 start[i]，那么后续填入的数字仍会受到 start 的约束。
@Author : 灵茶山艾府
@link : https://leetcode.cn/problems/count-the-number-of-powerful-integers/solutions/2595149/shu-wei-dp-shang-xia-jie-mo-ban-fu-ti-da-h6ci
"""
from functools import lru_cache
low = int(input())
high = int(input())
low, high = str(low), str(high)
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) -> 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)
# 第 i 个数位可以从 lo 枚举到 hi
# 如果对数位还有其它约束，应当只在下面的 for 循环做限制，不应修改 lo 或 hi
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): # 如果前面没有填数字，必须从 1 开始（因为不能有前导零）
res += dfs(i + 1, limit_low and d == lo, limit_high and d == hi, True)
return res