*Content from leetcode
1. Number of islands
Subject requirements
Given a 2D grid consisting of ‘1’ (land) and ‘0’ (water), please count the number of islands in the grid.
Islands are always surrounded by water, and each island can only be formed by connecting horizontally and/or vertically adjacent land.
Also, you can assume that the mesh is surrounded by water on all four sides.
Example 1:
Input: grid = [
[“1″,”1″,”1″,”1″,”0”],
[“1″,”1″,”0″,”1″,”0”],
[“1″,”1″,”0″,”0″,”0”],
[“0″,”0″,”0″,”0″,”0”]
]
Output: 1
Example 2:
Input: grid = [
[“1″,”1″,”0″,”0″,”0”],
[“1″,”1″,”0″,”0″,”0”],
[“0″,”0″,”1″,”0″,”0”],
[“0″,”0″,”0″,”1″,”1”]
]
Output: 3
train of thought
no idea
Three methods, BFS, DFS, and check
DFS
We can think of a two-dimensional grid as an undirected graph, where vertically or horizontally adjacent 1s are connected by edges.
To find the number of islands, we can scan the entire 2D grid. If a position is 1, start a depth-first search with it as the starting node. During the depth-first search, each found 1 is remarked as a 0.
The final number of islands is how many times we do a depth-first search.
class Solution:
def dfs(self, grid, r, l):
grid[r][l] = '0'
n,m = len(grid[0]),len(grid)
# Loop through the surrounding nodes
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:
#DFS
count = 0
n = 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
To find the number of islands, we can scan the entire 2D grid. If a position is 1, it is enqueued and a breadth-first search begins. During the breadth-first search, each found 1 is remarked as a 0. Until the queue is empty, the search ends.
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
#BFS
count = 0
n = len(grid[0])
m = len(grid)
if m == 0:
return 0
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
count + = 1
grid[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
And lookup
The relevant knowledge of the collection can be found in:
Algorithm Study Notes (1) : Union and Check Set bzdww
for current issues
To find the number of islands, we can scan the entire 2D grid. If a position is 1, it is merged with 11 in the adjacent four directions in the union search set.
The final number of islands is the number of connected components in the union search set.
# and search set
class FindUnion:
def __init__(self, grid):
m = len(grid[0])
n = len(grid)
self.fa = [-1]*(m*n)
self.count = 0
for i in range(n):
for j in range(m):
if grid[i][j] == '1':
self.fa[i*m + j] = i*m + j
self.count += 1
def find(self,i):
if self.fa[i] == i:
return i
else:
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] = headx
self.count -= 1
def getCount(self):
return self.count
class 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()
In the above implementation, the simplest union search set is used. The merge process is not optimized. The code optimized for union search is as follows
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 = 0
for i in range(n):
for j in range(m):
if grid[i][j] == '1':
self.fa[i*m + j] = i*m + j
self.count += 1
#The find process is optimized, each node is directly connected to the root node
def find(self,i):
if self.fa[i] == i:
return i
else:
self.fa[i] = self.find(self.fa[i])
return self. fa[i]
#Optimize the Union process, so that the tree hierarchy of the union search is less, and the speed is accelerated
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] = heady
else:
self.fa[heady] = headx
if self.rank[headx] == self.rank[heady] and headx != heady:
self.rank[heady] += 1
self.count -= 1
def getCount(self):
return self.count
–Intermediate Algorithm-Tree and Graph part completed–
–Intermediate Algorithm-Backtracking Algorithm–
2. Alphabet combination of phone number
Topic requirements
Given a string containing only digits 2-9, return all letter combinations it can represent. Answers can be returned in any order.
The mapping of numbers to letters is given as follows (same as for phone keys). Note that 1 does not correspond to any letter.
Example 1:
Input: digits = “23”
Output: [“ad”,”ae”,”af”,”bd”,”be”,”bf”,”cd”,”ce” ,”cf”]
Example 2:
Input: digits = “”
output: []
Example 3:
Input: digits = “2”
Output: [“a”,”b”,”c”]
train of thought
Initialize an empty result character list first, and the size of the list is determined by the phone number. Then add the corresponding letter to the result string according to the phone number. See code and comments for details
class Solution:
def checkNum(self, digit, result):
times = len(result)
# Generate a list of characters to add
#The size of the generated character list is the same as the size of the result list
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]
#Sort the results obtained each time, and each newly added strs list is not sorted
#In this way, we can ensure that the obtained list has no duplicates
result. sort()
return result
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return []
n = len(digits)
# Get the list size of the final result
nums = 1
for i in range(n):
if digits[i] == '7' or digits[i] == '9':
nums *= 4
else:
nums *= 3
result = [''] * nums
#Add new letters to the result list
for i in range(n):
result = self. checkNum(digits[i],result)
return result
Officially given, backtracking method
First use a hash table to store all possible letters corresponding to each number, and then perform a backtracking operation.
During the backtracking process, a string is maintained, representing the existing alphabetic arrangement (if all the digits of the phone number have not been traversed, the existing alphabetical arrangement is incomplete). The string is initially empty. Take one digit of the phone number each time, get all possible letters corresponding to the number from the hash table, and insert one of the letters behind the existing alphabet sequence, and then continue to process the last digit of the phone number , until all the numbers in the phone number are processed, that is, a complete sequence of letters is obtained. Then perform a fallback operation and traverse the remaining alphabetical arrangements.
The backtracking algorithm is used to find all feasible solutions, and if a solution is found to be infeasible, the infeasible solution will be discarded. In this question, since each letter corresponding to each number may enter the letter combination, there is no infeasible solution, and all the solutions can be exhausted directly.
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