剑指 Offer 13. 机器人的运动范围
程序员文章站
2022-04-03 10:01:48
剑指 Offer 13. 机器人的运动范围链接:https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/典型的用dfs或者bfs的题目,另外还有一种dp的方式,因为这里的坐标都是递增的,所以可以简化的只考虑值向右或者向下移动即可。bfs:注意python中计算数的每个位之和的方式,还有用set来判断当前位置是否被访问过class Solution: def movingCount(se......
剑指 Offer 13. 机器人的运动范围
链接:
https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/
典型的用dfs或者bfs的题目,另外还有一种dp的方式,因为这里的坐标都是递增的,所以可以简化的只考虑值向右或者向下移动即可。
bfs:注意python中计算数的每个位之和的方式,还有用set来判断当前位置是否被访问过
class Solution:
def movingCount(self, m: int, n: int, k: int) -> int:
def f(num):
return sum(int(i) for i in str(num))
dx = [0, 1]
dy = [1, 0]
ans = 1
queue, vis = [], set()
queue.append((0, 0))
vis.add((0, 0))
while queue:
x, y = queue.pop(0)
for i in range(len(dx)):
tx = x + dx[i]
ty = y + dy[i]
if tx < 0 or tx >= m or ty < 0 or ty >= n or f(tx)+f(ty)>k or (tx, ty) in vis:
continue
ans += 1
queue.append((tx, ty))
vis.add((tx, ty))
return ans
dfs的做法
class Solution:
def movingCount(self, m: int, n: int, k: int) -> int:
def f(num):
return sum(int(i) for i in str(num))
def dfs(x, y):
if x < 0 or x >= m or y < 0 or y >= n or f(x)+f(y)>k or (x, y) in vis:
return 0
vis.add((x, y))
dfs(x+1, y)
dfs(x, y+1)
vis = set()
dfs(0, 0)
return len(vis)
递推:如果(i,j)是满足要求的,只要(i-1,j)或者(i,j-1)是可达的就证明(i,j)也是可达的
class Solution:
def movingCount(self, m: int, n: int, k: int) -> int:
def f(num):
return sum(int(i) for i in str(num))
vis = [[0 for j in range(n)] for i in range(m)]
vis[0][0] = 1
ans = 1
for i in range(m):
for j in range(n):
if (i == 0 and j == 0) or f(i)+f(j)>k:
continue
if (i-1) >= 0:
vis[i][j] = vis[i][j] | vis[i-1][j]
if (j-1) >= 0:
vis[i][j] = vis[i][j] | vis[i][j-1]
ans += vis[i][j]
return ans
本文地址:https://blog.csdn.net/breeze_blows/article/details/107645452
上一篇: 三国五虎上将之首是谁?是关羽还是张飞呢?
下一篇: python移动均线SMA及双均线策略