结果与总结
这里是式酱～(∠・ω< )⌒☆
手速场掉小分，T3好像稍微有点卡常，导致优化的过程T了很多发，结果T4也写的慢了，感觉今天状态不是很好呀。
100435. 找到稳定山的下标
按照题意模拟即可，找出左侧相邻的山的高度严格大于 的下标。
时间复杂度 。
class Solution:
def stableMountains(self, height: List[int], threshold: int) -> List[int]:
n = len(height)
arr = []
for i in range(1,n):
if height[i - 1] > threshold:
arr.append(i)
return arr100414. 穿越网格图的安全路径
好像是以前一道 hard 的变种，虽然数据范围小了。
很直观的想到需要用 BFS 来解决，由于走到 的格子上会有惩罚，那么我们是否可以实现优先走 的格子，然后再走 的格子呢？可以用 来解决，每次遇到 就从队列头插入，否则插入队列尾，这样可以实现到达每个格子上一定是消耗血量最少的方案，最后和当前血量比较一下即可。
时间复杂度 。
class Solution:
def findSafeWalk(self, grid: List[List[int]], health: int) -> bool:
from collections import deque
q = deque([(0,0,0)])
m,n = len(grid),len(grid[0])
visit = [[False] * n for _ in range(m)]
visit[0][0] = True
while q:
x,y,h = q.popleft()
h += grid[x][y]
if x == m - 1 and y == n - 1:
return h < health
for (dx,dy) in [(x + 1,y),(x - 1,y),(x,y + 1),(x,y - 1)]:
if 0 <= dx < m and 0 <= dy < n and not visit[dx][dy]:
visit[dx][dy] = True
if grid[dx][dy] == 0:
q.appendleft((dx,dy,h))
else:
q.append((dx,dy,h))100429. 求出数组中最大序列值
思考怎么用暴力来解决这道题，值域很小，我们可以写一个递推的过程， 记作在 下长度为 的子序列或起来值为 是否成立。我们枚举分割点，前向做一次，在反向做一次，最后暴力扫一下两边满足的值，返回异或最大值即可。
实现上做了空间优化，遍历的维度可以去掉，且我们只需要保留最后一个数组。
时间复杂度 。
class Solution:
def maxValue(self, nums: List[int], k: int) -> int:
n = len(nums)
V = 1 << (max(nums).bit_length())
pre = [[False] * V for _ in range(k + 1)]
S = []
pre[0][0] = True
for i,x in enumerate(nums):
for j in range(k - 1, -1, -1):
for v in range(V):
if pre[j][v]:
pre[j + 1][v | x] = True
# 保留前缀长度为k的子序列的所有或结果
S.append(pre[k][:])
suf = [[False] * V for _ in range(k + 1)]
suf[0][0] = True
ans = 0
for i in range(n - 1, -1, -1):
for j in range(k - 1, -1, -1):
for v in range(V):
if suf[j][v]:
suf[j + 1][v | nums[i]] = True
if i >= k and i + k <= n:
for v1 in range(V):
for v2 in range(V):
if S[i - 1][v1] and suf[k][v2]:
ans = max(ans, v1 ^ v2)
return ans100426. 最长上升路径的长度
二维数点经典题，可以通过排序去掉其中一个维度，我们只需要考虑剩下一个怎么做，由于值域很大，我们可以做一个离散化。用线段树维护每个位置的最大上升路径长度，每次更新其实就是查询一下区间最大值，在此之上加 即可。
由于题目要求下标 序列 一定要在最长上升路径中，那么我们可以修改merge操作，每次优先返回包含下标 序列的答案即可，具体实现见代码。
时间复杂度 。
class SegmentTree():
def __init__(self, init, unitX, f):
self.f = f # (X, X) -> X
self.unitX = unitX
self.f = f
if type(init) == int:
self.n = init
self.n = 1 << (self.n - 1).bit_length()
self.X = [unitX] * (self.n * 2)
else:
self.n = len(init)
self.n = 1 << (self.n - 1).bit_length()
# len(init)が2の累乗ではない时UnitXで埋める
self.X = [unitX] * self.n + init + [unitX] * (self.n - len(init))
# 配列のindex1まで埋める
for i in range(self.n - 1, 0, -1):
self.X[i] = self.f(self.X[i * 2], self.X[i * 2 | 1])
def update(self, i, x):
"""0-indexedのi番目の値をxで置换"""
# 最下段に移动
i += self.n
self.X[i] = self.f(self.X[i], x)
# 上向に更新
i >>= 1
while i:
self.X[i] = self.f(self.X[i * 2], self.X[i * 2 | 1])
i >>= 1
def getvalue(self, i):
"""元の配列のindexの値を见る"""
return self.X[i + self.n]
def getrange(self, l, r):
"""区间[l, r)でのfを行った値"""
l += self.n
r += self.n
al = self.unitX
ar = self.unitX
while l < r:
# 左端が右子ノードであれば
if l & 1:
al = self.f(al, self.X[l])
l += 1
# 右端が右子ノードであれば
if r & 1:
r -= 1
ar = self.f(self.X[r], ar)
l >>= 1
r >>= 1
return self.f(al, ar)
def op(x, y):
if x[1] == y[1]:
return max(x[0], y[0]), x[1]
else:
if x[1]:
return x
else:
return y
class Solution:
def maxPathLength(self, coordinates: List[List[int]], k: int) -> int:
d = defaultdict(list)
# 离散化
s = set()
for x, y in coordinates:
d[x].append(y)
s.add(y)
s = sorted(list(s))
idx = {v: i for i, v in enumerate(s)}
tree = SegmentTree([[0,False] for _ in range(len(s))], [0, False], op)
for key in sorted(d.keys()):
li = []
for y in d[key]:
li.append(tree.getrange(0, idx[y]))
for i in range(len(li)):
x, y = key, d[key][i]
if x == coordinates[k][0] and y == coordinates[k][1]:
tree.update(idx[y], [li[i][0] + 1, True])
else:
tree.update(idx[y], [li[i][0] + 1, li[i][1]])
return tree.getrange(0, len(s))[0]写在最后
评论 (5)
