网站导航
> 文章列表 > LeetCode 第十四天 huawei测试准备 python （BFS DFS 回溯）

LeetCode 第十四天 huawei测试准备 python （BFS DFS 回溯）

网友: 文章列表 2024-03-21 17:32:53

LeetCode 第十四天 huawei测试准备 python （BFS DFS 回溯）

以下题目来源力扣
127. 单词接龙
字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> … -> sk：

每一对相邻的单词只差一个字母。
对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
sk == endWord
给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。
太难了 我写完别的再学习这个

  1. 被围绕的区域
    给你一个 m x n 的矩阵 board ，由若干字符 ‘X’ 和 ‘O’ ，找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。
    输入：board = [[“X”,“X”,“X”,“X”],[“X”,“O”,“O”,“X”],[“X”,“X”,“O”,“X”],[“X”,“O”,“X”,“X”]]
    输出：[[“X”,“X”,“X”,“X”],[“X”,“X”,“X”,“X”],[“X”,“X”,“X”,“X”],[“X”,“O”,“X”,“X”]]
    解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 ‘O’ 都不会被填充为 ‘X’。 任何不在边界上，或不与边界上的 ‘O’ 相连的 ‘O’ 最终都会被填充为 ‘X’。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
class Solution:def solve(self, board: List[List[str]]) -> None:"""Do not return anything, modify board in-place instead."""m=len(board)n=len(board[0])def dfs(x,y):if 0<=x<m and 0<=y<n and board[x][y]=='O':board[x][y]='A'dfs(x-1,y)dfs(x+1,y)dfs(x,y-1)dfs(x,y+1)for i in range(0,m):dfs(i,0)dfs(i,n-1)for i in range(0,n):dfs(0,i)dfs(m-1,i)for i in range(0,m):for j in range(0,n):if board[i][j]=='A':board[i][j]='O'elif board[i][j]=='O':board[i][j]='X'return board

529. 扫雷游戏
让我们一起来玩扫雷游戏！

给你一个大小为 m x n 二维字符矩阵 board ，表示扫雷游戏的盘面，其中：

‘M’ 代表一个 未挖出的 地雷，
‘E’ 代表一个 未挖出的 空方块，
‘B’ 代表没有相邻（上，下，左，右，和所有4个对角线）地雷的 已挖出的 空白方块，
数字（‘1’ 到 ‘8’）表示有多少地雷与这块 已挖出的 方块相邻，
‘X’ 则表示一个 已挖出的 地雷。
给你一个整数数组 click ，其中 click = [clickr, clickc] 表示在所有 未挖出的 方块（‘M’ 或者 ‘E’）中的下一个点击位置（clickr 是行下标，clickc 是列下标）。

根据以下规则，返回相应位置被点击后对应的盘面：

如果一个地雷（‘M’）被挖出，游戏就结束了- 把它改为 ‘X’ 。
如果一个 没有相邻地雷 的空方块（‘E’）被挖出，修改它为（‘B’），并且所有和其相邻的 未挖出 方块都应该被递归地揭露。
如果一个 至少与一个地雷相邻 的空方块（‘E’）被挖出，修改它为数字（‘1’ 到 ‘8’ ），表示相邻地雷的数量。
如果在此次点击中，若无更多方块可被揭露，则返回盘面。

class Solution:def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:m=len(board)n=len(board[0])dir_x = [0, 1, 0, -1, 1, 1, -1, -1]dir_y= [1, 0, -1, 0, 1, -1, 1, -1]def explore(x,y): #是雷的话爆炸board[x][y]='X'def reveal(x,y): #递归揭露了所有不是地雷的未点击方块count=0for i in range(0,8):tx=x+dir_x[i]ty=y+dir_y[i]if 0<=tx<m and 0<=ty<n and board[tx][ty]=='M':count=count+1if count>0:board[x][y]=str(count)else:board[x][y]='B'for i in range(0,8):tx=x+dir_x[i]ty=y+dir_y[i]if 0<=tx<m and 0<=ty<n and board[tx][ty]=='E':reveal(tx,ty)r=click[0]c=click[1]if board[r][c]=='M':explore(r,c)else:reveal(r,c)return board

815. 公交路线
给你一个数组 routes ，表示一系列公交线路，其中每个 routes[i] 表示一条公交线路，第 i 辆公交车将会在上面循环行驶。

例如，路线 routes[0] = [1, 5, 7] 表示第 0 辆公交车会一直按序列 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> … 这样的车站路线行驶。
现在从 source 车站出发（初始时不在公交车上），要前往 target 车站。 期间仅可乘坐公交车。

求出 最少乘坐的公交车数量 。如果不可能到达终点车站，返回 -1 。
示例 1：

输入：routes = [[1,2,7],[3,6,7]], source = 1, target = 6
输出：2
解释：最优策略是先乘坐第一辆公交车到达车站 7 , 然后换乘第二辆公交车到车站 6 。

广度遍历

class Solution:def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:# 每个车站可以乘坐的公交车stations = defaultdict(set)for i, stops in enumerate(routes):for stop in stops:stations[stop].add(i)# 每个公交车线路可以到达的车站routes = [set(x) for x in routes]q = deque([(source, 0)])# 已经乘坐了的公交车buses = set()# 已经到达了的车站stops = {source}while q:pos, cost = q.popleft()if pos == target:return cost# 当前车站中尚未乘坐的公交车for bus in stations[pos] - buses:# 该公交车尚未到达过的车站for stop in routes[bus] - stops:buses.add(bus)stops.add(stop)q.append((stop, cost + 1))return -1作者：himymBen
链接：https://leetcode.cn/problems/bus-routes/solution/python-bfs-ba-gong-jiao-kan-zuo-zheng-ti-8w0i/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

困难题好难 俺要去跑步了 再见

网络标签：

相关问题