面试题 03.06. 动物收容所
from collections import deque
class AnimalShelf:
def __init__(self):
self.cat = deque()
self.dog = deque()
self.time = 0
def enqueue(self, animal: List[int]) -> None:
if animal[1] == 0:
self.cat.append((animal[0], self.time))
else:
self.dog.append((animal[0], self.time))
self.time += 1
def dequeueAny(self) -> List[int]:
if self.cat and not self.dog:
return [self.cat.popleft()[0], 0]
elif not self.cat and self.dog:
return [self.dog.popleft()[0], 1]
elif self.cat and self.dog:
cat = self.cat.popleft()
dog = self.dog.popleft()
if cat[1] > dog[1]:
self.cat.appendleft(cat)
return [dog[0], 1]
else:
self.dog.appendleft(dog)
return [cat[0], 0]
return [-1, -1]
def dequeueDog(self) -> List[int]:
if self.dog:
return [self.dog.popleft()[0], 1]
return [-1, -1]
def dequeueCat(self) -> List[int]:
if self.cat:
return [self.cat.popleft()[0], 0]
return [-1, -1]
506. 相对名次
class Solution:
def findRelativeRanks(self, score: List[int]) -> List[str]:
ans = [''] * len(score)
for i in range(len(score)):
score[i] = (score[i], i)
score.sort(reverse=True)
if len(score) >= 1:
ans[score[0][1]] = "Gold Medal"
if len(score) >= 2:
ans[score[1][1]] = "Silver Medal"
if len(score) >= 3:
ans[score[2][1]] = "Bronze Medal"
for i in range(3, len(score)):
ans[score[i][1]] = str(i + 1)
return ans1254. 统计封闭岛屿的数目
class Solution:
def __init__(self):
self.next = [[-1, 0], [1, 0], [0, 1], [0, -1]]
def closedIsland(self, grid: List[List[int]]) -> int:
ans = 0
for i in range(len(grid)):
for j in range(len(grid[i])):
if grid[i][j] == 0:
if self.dfs(grid, i, j, i, j):
ans += 1
return ans
def dfs(self, grid, x, y, from_x, from_y):
if x < 0 or x >= len(grid) or y < 0 or y >= len(grid[0]):
return False
if grid[x][y] == 1 or grid[x][y] == 2:
return True
grid[x][y] = 2
ans = [False] * 4
for i in range(len(self.next)):
next_x = self.next[i][0] + x
next_y = self.next[i][1] + y
if next_y == from_y and next_x == from_x:
ans[i] = True
continue
ans[i] = self.dfs(grid, next_x, next_y, x, y)
return all(ans)1233. 删除子文件夹
官方题解优化了剪枝过程
对于字典树中的每一个节点，我们仅需要存储一个变量 ${ref}$，如果 $ref≥0$ ，说明该节点对应着$ folder[ref ]$，否则（$ref=−1$）说明该节点只是一个中间节点。
class Solution:
def removeSubfolders(self, folder: List[str]) -> List[str]:
tree = {}
for i in range(len(folder)):
folder[i] = folder[i].split('/')
level = tree
for j in range(1, len(folder[i])):
tmp = level.get(folder[i][j], None)
if tmp is None:
level[folder[i][j]] = {}
tmp = level[folder[i][j]]
level = tmp
for i in range(len(folder)):
f = folder[i]
level = tree
for j in range(1, len(f)):
tmp = level.get(f[j], None)
if tmp is None:
break
level = tmp
else:
level.clear()
ans = []
self.dfs(tree, ans, '')
return ans
def dfs(self, level: dict, ans, s):
if not level:
ans.append(s)
for k, v in level.items():
self.dfs(v, ans, s + f'/{k}')393. UTF-8 编码验证
class Solution:
def validUtf8(self, data: List[int]) -> bool:
length = 0
for i in range(len(data)):
if length == 0:
if data[i] >> 7 == 0b0:
length = 1
elif data[i] >> 5 == 0b110:
length = 2
elif data[i] >> 4 == 0b1110:
length = 3
elif data[i] >> 3 == 0b11110:
length = 4
else:
return False
else:
if data[i] >> 6 != 0b10:
return False
length -= 1
return True if length == 0 else False741. 摘樱桃
超时，假装做出来了
from functools import cache
class Solution:
def __init__(self):
self.dp = None
self.next_step = [[1, 0], [0, 1]]
self.n = 0
self.grid = None
def cherryPickup(self, grid: List[List[int]]) -> int:
self.n = n = len(grid)
self.grid = grid
self.dp = [[[[None for _ in range(n)] for _ in range(n)] for _ in range(n)] for _ in range(n)]
return max(0, self.dp_func(0, 0, 0, 0))
@cache
def dp_func(self, x0, y0, x1, y1):
if x0 == self.n - 1 and y0 == self.n - 1:
return self.grid[self.n - 1][self.n - 1]
if self.dp[x0][y0][x1][y1] is not None:
return self.dp[x0][y0][x1][y1]
if x0 == x1 and y0 == y1:
cur = self.grid[x0][y0]
else:
cur = self.grid[x0][y0] + self.grid[x1][y1]
res = float('-inf')
for i in range(len(self.next_step)):
next_x0 = x0 + self.next_step[i][0]
next_y0 = y0 + self.next_step[i][1]
if next_x0 < 0 or next_x0 >= self.n or next_y0 < 0 or next_y0 >= self.n or self.grid[next_x0][next_y0] == -1:
continue
for j in range(len(self.next_step)):
next_x1 = x1 + self.next_step[j][0]
next_y1 = y1 + self.next_step[j][1]
if next_x1 < 0 or next_x1 >= self.n or next_y1 < 0 or next_y1 >= self.n or self.grid[next_x1][next_y1] == -1:
continue
res = max(res, cur + self.dp_func(next_x0, next_y0, next_x1, next_y1))
self.dp[x0][y0][x1][y1] = res
return res
Comments | NOTHING