本文最后更新于 2 分钟前，文中所描述的信息可能已发生改变。
3602. 十六进制和三十六进制转化 - 力扣（LeetCode）
解题思路
代码复用，转换进制
库函数解法详见参考
示例代码
python
class Solution:
def concatHex36(self, n: int) -> str:
d = digits + ascii_uppercase
def convert(n, base):
ans = []
while n:
ans.append(d[n % base])
n //= base
return ''.join(ans[::-1])
return convert(n * n, 16) + convert(n * n * n, 36)python
import numpy as np
class Solution:
def concatHex36(self, n: int) -> str:
return np.base_repr(n ** 2, base=16) + np.base_repr(n ** 3, base=36)3603. 交替方向的最小路径代价 II - 力扣（LeetCode）
解题思路
网格图 DP，从上方或左边转移，注意起点和终点的权值计算方式
示例代码
python
class Solution:
def minCost(self, m: int, n: int, w: List[List[int]]) -> int:
f = [[inf] * (n + 1) for _ in range(m + 1)]
f[1][0] = f[0][1] = 0
for i in range(m):
for j in range(n):
v = w[i][j] + (i + 1) * (j + 1)
if i == j == 0 or i == m - 1 and j == n - 1:
v -= w[i][j]
f[i + 1][j + 1] = min(f[i + 1][j + 1], f[i][j + 1] + v)
f[i + 1][j + 1] = min(f[i + 1][j + 1], f[i + 1][j] + v)
return f[-1][-1]3604. 有向图中到达终点的最少时间 - 力扣（LeetCode）
解题思路
最短路，可以用模板，不用模板就手搓，没啥难度
示例代码
python
class Solution:
def minTime(self, n: int, edges: List[List[int]]) -> int:
g = [[] for _ in range(n)]
for u, v, st, ed in edges:
g[u].append((v, st, ed))
h = [(0, 0)]
d = [inf] * n
while h:
cur, u = heappop(h)
if u == n - 1:
return cur
for v, st, end in g[u]:
if cur > end:
continue
tmp = max(cur, st) + 1
if tmp < d[v]:
d[v] = tmp
heappush(h, (tmp, v))
return -13605. 数组的最小稳定性因子 - 力扣（LeetCode）
解题思路
笨蛋解法：二分查找最小稳定子数组，用线段树维护区间最大公因数，修改只用修改区间最右端即可，这样可以使[l, l + m] -> [m, m + m]均为不稳定数组，计数跳至 m + 1，继续计算需修改的次数即可
智慧解法： logTrick，详见参考
示例代码
python
class Solution:
def minStable(self, nums: List[int], maxC: int) -> int:
n = len(nums)
seg = SegmentTree(gcd, 0, nums)
l = 1
r = n
while l <= r:
m = l + r >> 1
i = 0
cnt = 0
while i + m <= n:
g = seg.prod(i, i + m)
if g > 1:
i += m - 1
cnt += 1
i += 1
if cnt > maxC:
l = m + 1
else:
r = m - 1
return rpy
import typing
class SegTree:
__slots__ = ["_op", "_e", "_n", "_log", "_size", "_d"]
def __init__(self, op: typing.Callable[[typing.Any, typing.Any], typing.Any],
e: typing.Any,
v: typing.Union[int, typing.List[typing.Any]]) -> None:
"""
Args:
op: maintain operation function, such as add, max, min, etc.
e: initial value of the segment tree
v: initial value of the array
"""
self._op = op
self._e = e
if isinstance(v, int):
v = [e] * v
self._n = len(v)
self._log = (self._n - 1).bit_length()
self._size = 1 << self._log
self._d = [e] * (2 * self._size)
for i in range(self._n):
self._d[self._size + i] = v[i]
for i in range(self._size - 1, 0, -1):
self._update(i)
def set(self, p: int, x: typing.Any) -> None:
assert 0 <= p < self._n
p += self._size
self._d[p] = x
for i in range(1, self._log + 1):
self._update(p >> i)
def get(self, p: int) -> typing.Any:
assert 0 <= p < self._n
return self._d[p + self._size]
def prod(self, left: int, right: int) -> typing.Any:
assert 0 <= left <= right <= self._n
sml = self._e
smr = self._e
left += self._size
right += self._size
while left < right:
if left & 1:
sml = self._op(sml, self._d[left])
left += 1
if right & 1:
right -= 1
smr = self._op(self._d[right], smr)
left >>= 1
right >>= 1
return self._op(sml, smr)
def all_prod(self) -> typing.Any:
return self._d[1]
def max_right(self, left: int,
f: typing.Callable[[typing.Any], bool]) -> int:
assert 0 <= left <= self._n
assert f(self._e)
if left == self._n:
return self._n
left += self._size
sm = self._e
first = True
while first or (left & -left) != left:
first = False
while left % 2 == 0:
left >>= 1
if not f(self._op(sm, self._d[left])):
while left < self._size:
left *= 2
if f(self._op(sm, self._d[left])):
sm = self._op(sm, self._d[left])
left += 1
return left - self._size
sm = self._op(sm, self._d[left])
left += 1
return self._n
def min_left(self, right: int,
f: typing.Callable[[typing.Any], bool]) -> int:
assert 0 <= right <= self._n
assert f(self._e)
if right == 0:
return 0
right += self._size
sm = self._e
first = True
while first or (right & -right) != right:
first = False
right -= 1
while right > 1 and right % 2:
right >>= 1
if not f(self._op(self._d[right], sm)):
while right < self._size:
right = 2 * right + 1
if f(self._op(self._d[right], sm)):
sm = self._op(self._d[right], sm)
right -= 1
return right + 1 - self._size
sm = self._op(self._d[right], sm)
return 0
def _update(self, k: int) -> None:
self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1])