Recursive / DFS/BFS
In constant update
The n ∧ queen problem studies how to place n ∧ queens in n × N's chessboard, and the Queens can't attack each other.
Give you an integer n, which returns the solution of all different ， queen problems.
Each solution contains a different chess placement scheme for the n queen problem, in which 'Q' and '.' They represent the queen and the vacant seat respectively.
Example 1:
Input: n = 4
Output: [". Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: as shown in the figure above, there are two different solutions to the 4 queen problem.
Example 2:
Input: n = 1
Output: ["Q"]]
Tips:
1 <= n <= 9
Queens cannot attack each other, that is, no two Queens can be in the same horizontal, vertical or diagonal line.
Source: LeetCode
Link: https://leetcode-cn.com/problems/n-queens
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.
Method 1: violent search
This problem can be transformed into the problem of finding the total arrangement of 1~n numbers. Violent search lists all permutations of N numbers 1~n, and then judge whether the permutation meets the rules of Queen n (different rows, different columns and different diagonals)
class Solution:
def generate_permutation(self, index):
if index == self.n:
flag = 1
for i in range(self.n):
for j in range(i + 1, self.n):
if abs(i - j) == abs(self.p_current[i] - self.p_current[j]): # Judge whether the two queens are on the same diagonal
flag = 0
break
if flag:
# print(p_current)
self.permutation_list.append(self.p_current.copy())
self.count += 1
return
for i in range(self.n):
if self.num_exist[i] == 0:
# print(i + 1)
self.p_current[index] = i + 1
self.num_exist[i] = 1
self.generate_permutation(index + 1)
self.num_exist[i] = 0
def solveNQueens(self, n):
"""
:type n: int
:rtype: List[List[str]]
"""
self.n = n
self.num_exist = [0] * n # Records whether a number already exists in the current arrangement
self.permutation_list = [] # All permutations
self.p_current = [0] * n # Current arrangement
self.count = 0 # Number of legal schemes
self.generate_permutation(0) # Generate an arrangement that conforms to the n Queen rule
result = []
k = 0
for each in self.permutation_list:
# print(each)
r = []
for i in range(n):
pp = ['.'] * n
pp[each[i] - 1] = 'Q'
r.append(''.join(pp))
k += 1
result.append(r)
return resultMethod 2: backtracking method
The same is to find the arrangement of n numbers from 1 to n, but compared with method 1, first find all the arrangements and judge whether they comply with the n Queen rule one by one. We can find that when some queens are placed, the remaining queens may not be legal no matter how they are placed. At this time, there is no need to recurse down. Directly return to the previous layer can reduce the amount of calculation. This is the backtracking method.
class Solution:
def generate_permutation(self, index):
if index == self.n:
self.permutation_list.append(self.p_current.copy())
return
for i in range(self.n):
if self.num_exist[i] == 0:
flag = 1
for pre in range(0, index):
if abs(index - pre) == abs(i - self.p_current[pre] + 1):
flag = 0
break
if flag:
self.p_current[index] = i + 1
self.num_exist[i] = 1
self.generate_permutation(index + 1)
self.num_exist[i] = 0
def solveNQueens(self, n):
"""
:type n: int
:rtype: List[List[str]]
"""
self.n = n
self.num_exist = [0] * n # Records whether a number already exists in the current arrangement
self.permutation_list = [] # All permutations
self.p_current = [0] * n # Current arrangement
self.count = 0 # Number of legal schemes
self.generate_permutation(0) # Generate an arrangement that conforms to the n Queen rule
result = []
k = 0
for each in self.permutation_list:
r = []
for i in range(n):
pp = ['.'] * n
pp[each[i] - 1] = 'Q'
r.append(''.join(pp))
k += 1
result.append(r)
return resultThe n ∧ queen problem studies how to place n ∧ queens in n × N's chessboard, and the Queens can't attack each other.
Give you an integer n and return the number of different solutions to the n queen problem.
Example 1:
Input: n = 4
Output: 2
Explanation: as shown in the figure above, there are two different solutions to the 4 queen problem.
Example 2:
Input: n = 1
Output: 1
Tips:
1 <= n <= 9
Queens cannot attack each other, that is, no two Queens can be in the same horizontal, vertical or diagonal line.
Source: LeetCode
Link: https://leetcode-cn.com/problems/n-queens-ii
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.
Idea: for the method of finding the arrangement of Queen n, please look at the previous question. The previous question can get all the arrangements of Queen n. this question is to count the number of arrangements.
class Solution:
def generate_permutation(self, index):
if index == self.n:
# self.permutation_list.append(self.p_current.copy())
self.count += 1
return
for i in range(self.n):
if self.num_exist[i] == 0:
flag = 1
for pre in range(0, index):
if abs(index - pre) == abs(i - self.p_current[pre] + 1):
flag = 0
break
if flag:
self.p_current[index] = i + 1
self.num_exist[i] = 1
self.generate_permutation(index + 1)
self.num_exist[i] = 0
def totalNQueens(self, n):
"""
:type n: int
:rtype: List[List[str]]
"""
self.n = n
self.num_exist = [0] * n # Records whether a number already exists in the current arrangement
self.permutation_list = [] # All permutations
self.p_current = [0] * n # Current arrangement
self.count = 0 # Number of legal schemes
self.generate_permutation(0) # Generate an arrangement that conforms to the n Queen rule
return self.count200. Number of islands
Give you a two-dimensional grid composed of '1' (land) and '0' (water). Please calculate the number of islands in the grid.
Islands are always surrounded by water, and each island can only be formed by adjacent land connections in the horizontal and / or vertical direction.
In addition, you can assume that all four sides of the mesh are surrounded by water.
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
Tips:
m == grid.length
n == grid[i].length
1 <= m, n <= 300
The value of grid[i][j] is' 0 'or' 1 '
Source: LeetCode
Link: https://leetcode-cn.com/problems/number-of-islands
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.
Idea: the grid is regarded as an undirected graph, and the vertical or horizontal adjacent elements are 1, indicating that there is an edge connection between the two nodes. Using the idea of DFS, start with a node with element 1 to DFS its upper, lower, left and right nodes. Each searched 1 will be re marked as 0. Finally, the number of islands is the number of deep first searches.
class Solution:
def dfs(self, grid, i, j):
m = len(grid)
n = len(grid[0])
grid[i][j] = 0
if i + 1 < m and grid[i + 1][j] == '1':
self.dfs(grid, i + 1, j)
if j + 1 < n and grid[i][j + 1] == '1':
self.dfs(grid, i, j + 1)
if i - 1 >= 0 and grid[i - 1][j] == '1':
self.dfs(grid, i - 1, j)
if j - 1 >= 0 and grid[i][j - 1] == '1':
self.dfs(grid, i, j - 1)
def numIslands(self, grid: List[List[str]]) -> int:
m = len(grid)
if m == 0:
return
n = len(grid[0])
num_islands = 0
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
num_islands += 1
self.dfs(grid, i, j)
return num_islands
286. Walls and doors
You are given a {m × There are three possible initialization values in the two-dimensional grid rooms of n +
-1 ￠ indicates a wall or obstacle
0 indicates a door
INF infinity represents an empty room. Then, we use 231 - 1 = 2147483647 to represent INF. You can think that the distance to the door is always less than 2147483647.
You should fill in the distance between the room and the nearest door for each vacant room. If you can't get to the door, fill in "INF".
Example 1:
Input: rooms = [[2147483647, - 1,02147483647], [2147483647, - 1], [2147483647, - 0, - 121474836472147483647]]
Output: [3, - 1,0,1], [2,2,1, - 1], [1, - 1,2, - 1], [0, - 1,3,4]]
Example 2:
Input: rooms = [[-1]]
Output: [[- 1]]
Example 3:
Input: rooms = [[2147483647]]
Output: [[2147483647]]
Example 4:
Input: rooms = [[0]]
Output: [[0]]
Tips:
m == rooms.length
n == rooms[i].length
1 <= m, n <= 250
rooms[i][j] is - 1, 0, or 231 - 1
Source: LeetCode
Link: https://leetcode-cn.com/problems/walls-and-gates
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.
Idea: use the idea of BFS to convert the problem into the shortest distance from each door to each space, then the starting point of BFS is the position of the door, record the current number of layers when traversing each space in breadth first, and update the shortest distance from all doors to the space at the same time. When it comes to BFS, queues must be used. There is no queue data structure in python, but list can also achieve the effect of queues. append is equivalent to joining the queue, and pop(0) is equivalent to popping up the first element of the queue.
class Solution:
def bfs(self, rooms, vis, startx, starty):
m = len(rooms)
n = len(rooms[0])
step = [[0] * n for _ in range(m)]
neighbors = []
neighbors.append((startx, starty))
while len(neighbors) != 0:
(i, j) = neighbors.pop(0) # Pop up team leader element
for x, y in ((i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1)):
if x >= 0 and x < m and y >= 0 and y < n and rooms[x][y] != -1 and rooms[x][y] != 0 and vis[x][y] == 0:
neighbors.append((x, y)) # Add spaces to the end of the queue
step[x][y] = step[i][j] + 1 # Update the number of layers of space-time lattice starting from startx and starty
vis[x][y] = 1 # Set the space to traversed
rooms[x][y] = min(rooms[x][y], step[x][y]) # Update the shortest distance from all doors to the space
def wallsAndGates(self, rooms):
"""
Do not return anything, modify rooms in-place instead.
"""
m = len(rooms)
if m == 0:
return
n = len(rooms[0])
if m == 1 and n == 1:
return
for i in range(m):
for j in range(n):
if rooms[i][j] == 0: # Get the position of each door
vis = [[0] * n for _ in range(m)] # The vis array is used to record whether spaces have been traversed
self.bfs(rooms, vis, i, j) # Take the position of the door as the starting point of the BFS77. Portfolio
Given two integers n and k, return 1 The combination of all possible k numbers in n.
Example:
Input: n = 4, k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
Source: LeetCode
Link: https://leetcode-cn.com/problems/combinations
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.
Idea: backtracking method
class Solution:
def backtracking(self, n, k, startIndex):
if len(self.path) == k:
self.result.append(self.path.copy())
return
for i in range(startIndex, n + 1):
self.path.append(i)
self.backtracking(n, k, i + 1)
self.path.pop(-1)
def combine(self, n: int, k: int) -> List[List[int]]:
self.result = []
self.path = []
self.backtracking(n, k, 1)
return self.result
Pruning
class Solution:
def backtracking(self, n, k, startIndex):
if len(self.path) == k: # If the length k is satisfied, it is added to the result set
self.result.append(self.path.copy())
return
for i in range(startIndex, n - (k - len(self.path)) + 2): # prune
self.path.append(i) # handle
self.backtracking(n, k, i + 1) # recursion
self.path.pop(-1) # to flash back
def combine(self, n: int, k: int) -> List[List[int]]:
self.result = []
self.path = []
self.backtracking(n, k, 1)
return self.result
216. Combined sum III
Find the combination of all k ， numbers whose sum is ， n. Only positive integers of 1 - 9 are allowed in the combination, and there are no duplicate numbers in each combination.
explain:
All numbers are positive integers.
The solution set cannot contain duplicate combinations.
Example 1:
Input: k = 3, n = 7
Output: [[1,2,4]]
Example 2:
Input: k = 3, n = 9
Output: [[1,2,6], [1,3,5], [2,3,4]]
Source: LeetCode
Link: https://leetcode-cn.com/problems/combination-sum-iii
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.
class Solution:
def backtracking(self, sum, targetSum, k, startIndex):
if sum > targetSum: # prune
return
if len(self.path) == k:
if sum == targetSum: # If the conditions are met, add to the result set
self.result.append(self.path.copy())
return
for i in range(startIndex, 10):
sum += i # handle
self.path.append(i) # handle
self.backtracking(sum, targetSum, k, i + 1) # recursion
sum -= i # to flash back
self.path.pop(-1) # to flash back
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
self.path = []
self.result = []
self.backtracking(0, n, k, 1)
return self.result
17. Letter combination of telephone number
Given a string containing only the numbers ， 2-9 ， returns all the letter combinations it can represent. The answers can be returned in any order.
The number to letter mapping is given as follows (the same as the telephone key). 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"]
Tips:
0 <= digits.length <= 4
digits[i] is a number in the range ['2 ','9'].
Source: LeetCode
Link: https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.
class Solution:
def backtracking(self, digits, index):
if len(self.s) == len(digits):
self.result.append(self.s.copy())
return
digit_str = digits[index]
letters = self.letterMap[digit_str]
for i in range(len(letters)):
self.s.append(letters[i])
self.backtracking(digits, index + 1)
self.s.pop(-1)
def letterCombinations(self, digits: str) -> List[str]:
if digits == "":
return []
self.s = []
self.result = []
self.letterMap = {
"2": "abc",
"3": "def",
"4": "ghi",
"5": "jkl",
"6": "mno",
"7": "pqrs",
"8": "tuv",
"9": "wxyz"
}
self.backtracking(digits, 0)
r = []
for s in self.result:
s = "".join(s)
r.append(s)
self.result = r
return self.result
39. Combination sum
Given an array of non repeating elements ， candidates ， and a target number ， target, find all combinations in ， candidates ， that can make the sum of numbers ， target.
The number in candidates ， can be selected repeatedly without limit.
explain:
All numbers (including target) are positive integers.
The solution set cannot contain duplicate combinations.
Example 1:
Input: candidates = [2,3,6,7], target = 7,
The solved set is:
[
[7],
[2,2,3]
]
Example 2:
Input: candidates = [2,3,5], target = 8,
The solved set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
Tips:
1 <= candidates.length <= 30
1 <= candidates[i] <= 200
Each element in the candidate is unique.
1 <= target <= 500
Source: LeetCode
Link: https://leetcode-cn.com/problems/combination-sum
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.
class Solution:
def backtracking(self, candidates, target, index, sum):
if sum > target:
return
if sum == target:
self.result.append(self.path.copy())
return
# i = index
# while i < len(candidates) and sum + candidates[i] <= target:
for i in range(index, len(candidates)):
sum += candidates[i] # handle
self.path.append(candidates[i]) # handle
self.backtracking(candidates, target, i, sum) # recursion
self.path.pop(-1) # to flash back
sum -= candidates[i] # to flash back
# i += 1
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
self.path = []
self.result = []
self.backtracking(candidates, target, 0, 0)
return self.result
40. Combined sum II
Given an array of ， candidates ， and a target number ， target, find all combinations in ， candidates ， that can make the sum of numbers ， target.
Each number in candidates ， can only be used once in each combination.
explain:
All numbers (including the target number) are positive integers.
The solution set cannot contain duplicate combinations.
Example 1:
Input: candidates = [10,1,2,7,6,1,5], target = 8,
The solved set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
Example 2:
Input: candidates = [2,5,2,1,2], target = 5,
The solved set is:
[
[1,2,2],
[5]
]
Source: LeetCode
Link: https://leetcode-cn.com/problems/combination-sum-ii
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.
class Solution:
def backtracking(self, candidates, target, index, sum, used):
if sum > target:
return
if sum == target:
self.result.append(self.path.copy())
return
# i = index
# while i < len(candidates) and sum + candidates[i] <= target:
for i in range(index, len(candidates)):
if i > 0 and candidates[i] == candidates[i - 1] and used[i - 1] == 0:
continue
sum += candidates[i] # handle
self.path.append(candidates[i]) # handle
used[i] = 1
self.backtracking(candidates, target, i + 1, sum, used) # recursion
used[i] = 0
self.path.pop(-1) # to flash back
sum -= candidates[i] # to flash back
# i += 1
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
self.path = []
self.result = []
used = [0] * len(candidates)
candidates.sort()
self.backtracking(candidates, target, 0, 0, used)
return self.result
131. Split palindrome string
Give you a string s. please divide s into some substrings so that each substring is a palindrome string. Returns s all possible segmentation schemes.
A palindrome string is a string that reads the same forward and reverse.
Example 1:
Input: s = "aab"
Output: ["a","a","b"],["aa","b"]]
Example 2:
Input: s = "a"
Output: ["a"]]
Tips:
1 <= s.length <= 16
s consists of lowercase English letters only
Source: LeetCode
Link: https://leetcode-cn.com/problems/palindrome-partitioning
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.
class Solution:
def is_huiwen(self, s):
i = 0
j = len(s) - 1
while i < len(s) and j >= 0:
if s[i] != s[j]:
return False
i += 1
j -= 1
return True
def backtracking(self, s, startIndex):
if startIndex >= len(s):
self.result.append(self.path.copy())
return
for i in range(startIndex, len(s)):
if self.is_huiwen(s[startIndex:i + 1]):
self.path.append(s[startIndex:i + 1])
else:
continue
self.backtracking(s, i + 1)
self.path.pop(-1)
def partition(self, s: str) -> List[List[str]]:
self.path = []
self.result = []
self.backtracking(s, 0)
return self.result
93. Restore IP address
Given a string containing only numbers to represent an IP address, return all valid IP addresses that may be obtained from s. You can return answers in any order.
A valid IP address consists of exactly four integers (each integer is between 0 and 255 and cannot contain a leading 0). Integers are separated by '.'.
For example, "0.1.2.201" and "192.168.1.1" are valid IP addresses, but "0.011.255.245", "192.168.1.312" and "192 168@1.1 "Is an invalid IP address.
Example 1:
Input: s = "25525511135"
Output: [255.255.11.135 "," 255.255.111.35 "]
Example 2:
Input: s = "0000"
Output: ["0.0.0.0"]
Example 3:
Input: s = "1111"
Output: ["1.1.1.1"]
Example 4:
Input: s = "010010"
Output: ["0.10.0.10", "0.100.1.0"]
Example 5:
Input: s = "101023"
Output: ["1.0.10.23", "1.0.102.3", "10.1.0.23", "10.10.2.3", "101.0.2.3"]
Tips:
0 <= s.length <= 3000
s consists of numbers only
Source: LeetCode
Link: https://leetcode-cn.com/problems/restore-ip-addresses
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.
class Solution:
def is_valid(self, s):
if s == '':
return False
if s.startswith("0") and len(s) > 1:
return False
num = 0
for i in range(0, len(s)):
if s[i] > '9' or s[i] < '0':
return False
num = num * 10 + int(s[i])
if num > 255:
return False
return True
def backtracking(self, s, startIndex, pointNum):
if pointNum == 3:
if self.is_valid(s[startIndex:]):
self.path.append(s[startIndex:])
self.result.append(self.path.copy())
self.path.pop(-1)
return
for i in range(startIndex, len(s)):
if self.is_valid(s[startIndex:i + 1]):
self.path.append(s[startIndex:i + 1])
pointNum += 1
else:
continue
self.backtracking(s, i + 1, pointNum)
self.path.pop(-1)
pointNum -= 1
def restoreIpAddresses(self, s: str) -> List[str]:
self.path = []
self.result = []
self.backtracking(s, 0, 0)
r = []
for p in self.result:
pp = ".".join(p)
r.append(pp)
self.result = r
return self.result
78. Subset
Give you an integer array {nums. The elements in the array are different from each other. Returns all possible subsets (power sets) of the array.
The solution set cannot contain duplicate subsets. You can return the solution set in any order.
Example 1:
Input: num = [1,2,3]
Output: [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]
Example 2:
Input: num = [0]
Output: [[], [0]]
Tips:
1 <= nums.length <= 10
-10 <= nums[i] <= 10
All elements in nums are different from each other
Source: LeetCode
Link: https://leetcode-cn.com/problems/subsets
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.
class Solution:
def backtracking(self, nums, startIndex):
self.result.append(self.path.copy())
for i in range(startIndex, len(nums)):
self.path.append(nums[i])
self.backtracking(nums, i + 1)
self.path.pop(-1)
def subsets(self, nums: List[int]) -> List[List[int]]:
self.path = []
self.result = []
self.backtracking(nums, 0)
return self.result90. Subset II
Give you an integer array nums, which may contain duplicate elements. Please return all possible subsets (power sets) of the array.
The solution set cannot contain duplicate subsets. Subsets of the returned solution set can be arranged in any order.
Example 1:
Input: num = [1,2,2]
Output: [[], [1], [1,2], [1,2,2], [2], [2,2]]
Example 2:
Input: num = [0]
Output: [[], [0]]
Tips:
1 <= nums.length <= 10
-10 <= nums[i] <= 10
Source: LeetCode
Link: https://leetcode-cn.com/problems/subsets-ii
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.
class Solution:
def backtracking(self, nums, startIndex, used):
self.result.append(self.path.copy())
for i in range(startIndex, len(nums)):
if i > 0 and nums[i] == nums[i - 1] and used[i - 1] == 0:
continue
self.path.append(nums[i])
used[i] = 1
self.backtracking(nums, i + 1, used)
used[i] = 0
self.path.pop(-1)
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
self.path = []
self.result = []
used = [0] * len(nums)
nums.sort()
self.backtracking(nums, 0, used)
return self.result