993. 二叉树的堂兄弟节点
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:
x_d, y_d, x_p, y_p = None, None, None, None
def dfs(root, parent, x, y, depth):
nonlocal x_d, y_d, x_p, y_p
if not root:
return
if root.val == x:
x_d = depth
x_p = parent
if root.val == y:
y_d = depth
y_p = parent
dfs(root.left, root, x ,y, depth + 1)
dfs(root.right, root, x ,y ,depth + 1)
dfs(root, None, x ,y, 0)
return x_d == y_d and x_p != y_p
542. 01 矩阵
class Solution:
def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
direct = [[0,1], [0,-1], [1, 0],[-1, 0]]
queue = []
n = len(mat)
m = len(mat[0])
vis = [[-1 for _ in range(m)] for _ in range(n)]
for i in range(n):
for j in range(m):
if mat[i][j]: continue
vis[i][j] = 0
queue.append((i, j, 0))
while queue:
cur = queue.pop(0)
for idx in direct:
x = cur[0] + idx[0]
y = cur[1] + idx[1]
if x < 0 or y < 0 or x >= n or y >= m: continue
if vis[x][y] != -1: continue
vis[x][y] = cur[2] + 1
queue.append((x, y, cur[2] + 1))
return vis
1091. 二进制矩阵中的最短路径
class Solution:
def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
if grid[0][0] == 1: return -1
direct = [[1, 0],[-1, 0], [0, 1], [0, -1], [1,1], [-1, 1], [1, -1], [-1, -1]]
n = len(grid)
m = len(grid[0])
vis = [[-1 for _ in range(m)] for _ in range(n)]
# queue = collections.deque()
queue = [(0, 0, 1)] # 元组
vis[0][0] = 1
while queue:
cur = queue.pop(0)
if cur[0] == n -1 and cur[1] == m - 1: return cur[2]
for idx in direct:
x = cur[0] + idx[0]
y = cur[1] + idx[1]
if x < 0 or y < 0 or x >= n or y >= m or grid[x][y]: continue
if vis[x][y] != -1: continue
vis[x][y] = 1
queue.append((x, y, cur[2] + 1))
return -1
752. 打开转盘锁
class Solution:
def openLock(self, deadends: List[str], target: str) -> int:
def get_s(s, ch, k):
tmp = list(s)
if k: tmp[ch] = chr(ord(tmp[ch]) + 1)
else: tmp[ch] = chr(ord(tmp[ch]) - 1)
if tmp[ch] > '9': tmp[ch] = '0'
if tmp[ch] < '0': tmp[ch] = '9'
return ''.join(tmp)
vis = set()
for deadend in deadends:
vis.add(deadend)
if '0000' in vis: return -1
queue = [('0000', 0)]
while queue:
cur = queue.pop(0)
if target == cur[0]: return cur[1]
for ch in range(4):
for k in range(2):
t = get_s(cur[0], ch, k)
if t in vis: continue
vis.add(t)
queue.append((t, cur[1] + 1))
return -1
面试题13. 机器人的运动范围
class Solution:
def movingCount(self, m: int, n: int, k: int) -> int:
vis = set()
direct = [[1, 0], [-1, 0], [0, 1],[0, -1]]
dsum = [0] * 100
for i in range(10):
for j in range(10):
dsum[i * 10 + j] = i + j
queue = [(0, 0)]
vis.add(0)
ans = 0
while queue:
cur = queue.pop(0)
ans += 1
for idx in direct:
x = cur[0] + idx[0]
y = cur[1] + idx[1]
if x < 0 or y < 0 or x >= m or y >= n or (x * n + y) in vis: continue
if dsum[x] + dsum[y] > k: continue
vis.add(x * n + y)
queue.append((x, y))
return ans
130. 被围绕的区域
class Solution:
def solve(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
def dfs(board, i ,j, m, n):
if i < 0 or j < 0 or i > m - 1 or j > n - 1: return
if board[i][j] == 'X' or board[i][j] == '#': return
board[i][j] = '#'
dfs(board, i + 1, j, m, n)
dfs(board, i - 1, j, m, n)
dfs(board, i, j + 1, m, n)
dfs(board, i, j - 1, m, n)
return
m, n = len(board), len(board[0])
i = 0
for j in range(n):
if board[i][j] == 'X' or board[i][j] == '#':continue
dfs(board, i, j, m, n)
i = m - 1
for j in range(n):
if board[i][j] == 'X' or board[i][j] == '#':continue
dfs(board, i, j, m, n)
j = 0
for i in range(m):
if board[i][j] == 'X' or board[i][j] == '#':continue
dfs(board, i, j, m, n)
j = n - 1
for i in range(m):
if board[i][j] == 'X' or board[i][j] == '#': continue
dfs(board, i, j, m, n)
for i in range(m):
for j in range(n):
if board[i][j] == '#': board[i][j] = 'O'
elif board[i][j] == 'O': board[i][j] = 'X'
return board
494. 目标和
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
if sum(nums) < target: return 0
def dfs(i, target, nums):
if i > len(nums) - 1:
if target == 0: return 1
return 0
ans = 0
if (i, target) in vis:
return vis[(i, target)]
ans += dfs(i + 1, target - nums[i], nums)
ans += dfs(i + 1, target + nums[i], nums)
vis[(i, target)] = ans
return ans
vis = dict()
return dfs(0, target, nums)
473. 火柴拼正方形
class Solution:
def makesquare(self, matchsticks: List[int]) -> bool:
if not matchsticks:
return False
total = sum(matchsticks)
if total % 4 != 0:
return False
avg = total // 4
matchsticks.sort(reverse=True)
def dfs(index, w_arr):
if index == len(matchsticks):
return all([i == 0 for i in w_arr])
for i in range(len(w_arr)):
if i > 0 and w_arr[i] == w_arr[i-1]:
continue
if w_arr[i] >= matchsticks[index]:
w_arr[i] -= matchsticks[index]
if dfs(index + 1, w_arr):
return True
w_arr[i] += matchsticks[index]
return False
return dfs(0, [avg, avg, avg,avg])
39. 组合总和
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
result = []
def dfs(candidates, target, res):
if target < 0:
return
if target == 0:
result.append(res)
for i, num in enumerate(candidates):
dfs(candidates[i:], target - num, res+[num])
dfs(candidates, target, [])
return result
51. N 皇后
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
result = []
queen = [-1] * n
columns = set()
dia1 = set()
dia2 = set()
row = ['.'] * n
def dfs(row):
if row == n:
item = get_item()
result.append(item)
else:
for i in range(n):
if i in columns or row - i in dia1 or row + i in dia2:
continue
queen[row] = i
columns.add(i)
dia1.add(row - i)
dia2.add(row + i)
dfs(row + 1)
columns.remove(i)
dia1.remove(row - i)
dia2.remove(row + i)
def get_item():
item = []
for i in range(n):
row[queen[i]] = 'Q'
item.append("".join(row))
row[queen[i]] = '.'
return item
dfs(0)
return result
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/76883.html
