recursion
2019-07-19 本文已影响0人
cookyo
22 Generate Parentheses
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
if n == 0:
return []
self.res = []
self.solution('', n, n)
return self.res
def solution(self, s, left_n, right_n):
if left_n == 0 and right_n == 0:
self.res.append(s)
if left_n > right_n or left_n < 0 or right_n < 0:
return
self.solution(s+'(', left_n - 1, right_n)
self.solution(s+')', left_n, right_n - 1)
39 Combination Sum
'''
Example :
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[2,2,3]
]
'''
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
if not candidates or not target:
return []
res = []
path = []
def dfs(candidates, target, tmp):
if target < 0:
return
elif target == 0:
res.append(tmp)
else:
for i in range(len(candidates)):
if candidates[i] <= target:
dfs(candidates[i:], target-candidates[i], tmp+[candidates[i]])
dfs(candidates, target, [])
return res
40 Combination Sum II
'''
Example :
Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
'''
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
if not candidates or not target:
return []
candidates = sorted(candidates)
res = []
path = []
def dfs(candidates, target, tmp):
if target < 0:
return
elif target == 0:
if tmp not in res:
res.append(tmp)
else:
for i in range(len(candidates)):
if candidates[i] <= target:
dfs(candidates[i+1:], target-candidates[i], tmp+[candidates[i]])
dfs(candidates, target, [])
return res
46 Permutations
# 全排列
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
if len(nums) == 0:
return []
self.res = []
self.used = [False] * len(nums)
self._dfs(nums, 0, [])
return self.res
def _dfs(self, nums, index, tmp):
if index == len(nums):
self.res.append(tmp)
return
for i in range(len(nums)):
if not self.used[i]:
self.used[i] = True
self._dfs(nums, index+1, tmp+[nums[i]])
self.used[i] = False
47 Permutations II
'''
Input: [1,1,2]
Output:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
'''
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
if len(nums) == 0:
return []
self.res = []
self.used = [False] * len(nums)
self._dfs(nums, 0, [])
return self.res
def _dfs(self, nums, index, tmp):
if index == len(nums) and tmp not in self.res:
self.res.append(tmp)
return
for i in range(len(nums)):
if not self.used[i]:
self.used[i] = True
self._dfs(nums, index+1, tmp+[nums[i]])
self.used[i] = False
52 N-Queens II
class Solution:
def totalNQueens(self, n: int) -> int:
if n < 1:
return 0
self.count = 0
self.cols = set()
self.pie = set()
self.na = set()
self._dfs(n, 0)
return self.count
def _dfs(self, n, row):
if row >= n:
self.count += 1
for col in range(n):
if col in self.cols or row+col in self.pie or row-col in self.na:
continue
self.cols.add(col)
self.pie.add(row+col)
self.na.add(row-col)
self._dfs(n, row+1)
self.cols.remove(col)
self.pie.remove(row+col)
self.na.remove(row-col)
55. Jump Game
'''
Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
'''
class Solution:
def canJump(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
#贪心
# n = len(nums)
# reach = 0
# i = 0
# while i <= reach and reach < n-1:
# reach = max(reach, nums[i] + i)
# i += 1
# if reach >= n - 1:
# return True
# else:
# return False
#dp
n = len(nums)
dp = [0] * n
dp[0] = 0
for i in range(1, n):
dp[i] = max(dp[i-1], nums[i-1]) - 1
if dp[i] < 0:
return False
if dp[-1] >= 0:
return True
67 Add Binary
'''
Example 1:
Input: a = "11", b = "1"
Output: "100"
Example 2:
Input: a = "1010", b = "1011"
Output: "10101"
'''
class Solution:
# 递归
def addBinary(self, a: str, b: str) -> str:
if not a or not b:
return a if a else b
if a[-1] == '1' and b[-1] == '1':
return self.addBinary(self.addBinary(a[:-1], b[:-1]), '1') + '0'
elif a[-1] == '0' and b[-1] == '0':
return self.addBinary(a[:-1], b[:-1]) + '0'
else:
return self.addBinary(a[:-1], b[:-1]) + '1'
77 Combinations
'''
Input: n = 4, k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
'''
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
if n < 1:
return []
if k > n:
return []
self.res = []
self.dfs(n, k, 1, [])
return self.res
def dfs(self, n, k, start, tmp): #从start开始选，下次选只能选start后面的数
if len(tmp) == k:
self.res.append(tmp)
return
for i in range(start, n+1):
self.dfs(n, k, i+1, tmp+[i])
78 Subsets
'''
Input: nums = [1,2,3]
Output:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
'''
class Solution(object):
def subsets(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = []
if len(nums) == 0:
return res
res.append([])
for n in nums:
temp = []
for t in res:
m = t + [n]
temp.append(m)
res = res + temp
return res
#递归
class Solution(object):
def subsets(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
if len(nums) == 0:
return []
res = []
temp = []
self.hs(nums, res, temp, 0)
return res
def hs(self, nums, res, temp, i):
if i == len(nums):
res.append(temp)
return
self.hs(nums, res, temp+[nums[i]], i+1)
self.hs(nums, res, temp, i+1)
87 Scramble String
'''
Example 1:
Input: s1 = "great", s2 = "rgeat"
Output: true
Example 2:
Input: s1 = "abcde", s2 = "caebd"
Output: false
'''
class Solution:
def isScramble(self, s1, s2):
"""
:type s1: str
:type s2: str
:rtype: bool
"""
if s1 == s2:
return True
if sorted(s1) != sorted(s2):
return False
length = len(s1)
for i in range(1, length):
if self.isScramble(s1[:i], s2[:i]) and self.isScramble(s1[i:], s2[i:]):
return True
if self.isScramble(s1[:i], s2[length - i:]) and self.isScramble(s1[i:], s2[:length - i]):
return True
return False
95 Unique Binary Search Trees II
'''
Example:
Input: 3
Output:
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
Explanation:
The above output corresponds to the 5 unique BST's shown below:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
'''
class Solution:
def generateTrees(self, n: int) -> List[TreeNode]:
if n == 0:
return []
return self.dfs(1, n)
def dfs(self, left, right):
if left > right:
return [None]
res = []
for i in range(left, right + 1):
leftNode = self.dfs(left, i-1)
rightNode = self.dfs(i+1, right)
for l_n in leftNode:
for r_n in rightNode:
root = TreeNode(i)
root.left = l_n
root.right = r_n
res.append(root)
return res
130 Surrounded Regions
'''
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:
X X X X
X X X X
X X X X
X O X X
'''
class Solution:
# dfs
def solve(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
def dfs(x, y):
if x < 0 or x >= m or y < 0 or y >=n or board[x][y] != 'O': return
board[x][y] = 'D'
dfs(x-1, y)
dfs(x+1, y)
dfs(x, y-1)
dfs(x, y+1)
m = len(board)
if m == 0: return
n = len(board[0])
for i in range(m):
dfs(i, 0)
dfs(i, n-1)
for j in range(n):
dfs(0, j)
dfs(m-1, j)
for i in range(m):
for j in range(n):
if board[i][j] == 'O':
board[i][j] = 'X'
elif board[i][j] == 'D':
board[i][j] = 'O'
200 Number of Islands
# # method1 floodfill
# class Solution:
# def numIslands(self, grid: List[List[str]]) -> int:
# if not grid or not grid[0]:
# return 0
# self.dx = [-1, 1, 0, 0]
# self.dy = [0, 0, -1, 1]
# self.max_x = len(grid)
# self.max_y = len(grid[0])
# self.grid = grid
# self.visited = set()
# res = 0
# for i in range(self.max_x):
# for j in range(self.max_y):
# res += self.floodfill_dfs(i, j)
# return res
# def floodfill_dfs(self, x, y):
# if not self._is_valid(x, y):
# return 0
# self.visited.add((x, y))
# for k in range(4):
# self.floodfill_dfs(x+self.dx[k], y+self.dy[k])
# return 1
# def _is_valid(self, x, y):
# if x < 0 or x >= self.max_x or y < 0 or y >= self.max_y:
# return False
# if (x, y) in self.visited or self.grid[x][y] == '0':
# return False
# return True
# method2 UnionFind
class UnionFind():
def init(self, grid):
m, n = len(grid), len(grid[0])
self.count = 0
self.parent = [-1] * (m*n)
self.rank = [0] * (m*n)
for i in range(i):
for j in range(j):
if grid[i][j] = '1':
self.parent[i*n + j] = i*n + j
self.count += 1
def find(self, i):
if self.parent[i] != i:
self.parent[i] = self.find(parent[i])
return self.parent[i]
def union(self, i, j):
rooti = self.find(i)
rootj = self.find(j)
if rooti != rootj:
if self.rank[rooti] > self.rank[rootj]:
self.parent[rootj] = rooti
elif self.rank[rooti] < self.rank[rootj]:
self.parent[rooti] = rootj
else:
self.parent[rooti] = rootj
self.rank[rootj] += 1
self.count -= 1
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if not grid or not grid[0]:
return 0
uf = UnionFind(grid)
directions = [(0,1),(0,-1),(1,0),(-1,0)]
m, n = len(grid), len(grid[0])
for i in range(m):
for j in range(n):
if grid[i][j] == '0':
continue
for d in directions:
nr, nc = i+d[0], j+d[1]
if nr >= 0 and nc >= 0 and nr < m and nc < n and grid[i][j] == '1':
uf.union(i*n+j, nr*n+nc)
return uf.count
212 Word Search II
# 回溯法会超时
#class Solution:
# def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
# self.res = []
# num = len(words)
# for i in range(num):
# self.find(board, words[i])
# return self.res
# def find(self, board, word):
# self.m = len(board)
# self.n = len(board[0])
# self.visited = set()
# self.dir = [[0, 1], [0, -1], [1, 0], [-1, 0]]
# for i in range(self.m):
# for j in range(self.n):
# if board[i][j] == word[0]:
# tmp = word
# #self.dfs(board, i, j, word[1:], tmp)
# if self.dfs(board, i, j, word[1:], tmp):
# #print('res append word')
# if word not in self.res:
# self.res.append(word)
# def dfs(self, board, i, j, word, tmp):
# if not word:
# #print ('word length == 0')
# #self.res.append(tmp)
# return True
# self.visited.add((i, j))
# for d in self.dir:
# #print (self.visited)
# ni = i + d[0]
# nj = j + d[1]
# if not self.vaild(ni, nj) or board[ni][nj] != word[0]:
# continue
# if self.dfs(board, ni, nj, word[1:], tmp):
# return True
# self.visited.remove((i, j))
# return False
# def vaild(self, ni, nj):
# if ni < 0 or nj < 0 or ni >= self.m or nj >= self.n or (ni, nj) in self.visited:
# return False
# return True
# 需要优化回溯算法以通过更大数据量的测试， 使用前缀树
class TrieNode:
def __init__(self):
self.children = {}
self.Word = ''
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
m = len(board)
if m == 0:
return []
n = len(board[0])
trie = self.buildTrie(words)
self.res = []
for i in range(m):
for j in range(n):
self.DFS(board, i, j, trie)
return self.res
def DFS(self, board, i, j, trie):
if trie.Word:
self.res.append(trie.Word)
trie.Word = ''
if i<0 or i>=len(board) or j<0 or j>=len(board[0]) or not board[i][j] in trie.children:
return
tmp,board[i][j]=board[i][j],'X'
for dx,dy in zip((-1,0,1,0),(0,-1,0,1)):
self.DFS(board,i+dx,j+dy,trie.children[tmp])
board[i][j]=tmp
def buildTrie(self, words):
trie = TrieNode()
for word in words:
cur = trie
for c in word:
if c not in cur.children: cur.children[c] = TrieNode()
cur = cur.children[c]
cur.Word = word
return trie
403 Frog Jump
'''
[0,1,3,5,6,8,12,17]
There are a total of 8 stones.
The first stone at the 0th unit, second stone at the 1st unit,
third stone at the 3rd unit, and so on...
The last stone at the 17th unit.
Return true. The frog can jump to the last stone by jumping
1 unit to the 2nd stone, then 2 units to the 3rd stone, then
2 units to the 4th stone, then 3 units to the 6th stone,
4 units to the 7th stone, and 5 units to the 8th stone.
'''
class Solution:
def canCross(self, nums):
"""
:type stones: List[int]
:rtype: bool
"""
stone={num:1 for num in nums}
index=1
k=1
self.res={}
return self.jump(stone,1,1,nums[-1])
def jump(self,stone,index,k,n):
if index==n:
return True
if index>n or (index not in stone) :
return False
if (index,k) in self.res:
return self.res[(index,k)]
if k==1:
judge=self.jump(stone,index+k,k,n) or self.jump(stone,index+k+1,k+1,n)
self.res[(index,k)]=judge
return judge
if k>1:
judge= self.jump(stone,index+k,k,n) or self.jump(stone,index+k+1,k+1,n) or self.jump(stone,index+k-1,k-1,n)
self.res[(index,k)]=judge
return judge
437 Path Sum III
'''
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
Return 3. The paths that sum to 8 are:
1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11
'''
class Solution:
def pathSum(self, root: TreeNode, sum: int) -> int:
if root is None:
return 0
res = self.findpath(root, sum)
res += self.pathSum(root.left, sum)
res += self.pathSum(root.right, sum)
return res
def findpath(self, node, num):
if node is None:
return 0
res = 0
if node.val == num:
res += 1
res += self.findpath(node.left, num-node.val)
res += self.findpath(node.right, num-node.val)
return res
980 Unique Paths III
'''
On a 2-dimensional grid, there are 4 types of squares:
1 represents the starting square. There is exactly one starting square.
2 represents the ending square. There is exactly one ending square.
0 represents empty squares we can walk over.
-1 represents obstacles that we cannot walk over.
Input: [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output: 2
Explanation: We have the following two paths:
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)
'''
class Solution:
def uniquePathsIII(self, grid: List[List[int]]) -> int:
m = len(grid)
n = len(grid[0])
zeronum = 0
for i in range(m):
for j in range(n):
if grid[i][j] == 0:
zeronum += 1
self.res = 0
self.dir = [[0, 1], [0, -1], [-1, 0], [1, 0]]
self.visited = set()
#print(self.visited)
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
self.dfs(grid, i, j, zeronum, 0)
return self.res
def dfs(self, grid, i, j, zeronum, cnt):
if grid[i][j] == 2 and cnt == zeronum:
self.res += 1
if (grid[i][j] == 0 or grid[i][j] == 1):
self.visited.add((i, j))
print(self.visited)
for d in self.dir:
nx = i + d[0]
ny = j + d[1]
if nx < 0 or ny < 0 or nx >= len(grid) or ny >= len(grid[0]) or grid[nx][ny] == -1 or (nx, ny) in self.visited:
continue
if grid[i][j] == 0:
self.dfs(grid, nx, ny, zeronum, cnt+1)
if grid[i][j] == 1:
self.dfs(grid, nx, ny, zeronum, cnt)
self.visited.remove((i, j))
