1004.Max Consecutive Ones III
Sliding window
def longestOnes(self, A: List[int], K: int) -> int:
left = right = 0
for right in range(len(A)):
# if we encounter a 0 the we decrement K
if A[right] == 0:
K -= 1
# else no impact to K
# if K < 0 then we need to move the left part of the window forward
# to try and remove the extra 0's
if K < 0:
# if the left one was zero then we adjust K
if A[left] == 0:
K += 1
# regardless of whether we had a 1 or a 0 we can move left side by 1
# if we keep seeing 1's the window still keeps moving as-is
left += 1
return right - left + 1对比(自己):
def longestOnes(self, nums: List[int], k: int) -> int:
cont = False
running = deque([])
current_sum = 0
running_max = 0
k_count = 0
for num in nums:
if num == 1:
if cont:
running[-1] += 1
else:
running.append(1)
cont = True
else:
running_max = max(running_max, current_sum)
if cont:
running[-1] += 1
cont = False
else:
running.append(1)
k_count += 1
if k_count > k:
current_sum -= running.popleft()
current_sum += 1
return max(running_max, current_su**241. Different Ways to Add Parentheses ****
非常重要的做题方式和思路 很长时间没有做类似的题了
def diffWaysToCompute(self, expression: str) -> List[int]:
op_set = {"*", "+", "-"}
dp = {}
def recur(expression):
if expression in dp:
return dp[expression]
retur = []
for i in range(len(expression)):
if expression[i] in op_set:
left = recur(expression[:i])
dp.setdefault(expression[:i], left)
right = recur(expression[i+1:])
dp.setdefault(expression[i+1:], left)
if expression[i] == "+":
retur += [l + r for l in left for r in right]
if expression[i] == "-":
retur += [l - r for l in left for r in right]
if expression[i] == "*":
retur += [l * r for l in left for r in right]
if not retur:
retur = [int(expression)]
dp[expression] = retur
return retur
return recur(expression)2232. Minimize Result by Adding Parentheses to Expression
def minimizeResult(self, expression: str) -> str: # Example: "247+38"
# left, right = "247","38"
left, right = expression.split('+')
value = lambda s:eval(s.replace('(','*(').replace(')',')*').strip('*'))
lft = [ left[0:i]+'('+ left[i:] for i in range( len(left ) )] # lft = ['(247', '2(47', '24(7']
rgt = [right[0:i]+')'+right[i:] for i in range(1,len(right)+1)] # rgt = ['3)8', '38)']
return min([l+'+'+r for l in lft for r in rgt], key = value)2257. Count Unguarded Cells in the Grid
binary search in
def countUnguarded(self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]) -> int:
gs, ws = {tuple(g) for g in guards}, {tuple(w) for w in walls}
# build 2 maps of all positions occupied by either a guard or a wall
# with keys being the position's row & col indices respectively
occ_map_by_i, occ_map_by_j = defaultdict(list), defaultdict(list)
for (i, j) in sorted(gs.union(ws)):
occ_map_by_i[i].append(j)
occ_map_by_j[j].append(i)
res = 0
# iterate through all positions in the 2D grid
for i in range(m):
for j in range(n):
if (i, j) in gs or (i, j) in ws: continue # pos is already occupied
row = occ_map_by_i[i]
x = bisect.bisect(row, j)
if x > 0 and (i, row[x-1]) in gs: continue # has guard to its west
if x < len(row) and (i, row[x]) in gs: continue # has guard to its east
col = occ_map_by_j[j]
y = bisect.bisect(col, i)
if y > 0 and (col[y-1], j) in gs: continue # has guard to its north
if y < len(col) and (col[y], j) in gs: continue # has guard to its south
res += 1 # current position is unoccupied & unguarded
return res2290. Minimum Obstacle Removal to Reach Corner
同样也是很久没做这个类型的 其实很常见 用greedy永远找目前最小obs路径
如果到了顶点直接就是结果
如果dfs遍历 更新所有 会很慢 没有很好的exit condition
Recursive dp → TLE
class Solution:
def __init__(self):
self.dp = None
self.grid = None
self.n = None
self.m = None
self.hist = {}
def minimumObstacles(self, grid: List[List[int]]) -> int:
self.n = len(grid)
self.m = len(grid[0])
# self.dp = [[float('inf')] * self.m for _ in range(self.n)]
self.grid = {(r, i): (0 if p == 0 else 1) for r, row in enumerate(grid) for i, p in enumerate(row)}
self.find((0, 0), 0)
return self.hist[(self.n-1,self.m-1)]
def find(self, pos, obs):
if pos in self.hist and obs >= self.hist[pos]:
return
self.hist[pos] = obs
if not 0 <= pos[0] < self.n or not 0 <= pos[1] < self.m:
return
obs += self.grid[pos]
self.find((pos[0]+1, pos[1]), obs)
self.find((pos[0]-1, pos[1]), obs)
self.find((pos[0], pos[1]+1), obs)
self.find((pos[0], pos[1]-1), obs)Dijkstra’s
def minimumObstacles(self, grid: List[List[int]]) -> int:
n = len(grid)
m = len(grid[0])
dp = [[float('inf')] * m for _ in range(n)]
dq = [(0, 0, 0)]
direc = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while dq:
obs, x, y = heapq.heappop(dq)
if x == n - 1 and y == m - 1:
return obs
for dx, dy in direc:
new_x, new_y = x + dx, y + dy
if 0 <= new_x < n and 0 <= new_y < m:
new_obs = obs + grid[new_x][new_y]
if new_obs < dp[new_x][new_y]:
dp[new_x][new_y] = new_obs
heapq.heappush(dq, (new_obs, new_x, new_y))
return -1Dijkstra’s -→ 0-1 BFS(当edge为0或1时)
ensure to always process path with fewer obs first
prioritize 0 weight edge
为什么只有0-1可以用 → 0, 1时1加到后面可以自动排序 不需要heappush 调顺序
如果不规定edge weight 加到后面顺序会乱 破坏搜索顺序
BFS 0-1 还有的优点是不需要在queue里记录 obs 因为都是自动排序 记录在dp中
要是讲的不清楚可以看这个 —>
https://codeforces.com/blog/entry/22276
def minimumObstacles(self, grid: List[List[int]]) -> int:
n = len(grid)
m = len(grid[0])
dp = [[float('inf')] * m for _ in range(n)]
dp[0][0] = 0
dq = deque([(0, 0)])
direc = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while dq:
x, y = dq.popleft()
obs = dp[x][y]
if x == n - 1 and y == m - 1:
return obs
for dx, dy in direc:
new_x, new_y = x + dx, y + dy
if 0 <= new_x < n and 0 <= new_y < m:
new_obs = obs + grid[new_x][new_y]
if new_obs < dp[new_x][new_y]:
dp[new_x][new_y] = new_obs
if grid[new_x][new_y] == 0:
dq.appendleft((new_x, new_y))
else:
dq.append((new_x, new_y))
return -1