# A. Count Prefixes of a Given String (opens new window)
Iterate over words, for each word word check if it starts with the string s.
DETAILS
def countPrefixes(self, words, s):
return sum(map(s.startswith, words))
# B. Minimum Average Difference (opens new window)
For each index, get its prefix average and suffix average, find the index with the smallest absolute difference.
DETAILS
def minimumAverageDifference(self, A: List[int]) -> int:
ans, ave = -1, 1000001
left, right = 0, sum(A)
n = len(A)
for i, a in enumerate(A):
left += a
right -= a
if i < n - 1:
cur = abs(left//(i + 1) - right//(n - i - 1))
else:
cur = abs(left//n)
if cur < ave:
ave = cur
ans = i
return ans
public int minimumAverageDifference(int[] nums) {
long ans = -1, ave = 100001;
long left = 0, right = 0;
for (int num : nums)
right += num;
long cur;
for (int idx = 0; idx < nums.length; ++idx) {
left += nums[idx];
right -= nums[idx];
if (idx < nums.length - 1) {
cur = (long)Math.round(Math.abs(left/(idx + 1) - right/(nums.length - idx - 1)));
} else {
cur = (long)Math.round(Math.abs(left/(nums.length)));
}
if (cur < ave) {
ave = cur;
ans = idx;
}
}
return (int)ans;
}
# C. Count Unguarded Cells in the Grid (opens new window)
Run BFS starting from every guard, check which cells is visible from four directions.
Lastly, calculate the number of cells that are not visible to any guard.
DETAILS
def countUnguarded(self, m: int, n: int, G: List[List[int]], W: List[List[int]]) -> int:
A = [[0] * n for _ in range(m)]
gset = set([(x, y) for x, y in G])
seen = set([(x, y) for x, y in G] + [(x, y) for x, y in W])
for x, y in seen:
A[x][y] = 1
dirs = ((0, 1), (1, 0), (-1, 0), (0, -1))
for x, y in gset:
for dx, dy in dirs:
nx, ny = x + dx, y + dy
while 0 <= nx < m and 0 <= ny < n and A[nx][ny] != 1:
A[nx][ny] = 2
nx += dx
ny += dy
return sum(1 for i in range(m) for j in range(n) if A[i][j] == 0)
# D. Escape the Spreading Fire (opens new window)
Please refer to This LC Discussion (opens new window) for my solutions in English.
两种解法
解法一，BFS + 二分查找
假设我们直接出发(等待0天)，在每一天内，我们和火都要寻找下一天可以到达的格子，也就是与当前格子相邻并且尚未被访问的格子。
虽然题目说明我们先移动，火焰后移动，但这个顺序并不能给我们带来什么便利。所以这里我们可以换一个顺序：每天火焰先蔓延到下一个格子，然后我们再选择尚未被火烧过的邻居格子移动，这样一来，我们可以直接避免那些【火焰与我们在同一天到达某个格子】的情况。
.png)
接下来，需要判断是否能到达右下角。如果我们与火在同一天或者更早到达右下角则为成功，否则失败。
.png)
现在回到题目，假设我们等待x天，这等于先让火焰蔓延x天，之后回到第一张图的情况。朴素的想法是我们可以一天一天地尝试，先试试等待1天能否成功，等待2天能否成功...
所以这里可以用二分法来快速缩小范围。
.png)
DETAILS
def maximumMinutes(self, A: List[List[int]]) -> int:
m, n = len(A), len(A[0])
fires, seen = [], set()
f = collections.deque()
for i in range(m):
for j in range(n):
if A[i][j] == 1:
fires.append((i, j))
seen.add((i, j))
f.append((i, j))
dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
# If we stay for 'days' days.
def helper(days):
fire, seen = fires[::], set()
# Let the fire spreads for 'days' days.
while days > 0:
newfire = []
for i, j in fire:
for di, dj in dirs:
ni, nj = i + di, j + dj
if 0 <= ni < m and 0 <= nj < n and A[ni][nj] == 0 and (ni, nj) not in seen:
# If the fire reach us before we move, we fail.
if ni == 0 and nj == 0:
return False
seen.add((ni, nj))
newfire.append((ni, nj))
fire = newfire[::]
days -= 1
# Then let the fire and us move by turn (fire first).
safe = [(0, 0)]
while safe:
# Fire spreads first.
newfire = []
for i, j in fire:
for di, dj in dirs:
ni, nj = i + di, j + dj
if 0 <= ni < m and 0 <= nj < n and A[ni][nj] == 0 and (ni, nj) not in seen:
# If the fire reaches bot-right cell, if we are just one step close to bot-right cell
# We can still reach it, otherwise we fail. (Please refer to picture 2)
if ni == m - 1 and nj == n - 1:
if not ((m - 2, n - 1) in safe or (m - 1, n - 2) in safe):
return False
seen.add((ni, nj))
newfire.append((ni, nj))
fire = newfire[::]
# We move then.
newsafe = []
for i, j in safe:
for di, dj in dirs:
ni, nj = i + di, j + dj
# If we can reach bot-right cell, success.
if ni == m - 1 and nj == n - 1:
return True
if 0 <= ni < m and 0 <= nj < n and A[ni][nj] == 0 and (ni, nj) not in seen:
seen.add((ni, nj))
newsafe.append((ni, nj))
safe = newsafe[::]
# If there is no more cell for us to move before reaching bot-right cell, we fail.
return False
# check if always safe:
while f:
i, j = f.popleft()
for di, dj in dirs:
ni, nj = i + di, j + dj
if 0 <= ni < m and 0 <= nj < n and A[ni][nj] == 0 and (ni, nj) not in seen:
seen.add((ni, nj))
f.append((ni, nj))
f = collections.deque([(0, 0)])
while f:
i, j = f.popleft()
for di, dj in dirs:
ni, nj = i + di, j + dj
if 0 <= ni < m and 0 <= nj < n and A[ni][nj] == 0 and (ni, nj) not in seen:
if ni == m - 1 and nj == n - 1:
return 10 ** 9
seen.add((ni, nj))
f.append((ni, nj))
# Binary search to find maximum days:
l, r = 0, 10 ** 4
while l < r:
mid = (l + r + 1) // 2
if helper(mid):
l = mid
else:
r = mid - 1
return l if helper(l) else -1
解法二，BFS
我们可以找到这样一个规律：在任意一条从左上到右下的路上，假设这条路的格子序列是1,2,3...，我们领先火焰到达格子的时间是非递增的。
换句话说，如果我们在格子x处提前火焰y天到达，那么在从x到右下的剩余路上的每个格子，我们也只能最多提前火焰y天。原因在于我们与火焰的移动速度相同，那么我们身后的火焰总可以以同样的速度在我们身后保持同样的距离，这就是我们领先火焰天数的上限。
如下图所示
因此我们只需要两次BFS，分别构建【我】和【火焰】到达每个格子的最短时间。
根据之前讨论的规律，我们只需要保证：在到达右下角格子的时候我们领先火焰，就可以保证整条路径上我们都领先火焰。剩下的就是一些比较tricky的边界条件。
DETAILS
def maximumMinutes(self, A: List[List[int]]) -> int:
m, n = len(A), len(A[0])
dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
ppl_time = [[-1] * n for _ in range(m)]
fire_time = [[-1] * n for _ in range(m)]
# BFS for people's arrival for each cell.
ppl_front = collections.deque([(0, 0, 0)])
while ppl_front:
cx, cy, days = ppl_front.popleft()
ppl_time[cx][cy] = days
for dx, dy in dirs:
nx, ny = cx + dx, cy + dy
if 0 <= nx < m and 0 <= ny < n and A[nx][ny] == 0 and ppl_time[nx][ny] == -1:
ppl_front.append((nx, ny, days + 1))
# BFS for fire's arrival for each cell.
fire_front = collections.deque([(x, y, 0) for x in range(m) for y in range(n) if A[x][y] == 1])
while fire_front:
cx, cy, days = fire_front.popleft()
fire_time[cx][cy] = days
for dx, dy in dirs:
nx, ny = cx + dx, cy + dy
if 0 <= nx < m and 0 <= ny < n and A[nx][ny] == 0 and fire_time[nx][ny] == -1:
fire_front.append((nx, ny, days + 1))
# Check the arrival days for the bottom-right cell.
ppl_arrival = ppl_time[-1][-1]
fire_arrival = fire_time[-1][-1]
# Some edge cases.
if ppl_arrival == -1:
return -1
if fire_arrival == -1:
return 10 ** 9
if fire_arrival < ppl_arrival:
return -1
# Whether we are 'followed' by fire on both two pathes toward bot-right cell.
diff = fire_arrival - ppl_arrival
ppl_1, ppl_2 = ppl_time[-1][-2], ppl_time[-2][-1]
fire_1, fire_2 = fire_time[-1][-2], fire_time[-2][-1]
if ppl_1 > -1 and ppl_2 > -1 and (fire_1 - ppl_1 > diff or fire_2 - ppl_2 > diff):
return diff
return diff - 1