[17]岛屿数量和电话号码的字母组合

*内容来自leetcode

1.岛屿数量

题目要求

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

示例 2：

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

思路

没有思路

三种方法，BFS，DFS，并查集

DFS

我们可以将二维网格看成一个无向图，竖直或水平相邻的 1 之间有边相连。

为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 1，则以其为起始节点开始进行深度优先搜索。在深度优先搜索的过程中，每个搜索到的 1 都会被重新标记为 0。

最终岛屿的数量就是我们进行深度优先搜索的次数。

class Solution:def dfs(self,grid,r,l):grid[r][l] = '0'n,m = len(grid[0]),len(grid)#循环遍历四周的节点for i,j in [(r-1,l),(r+1,l),(r,l+1),(r,l-1)]:if 0 <= i < m and 0 <= j < n and grid[i][j] == '1':self.dfs(grid,i,j)def numIslands(self, grid: List[List[str]]) -> int:#DFScount = 0n = len(grid[0])m = len(grid)for i in range(m):for j in range(n):if grid[i][j] == "1":count += 1 self.dfs(grid,i,j)return count

BFS

为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 1，则将其加入队列，开始进行广度优先搜索。在广度优先搜索的过程中，每个搜索到的 1 都会被重新标记为 0。直到队列为空，搜索结束。

class Solution:def numIslands(self, grid: List[List[str]]) -> int:#BFScount = 0n = len(grid[0])m = len(grid)if m == 0:return 0for i in range(m):for j in range(n):if grid[i][j] == '1':count += 1grid[i][j] == '0'duilie = collections.deque([(i,j)])while duilie:row,col = duilie.popleft()for x,y in [(row+1,col),(row-1,col),(row,col+1),(row,col-1)]:if 0 <= x < m and 0 <= y < n and grid[x][y] == '1':duilie.append((x,y))grid[x][y] = '0'return count

并查集

并查集的相关知识可见于：

算法学习笔记(1) : 并查集 - 知乎

针对当前的问题

为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 1，则将其与相邻四个方向上的 11在并查集中进行合并。

最终岛屿的数量就是并查集中连通分量的数目。

#并查集
class FindUnion:def __init__(self,grid):m = len(grid[0])n = len(grid)self.fa = [-1]*(m*n)self.count = 0for i in range(n):for j in range(m):if grid[i][j] == '1':self.fa[i*m+j] = i*m+jself.count += 1def find(self,i):if self.fa[i] == i:return ielse:return self.find(self.fa[i])def getUnion(self,x,y):headx = self.find(x)heady = self.find(y)if headx != heady:self.fa[heady] = headxself.count -= 1def getCount(self):return self.countclass Solution:def numIslands(self, grid: List[List[str]]) -> int:union = FindUnion(grid)m = len(grid[0])n = len(grid)for i in range(n):for j in range(m):if grid[i][j] == '1':grid[i][j] = '0'for x,y in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:if 0 <= x < n and 0 <= y < m and grid[x][y] == '1':union.getUnion(i*m+j,x*m+y)return union.getCount()

 在上述的实现中，使用的是最简单的并查集。没有对合并的过程进行优化。对并查集优化的代码如下

class FindUnion:def __init__(self,grid):m = len(grid[0])n = len(grid)self.fa = [-1]*(m*n)self.rank = [0]*(m*n)self.count = 0for i in range(n):for j in range(m):if grid[i][j] == '1':self.fa[i*m+j] = i*m+jself.count += 1#对find过程进行了优化，是每个节点直接连接到根节点def find(self,i):if self.fa[i] == i:return ielse:self.fa[i] = self.find(self.fa[i])return self.fa[i]#对Union过程进行了优化，让并查集的树层次结构更少，加快速度def getUnion(self,x,y):headx = self.find(x)heady = self.find(y)if headx != heady:if self.rank[headx] <= self.rank[heady]:self.fa[headx] = headyelse:self.fa[heady] = headxif self.rank[headx] == self.rank[heady] and headx != heady:self.rank[heady] += 1self.count -= 1def getCount(self):return self.count

——中级算法-树和图部分完结——

——中级算法-回溯算法——

2.电话号码的字母组合

题目要求

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：

输入：digits = ""
输出：[]
示例 3：

输入：digits = "2"
输出：["a","b","c"]

思路

先初始化一个空的result字符列表，列表的大小由电话号码决定。然后根据电话号码把对应字母添加到result字符串中。具体见代码及注释

class Solution:def checkNum(self,digit,result):times = len(result)#生成要添加的字符列表#生成的字符列表大小与result列表大小一致if digit == '2':strs = ['a','b','c']*(times//3)if digit == '3':strs = ['d','e','f']*(times//3)if digit == '4':strs = ['g','h','i']*(times//3)if digit == '5':strs = ['j','k','l']*(times//3)if digit == '6':strs = ['m','n','o']*(times//3)if digit == '7':strs = ['p','q','r','s']*(times//4)if digit == '8':strs = ['t','u','v']*(times//3)if digit == '9':strs = ['w','x','y','z']*(times//4)for i in range(len(result)):result[i] = result[i] + strs[I]#将每次得到的结果排序，而每次新添加的strs列表是没有排序的#这样才能保证得到的列表没有重复的result.sort()return resultdef letterCombinations(self, digits: str) -> List[str]:if not digits:return []n = len(digits)#获取最后结果的列表大小nums = 1for i in range(n):if digits[i] == '7' or digits[i] == '9':nums *= 4else:nums *= 3result = [''] * nums#往结果列表里添加新字母for i in range(n):result = self.checkNum(digits[i],result)return result

官方给出的，回溯法

首先使用哈希表存储每个数字对应的所有可能的字母，然后进行回溯操作。

回溯过程中维护一个字符串，表示已有的字母排列（如果未遍历完电话号码的所有数字，则已有的字母排列是不完整的）。该字符串初始为空。每次取电话号码的一位数字，从哈希表中获得该数字对应的所有可能的字母，并将其中的一个字母插入到已有的字母排列后面，然后继续处理电话号码的后一位数字，直到处理完电话号码中的所有数字，即得到一个完整的字母排列。然后进行回退操作，遍历其余的字母排列。

回溯算法用于寻找所有的可行解，如果发现一个解不可行，则会舍弃不可行的解。在这道题中，由于每个数字对应的每个字母都可能进入字母组合，因此不存在不可行的解，直接穷举所有的解即可。

class Solution:def letterCombinations(self, digits: str) -> List[str]:if not digits:return []phoneMap = {"2": "abc","3": "def","4": "ghi","5": "jkl","6": "mno","7": "pqrs","8": "tuv","9": "wxyz",}def trackBack(index):if index == len(digits):combinations.append("".join(combination))else:digit = digits[index]for letter in phoneMap[digit]:combination.append(letter)trackBack(index+1)combination.pop()combination = list()combinations = list()trackBack(0)return combinations

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！