2133-Jammy

, , ,

# 剑指 Offer 12. 矩阵中的路径

class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
def dfs(i, j, k):
if not 0 <= i < len(board) or not 0 <= j < len(board[0]) or board[i][j] != word[k]: return False
if k == len(word) - 1: return True
board[i][j] = ''
res = dfs(i + 1, j, k + 1) or dfs(i - 1, j, k + 1) or dfs(i, j + 1, k + 1) or dfs(i, j - 1, k + 1)
board[i][j] = word[k]
return res

for i in range(len(board)):
for j in range(len(board[0])):
if dfs(i, j, 0): return True
return False

if not 0 <= i < len(board) or not 0 <= j < len(board[0])

dfs(i + 1, j, k + 1) or dfs(i - 1, j, k + 1) or dfs(i, j + 1, k + 1) or dfs(i, j - 1, k + 1)

# 剑指 Offer 13. 机器人的运动范围

def movingCount(self, m: int, n: int, k: int) -> int:

def dfs(i, j):
# 边界定义
if not 0 <= i < m or not 0 <= j < n or (self.cal_sum(i) + self.cal_sum(j)) > k or (i, j) in visited: return 0
return 1 + dfs(i+1, j) + dfs(i, j+1)

visited = set()
return dfs(0, 0)

def cal_sum(self, num):
s = 0
while num > 0:
s += num % 10
num = num // 10
return s

def cal_sum(self, num):
s = 0
while num > 0:
s += num % 10
num = num // 10
return s

class Solution:
def movingCount(self, m: int, n: int, k: int) -> int:
queue, visited = [(0, 0, 0, 0)], set()
while queue:
i, j, si, sj = queue.pop(0)
if i >= m or j >= n or k < si + sj or (i, j) in visited: continue
queue.append((i + 1, j, si + 1 if (i + 1) % 10 else si - 8, sj))
queue.append((i, j + 1, si, sj + 1 if (j + 1) % 10 else sj - 8))
return len(visited)

queue.append((i + 1, j, si + 1 if (i + 1) % 10 else si - 8, sj))

# 剑指 Offer 65. 不用加减乘除做加法

class Solution:
def add(self, a: int, b: int) -> int:
x = 0xffffffff
a, b = a & x, b & x
while b != 0:
a, b = (a ^ b), (a & b) << 1 & x
return a if a <= 0x7fffffff else ~(a ^ x)

# 剑指 Offer 56 – I. 数组中数字出现的次数

class Solution:
def singleNumbers(self, nums: List[int]) -> List[int]:
x, y, n, m = 0, 0, 0, 1
for num in nums:         # 1. 遍历异或
n ^= num
while n & m == 0:        # 2. 循环左移，计算 m
m <<= 1
for num in nums:         # 3. 遍历 nums 分组
if num & m: x ^= num # 4. 当 num & m != 0
else: y ^= num       # 4. 当 num & m == 0
return x, y              # 5. 返回出现一次的数字

# 剑指 Offer 39. 数组中出现次数超过一半的数字

def majorityElement(self, nums: List[int]) -> int:
for num in nums:
mode = num
elif num == mode:
return mode

# 剑指 Offer 66. 构建乘积数组

def constructArr(self, a: List[int]) -> List[int]:
if not a: return []
length = len(a)
left, right = [1] * length, [1] * length
left[0], right[-1] = 1, 1
res = [1] * length
for i in range(1, length):
left[i] = left[i-1] * a[i-1]
for i in range(length-2, -1, -1):
right[i] = right[i+1] * a[i+1]
for i in range(length):
res[i] = left[i] * right[i]
return res

class Solution:
def constructArr(self, a: List[int]) -> List[int]:
b, tmp = [1] * len(a), 1
for i in range(1, len(a)):
b[i] = b[i - 1] * a[i - 1] # 下三角
for i in range(len(a) - 2, -1, -1):
tmp *= a[i + 1]            # 上三角
b[i] *= tmp                # 下三角 * 上三角
return b

Vieu3.3主题

Q Q 登 录