做旅游海报的软件或是网站,做网站要招什么样的程序员,全国企业信息查询官网系统,网站建设是基于矩阵搜索1.leetcode-200. 岛屿数量2.leetcode-695. 岛屿的最大面积3.leetcode-463. 岛屿的周长4.剑指 Offer 12. 矩阵中的路径5.leetcode-329. 矩阵中的最长递增路径6.leetcode-1091. 二进制矩阵中的最短路径1.leetcode-200. 岛屿数量
给你一个由 ‘1’#xff08;陆地#…
矩阵搜索1.leetcode-200. 岛屿数量2.leetcode-695. 岛屿的最大面积3.leetcode-463. 岛屿的周长4.剑指 Offer 12. 矩阵中的路径5.leetcode-329. 矩阵中的最长递增路径6.leetcode-1091. 二进制矩阵中的最短路径1.leetcode-200. 岛屿数量
给你一个由 ‘1’陆地和 ‘0’水组成的的二维网格请你计算网格中岛屿的数量。
岛屿总是被水包围并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。
此外你可以假设该网格的四条边均被水包围。
class Solution(object):def numIslands(self, grid):def dfs(r,c):grid[r][c]0for i,j in [(r1,c),(r-1,c),(r,c1),(r,c-1)]:if 0im and 0jn and grid[i][j]1:# print(i,j)dfs(i,j)count0mlen(grid)if m0:return countnlen(grid[0])for r in range(m):for c in range(n):if grid[r][c]1:count1dfs(r,c)return count2.leetcode-695. 岛屿的最大面积
给定一个包含了一些 0 和 1 的非空二维数组 grid 。
一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0代表水包围着。
找到给定的二维数组中最大的岛屿面积。(如果没有岛屿则返回面积为 0 。)
class Solution(object):def __init__(self):self.count0def maxAreaOfIsland(self, grid):def dfs(r,c):grid[r][c]0 self.count1for i,j in [(r1,c),(r-1,c),(r,c1),(r,c-1)]:if 0im and 0jn and grid[i][j]1:dfs(i,j)res0mlen(grid)if m0:return resnlen(grid[0])for r in range(m):for c in range(n):if grid[r][c]1:self.count0dfs(r,c)resmax(res,self.count)return res3.leetcode-463. 岛屿的周长
给定一个包含 0 和 1 的二维网格地图其中 1 表示陆地 0 表示水域。 网格中的格子水平和垂直方向相连对角线方向不相连。整个网格被水完全包围但其中恰好有一个岛屿或者说一个或多个表示陆地的格子相连组成的岛屿。
岛屿中没有“湖”“湖” 指水域在岛屿内部且不和岛屿周围的水相连。格子是边长为 1 的正方形。网格为长方形且宽度和高度均不超过 100 。计算这个岛屿的周长。 只有一个岛屿 从陆地走向边界/水域边长1。判断下一个坐标是边界位置还是水域从而改变总周长。
class Solution(object):def __init__(self):self.res 0def islandPerimeter(self, grid):def dfs(i,j):# print(i,j, self.res)grid[i][j] 2for r, c in [(i1, j), (i-1, j), (i, j1), (i, j-1)]: # 走四个方向看会发生什么情况嘛if r 0 or r m or c 0 or c n: # 往边界走了一格,# print(bian,i,j,r,c)self.res 1if 0 r m and 0 c n and grid[r][c] 0 : # 往水域走了一格# print(shui,i,j,r,c)self.res 1if 0 r m and 0 c n and grid[r][c] 1: dfs(r,c)m len(grid)if m 0:return 0n len(grid[0])for i in range(m): # 要区别是走过的陆地不能走还是原本就是水域不能走for j in range(n):# print(i,j)if grid[i][j] 1:dfs(i,j)return self.resgrid[[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
so Solution()
print(so.islandPerimeter(grid))4.剑指 Offer 12. 矩阵中的路径
请设计一个函数用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格那么该路径不能再次进入该格子。例如在下面的3×4的矩阵中包含一条字符串“bfce”的路径路径中的字母用加粗标出。
[[“a”,“b”,“c”,“e”], [“s”,“f”,“c”,“s”], [“a”,“d”,“e”,“e”]]
但矩阵中不包含字符串“abfb”的路径因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后路径不能再次进入这个格子。
约束不能两次经过同一个点 矩阵中的每一个元素dfs visted矩阵上下左右匹配当前字符 visted矩阵通过标记字符来实现
递归前保证矩阵下标的合理性递归出口由匹配情况控制 1.word 2.len(word) 1 and board[i][j] word[0] 3.board[i][j] ! word[0] 其他情况都是往下递归
class Solution(object):def exist(self, board, word):# board[i][j] 都进行深度优先匹配def dfs(i,j,word):if len(word) 0: # word 为空字符串时,匹配完成return Trueif len(word) 1 and board[i][j] word[0]: # 防止[i][j]下一步都是边界且是访问过的情况虽然已经匹配但是结果是false[[a]]areturn Trueif board[i][j] ! word[0]: # 第一字符不匹配完全不用递归直接输出return Falsetmp board[i][j] # 完全没有考虑不能重复走 board[i][j] Nonefor r,c in [(i1,j),(i-1,j),(i,j1),(i,j-1)]: # 第一哥字符匹配递归处理if 0 r m and 0 c n:if dfs(r,c,word[1:]): # 如果四个方向中有一格方向是可行的就返回True return Trueboard[i][j] tmpreturn False # 第一个字符匹配了但是后面的都不配输出Falsem len(board)if m 0:return word n len(board[0])for i in range(m):for j in range(n):if dfs(i,j,word):return Truereturn False # 所有遍历过了没有就输出false#[[a]],a
#[[a]],a5.leetcode-329. 矩阵中的最长递增路径
给定一个整数矩阵找出最长递增路径的长度。 对于每个单元格你可以往上下左右四个方向移动。 你不能在对角线方向上移动或移动到边界外即不允许环绕。
输入: nums
[[9,9,4],[6,6,8],[2,1,1]
]
输出: 4
解释: 最长递增路径为 [1, 2, 6, 9]。keypoint: 1.递增天然的不会两次走过同一个单元 2.dp[i][j] 以matrix[i][j]开始的最长递增路径
class Solution(object):def longestIncreasingPath_cyy(self, matrix):def dfs(i,j):if dp[i][j]:return dp[i][j]for r, c in [(i 1, j), (i - 1, j), (i, j 1), (i, j - 1)]:if 0 r m and 0 c n and matrix[r][c] matrix[i][j]:dp[i][j] max(dp[i][j], dfs(r,c)) # 下一层的最大深度dp[i][j] 1 # 本层的深度在下层深度的基础上1return dp[i][j]m len(matrix)if m 0:return 0n len(matrix[0])dp [[0] * n for _ in range(m)] # dp[i][j] 开始的最长路径res 0for i in range(m):for j in range(n):res max(res,dfs(i,j))# print(dp)return res6.leetcode-1091. 二进制矩阵中的最短路径
在一个 N × N 的方形网格中每个单元格有两种状态空0或者阻塞1。
一条从左上角到右下角、长度为 k 的畅通路径由满足下述条件的单元格 C_1, C_2, …, C_k 组成
相邻单元格 C_i 和 C_{i1} 在八个方向之一上连通此时C_i 和 C_{i1} 不同且共享边或角 C_1 位于 (0, 0)即值为 grid[0][0] C_k 位于 (N-1, N-1)即值为 grid[N-1][N-1] 如果 C_i 位于 (r, c)则 grid[r][c] 为空即grid[r][c] 0 返回这条从左上角到右下角的最短畅通路径的长度。如果不存在这样的路径返回 -1 。
最短路径问题BFS
def shortestPathBinaryMatrix(self, grid):n len(grid)if grid[0][0] 1 or grid[-1][-1] 1:return -1if n 1: # [[0]]这种特殊情况return 1res 1que [(0,0)]while(que):l len(que)for i in range(l):(i,j) que.pop(0)for (r,c) in [(i-1,j-1),(i-1,j),(i-1,j1),(i,j-1),(i,j1),(i1,j-1),(i1,j),(i1,j1)]:if 0 r n and 0 c n and grid[r][c] 0: # 有效坐标 并且能走if r n-1 and c n-1: # 能走到了终点return res 1que.append((r,c)) # 能走没到终点grid[r][c] 1 # 已经走过的地方不能再走不然就会一直进队出队res 1 # 广度优先的层数return -1
