本文最后更新于 2 分钟前，文中所描述的信息可能已发生改变。
3560. 木材运输的最小成本 - 力扣（LeetCode）
解题思路
数学公式，x(n - x) = -x^2 + nx，当x = k时，为最小值
示例代码
python
class Solution:
def minCuttingCost(self, n: int, m: int, k: int) -> int:
return max(k * (n - k), 0) + max(k * (m - k), 0)3561. 移除相邻字符 - 力扣（LeetCode）
解题思路
栈，能消除字符就出栈，不能则入栈
示例代码
python
class Solution:
def resultingString(self, s: str) -> str:
st = []
a = list(map(ord, s))
for i, x in enumerate(a):
if st and (abs(st[-1] - x) == 25 or abs(st[-1] - x) == 1):
st.pop()
else:
st.append(x)
return ''.join(map(chr, st))3562. 折扣价交易股票的最大利润 - 力扣（LeetCode）
解题思路
示例代码
python
class Solution:
def maxProfit(self, n: int, present: List[int], future: List[int], hierarchy: List[List[int]], budget: int) -> int:
g = defaultdict(list)
for u, v in hierarchy:
g[u - 1].append(v - 1)
fmax = lambda x, y: x if x > y else y
@cache
def dfs(x: int) -> List[List[int]]:
sf = [[0] * 2 for _ in range(budget + 1)]
# 计算子树的最大利润
for y in g[x]:
fy = dfs(y)
for j in range(budget, -1, -1):
for jy in range(j + 1):
for k in range(2):
sf[j][k] = fmax(sf[j][k], sf[j - jy][k] + fy[jy][k])
# 选或不选节点x
f = [[0] * 2 for _ in range(budget + 1)]
for j in range(budget + 1):
for k in range(2):
cost = present[x] // (k + 1)
if j >= cost:
f[j][k] = fmax(sf[j][0], sf[j - cost][1] + future[x] - cost)
else:
f[j][k] = sf[j][0]
return f
ans = dfs(0)[budget][0]
dfs.cache_clear()
return ans3563. 移除相邻字符后字典序最小的字符串 - 力扣（LeetCode）
解题思路
示例代码
python
class Solution:
def lexicographicallySmallestString(self, s: str) -> str:
n = len(s)
fair = lambda x, y: abs(ord(x) - ord(y)) == 1 \
or abs(ord(x) - ord(y)) == 25
@cache
def dfs(i, j):
if i > j:
return True
if fair(s[i], s[j]) and dfs(i + 1, j - 1):
return True
for k in range(i + 1, j - 1, 2):
if dfs(i, k) and dfs(k + 1, j):
return True
return False
@cache
def dfs2(i):
if i == n:
return ""
res = s[i] + dfs2(i + 1)
for j in range(i + 1, n, 2):
if dfs(i, j):
res = min(res, dfs2(j + 1))
return res
return dfs2(0)python
class Solution:
def lexicographicallySmallestString(self, s: str) -> str:
n = len(s)
fair = lambda x, y: abs(ord(x) - ord(y)) == 1 \
or abs(ord(x) - ord(y)) == 25
f = [[False] * n for _ in range(n)]
for i in range(n - 2, -1, -1):
f[i + 1][i] = True
for j in range(i + 1, n, 2):
if fair(s[i], s[j]) and f[i + 1][j - 1]:
f[i][j] = True
continue
for k in range(i + 1, j - 1, 2):
if f[i][k] and f[k + 1][j]:
f[i][j] = True
break
ans = [''] * (n + 1)
for i in range(n - 1, -1, -1):
res = s[i] + ans[i + 1]
for j in range(i + 1, n, 2):
if f[i][j]:
res = min(res, ans[j + 1])
ans[i] = res
return ans[0]