Skip to content

Commit e06c6ea

Browse files
linwtlinwt
authored
Add files via upload
1 parent aa1508c commit e06c6ea

File tree

62 files changed

+2181
-11
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

62 files changed

+2181
-11
lines changed

‎leetcode/017.电话号码的字母组合.py

Lines changed: 42 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -1,18 +1,52 @@
1-
# 递归
1+
# 回溯
22
class Solution(object):
33
def letterCombinations(self, digits):
4+
if not digits:
5+
return []
46
d = {'2':'abc', '3':'def', '4':'ghi', '5':'jkl', '6':'mno', '7':'pqrs', '8':'tuv', '9':'wxyz'}
5-
67
def combine(s, digits):
7-
# 终止条件，数字为空时把字符串添加到数组中
8+
# 递归终止条件
89
if not digits:
910
res.append(s)
1011
else:
1112
for char in d[digits[0]]:
12-
combine(s+char, digits[1:])
13-
13+
combine(s + char, digits[1:])
1414
res = []
15-
if not digits:
16-
return res
1715
combine('', digits)
18-
return res
16+
return res
17+
18+
19+
# 使用变量
20+
class Solution2(object):
21+
def letterCombinations(self, digits):
22+
if not digits:
23+
return []
24+
d = {'2':'abc', '3':'def', '4':'ghi', '5':'jkl', '6':'mno', '7':'pqrs', '8':'tuv', '9':'wxyz'}
25+
res = ['']
26+
for i in range(len(digits)):
27+
res = [x + y for x in res for y in d[digits[i]]]
28+
return res
29+
30+
# 递归
31+
class Solution3(object):
32+
def letterCombinations(self, digits):
33+
if not digits:
34+
return []
35+
d = {'2':'abc', '3':'def', '4':'ghi', '5':'jkl', '6':'mno', '7':'pqrs', '8':'tuv', '9':'wxyz'}
36+
if len(digits) == 1:
37+
return [x for x in d[digits[0]]]
38+
return [x + y for x in d[digits[0]] for y in self.letterCombinations(digits[1:])]
39+
40+
41+
# 动态规划
42+
class Solution4(object):
43+
def letterCombinations(self, digits):
44+
if not digits:
45+
return []
46+
d = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
47+
n = len(digits)
48+
dp = [[] for _ in range(n)]
49+
dp[0] = [x for x in d[digits[0]]]
50+
for i in range(1, n):
51+
dp[i] = [x + y for x in dp[i - 1] for y in d[digits[i]]]
52+
return dp[-1]

‎leetcode/022.括号生成.py

Lines changed: 5 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,16 +1,18 @@
11
class Solution(object):
22
def generateParenthesis(self, n):
3+
# 全局数组，存放所有结果
34
self.res = []
5+
# 调用递归函数，设置初值
46
self.generate('', 0, 0, n)
57
return self.res
68

9+
# 参数：输出字符串，左括号个数，右括号个数，括号限制个数
710
def generate(self, s, left, right, n):
8-
# 左右括号用完时，添加该括号字符串
11+
# 终止条件。满足当前条件时，则以下两个条件都不满足，故无需返回，自动终止递归
912
if left == n and right == n:
1013
self.res.append(s)
11-
# 左括号未完时，添加左括号，再递归
14+
# 剪枝条件。输出字符串和左右括号个数动态更新，调用递归逐步产生结果，递归完成后回溯，继续搜索下一个结果
1215
if left < n:
1316
self.generate(s+'(', left+1, right, n)
14-
# 右括号少于左括号时，可添加右括号，再递归
1517
if right < left:
1618
self.generate(s+')', left, right+1, n)

‎leetcode/037.解数独.py

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
class Solution(object):
2+
def solveSudoku(self, board):
3+
# 判断当前行列是否可以放数字n
4+
def is_valid(row, col, n):
5+
for i in range(9):
6+
# 判断每一列是否有数字重复
7+
if board[row][i] == n:
8+
return False
9+
# 判断每一行是否有数字重复
10+
if board[i][col] == n:
11+
return False
12+
# 判断每一个小方格是否有数字重复
13+
if board[row // 3 * 3 + i / 3][col // 3 * 3 + i % 3] == n:
14+
return False
15+
return True
16+
17+
def solve(board):
18+
# 遍历整个表格
19+
for row in range(9):
20+
for col in range(9):
21+
# 若非空则跳过
22+
if board[row][col] != '.':
23+
continue
24+
# 在空格处枚举1-9，递归求解
25+
for n in range(1, 10):
26+
# 判断该数字是否合法，不合法则跳过
27+
if not is_valid(row, col, str(n)):
28+
continue
29+
# 若合法，则将该数字填入表格
30+
board[row][col] = str(n)
31+
# 递归判断下一空格，若全部满足条件，返回True
32+
if solve(board):
33+
return True
34+
# 若不满足条件，则回溯，还原初始化设置
35+
board[row][col] = '.'
36+
# 1-9都不合法，返回False
37+
return False
38+
# 整个表格遍历完成，数字填充完毕，返回True
39+
return True
40+
41+
solve(board)
42+
return board

‎leetcode/039.组合总和.py

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
class Solution(object):
2+
def combinationSum(self, candidates, target):
3+
# 参数：输出数组，目标数
4+
def find(output, target):
5+
# 终止条件，将满足条件的结果添加到全局数组，返回空结束当前递归
6+
if target == 0 and sorted(output) not in res:
7+
res.append(sorted(output))
8+
return
9+
# 遍历每个元素处理判断
10+
for candidate in candidates:
11+
new_target = target - candidate
12+
# 剪枝条件，新的目标数若≥0，则可在候选数组继续寻找下一元素
13+
if new_target >= 0:
14+
# 输出数组和目标值动态更新，调用递归逐步产生结果，递归完成后回溯，继续搜索下一个结果
15+
find(output + [candidate], new_target)
16+
17+
res = []
18+
find([], target)
19+
return res

‎leetcode/040.组合总和 II.py

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
class Solution(object):
2+
def combinationSum2(self, candidates, target):
3+
# 参数：候选数组，目标值，输出数组
4+
def find(candidates, target, output):
5+
if target == 0 and sorted(output) not in res:
6+
res.append(sorted(output))
7+
return
8+
for i in range(len(candidates)):
9+
new_target = target - candidates[i]
10+
if new_target >= 0:
11+
# 候选数组每个数字在每个组合中只能使用一次，故递归时要去除已使用过的数字
12+
find(candidates[:i] + candidates[i+1:], new_target, output + [candidates[i]])
13+
14+
res = []
15+
find(candidates, target, [])
16+
return res

‎leetcode/046.全排列.py

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
class Solution(object):
2+
def permute(self, nums):
3+
# 参数：输出数组，数组终止长度，原始数组
4+
def gen(output, n, nums):
5+
# 终止条件，将满足要求的独立结果添加到全局数组，返回空结束当前递归
6+
if len(output) == n:
7+
res.append(output)
8+
return
9+
# 遍历，判断，递归，使得原始数组中每个元素都有机会成为输出数组的下一个元素
10+
for num in nums:
11+
# 剪枝条件
12+
if num not in output:
13+
# 输出数组元素动态更新，调用递归逐步产生结果，递归完成后回溯，继续搜索下一个结果
14+
gen(output + [num], n, nums)
15+
16+
# 全局数组，存放所有结果
17+
res = []
18+
# 调用递归函数，设置初值
19+
gen([], len(nums), nums)
20+
return res
21+
22+
23+
class Solution2(object):
24+
def permute(self, nums):
25+
# 参数：输出数组，剩余数组
26+
def gen(output, nums):
27+
if not nums:
28+
res.append(output)
29+
return
30+
# 遍历，递归，使得剩余数组中每个元素都有机会成为输出数组的下一个元素
31+
for i in range(len(nums)):
32+
# 输出数组和剩余数组元素动态更新
33+
gen(output + [nums[i]], nums[:i] + nums[i+1:])
34+
35+
res = []
36+
gen([], nums)
37+
return res

‎leetcode/047.全排列 II.py

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
class Solution(object):
2+
def permuteUnique(self, nums):
3+
def find(nums, output):
4+
if not nums and output not in res:
5+
res.append(output)
6+
return
7+
for i in range(len(nums)):
8+
find(nums[:i] + nums[i+1:], output + [nums[i]])
9+
10+
res = []
11+
find(nums, [])
12+
return res

‎leetcode/051.N皇后.py

Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
# 回溯法，判断指定行列位置能否放，能放就递归判断下一行的所有列，不能放就回溯
2+
class Solution(object):
3+
def solveNQueens(self, n):
4+
# 初始化棋盘和全局数组
5+
board, res = [['.']*n for _ in range(n)], []
6+
# 调用递归，设置初值
7+
self.dfs(board, n, 0, res)
8+
return res
9+
10+
# 参数：当前棋盘，皇后个数，当前行，全局结果数组
11+
def dfs(self, board, n, row, res):
12+
# 终止条件，最后一行已放完，满足要求，存入结果数组，返回空结束当前递归，回溯到上一步
13+
if row == n:
14+
res.append([''.join(i) for i in board])
15+
return
16+
# 遍历当前行的每一列
17+
for i in range(n):
18+
# 剪枝条件。判断当前位置能否放，不能放则跳过。若当前行每一列都不能放，则结束当前递归，回溯到上一步
19+
if not self.canPlace(row, i, n, board):
20+
continue
21+
# 能放则在当前棋盘做标记
22+
board[row][i] = 'Q'
23+
# 再继续递归判断下一行
24+
self.dfs(board, n, row+1, res)
25+
# 递归完成后回溯，还原初始化设置，继续遍历判断下一列
26+
board[row][i] = '.'
27+
28+
def canPlace(self, row, col, n, board):
29+
for i in range(1, row+1):
30+
# 判断同一列上是否有Q
31+
if board[row-i][col] == 'Q':
32+
return False
33+
# 判断左斜线是否有Q
34+
if col-i >= 0 and board[row-i][col-i] == 'Q':
35+
return False
36+
# 判断右斜线是否有Q
37+
if col+i < n and board[row-i][col+i] == 'Q':
38+
return False
39+
return True
40+
41+
42+
class Solution2(object):
43+
def solveNQueens(self, n):
44+
if n == 0:
45+
return []
46+
res = []
47+
48+
# 参数：
49+
def gen(solution, col, diff, add):
50+
row = len(solution)
51+
if len(col) == n:
52+
# line是每一行皇后放的位置
53+
res.append(['.' * line + 'Q' + '.' * (n - line - 1) for line in solution])
54+
return
55+
# 遍历当前行的每一列
56+
for index in range(n):
57+
# 如果当前位置不与其它皇后冲突
58+
if (index not in col) and (index - row not in diff) and (index + row not in add):
59+
# 则记录当前皇后可到达的位置
60+
col.add(index)
61+
diff.add(index - row)
62+
add.add(index + row)
63+
# 记录当前皇后可放位置，递归判断下一行
64+
gen(solution + [index], col, diff, add)
65+
# 递归完成后回溯，还原初始设置，继续遍历判断下一列
66+
col.remove(index)
67+
diff.remove(index - row)
68+
add.remove(index + row)
69+
70+
# 三个集合存放皇后能达到的列、左斜线、右斜线
71+
gen([], set(), set(), set())
72+
return res

‎leetcode/055.跳跃游戏.py

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
# 若数组i位置加上可跳跃步数大于终点位置，且i位置可到达，则能够到达终点
2+
class Solution(object):
3+
def canJump(self, nums):
4+
max_step = 0
5+
for i in range(len(nums)):
6+
if i > max_step:
7+
return False
8+
max_step = max(nums[i]+i, max_step)
9+
return True

‎leetcode/064.最小路径和.py

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
# 动态规划，dp记录每个位置的最短路径
2+
# 状态转移方程 dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
3+
class Solution(object):
4+
def minPathSum(self, grid):
5+
m, n = len(grid), len(grid[0])
6+
dp = [[0]*n]*m
7+
for i in range(m):
8+
for j in range(n):
9+
if i == 0 and j == 0:
10+
dp[i][j] = grid[i][j]
11+
elif i == 0 and j != 0:
12+
dp[i][j] = dp[i][j-1] + grid[i][j]
13+
elif i != 0 and j == 0:
14+
dp[i][j] = dp[i-1][j] + grid[i][j]
15+
else:
16+
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
17+
return dp[-1][-1]
18+
19+
20+
# 原地修改
21+
class Solution2(object):
22+
def minPathSum(self, grid):
23+
for i in range(len(grid)):
24+
for j in range(len(grid[0])):
25+
if i == 0 and j == 0:
26+
continue
27+
elif i == 0 and j != 0:
28+
grid[i][j] += grid[i][j-1]
29+
elif i != 0 and j == 0:
30+
grid[i][j] += grid[i-1][j]
31+
else:
32+
grid[i][j] += min(grid[i-1][j], grid[i][j-1])
33+
return grid[-1][-1]

‎leetcode/072.编辑距离.py

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
# dp[i][j] 表示 word1[:i] 和 word2[:j] 的编辑距离
2+
class Solution(object):
3+
def minDistance(self, word1, word2):
4+
m, n = len(word1), len(word2)
5+
dp = [[0]*(n+1) for _ in range(m+1)]
6+
# 初始化数组
7+
for i in range(1, n+1):
8+
dp[0][i] = i
9+
for j in range(1, m+1):
10+
dp[j][0] = j
11+
for i in range(1, m+1):
12+
for j in range(1, n+1):
13+
if word1[i-1] == word2[j-1]:
14+
# 两字符相等，则当前状态等于前一状态
15+
dp[i][j] = dp[i-1][j-1]
16+
else:
17+
# 添加：dp[i][j-1]表面上是删除word2最后一个字符，换个角度理解是在word1添加word2的最后一个字符，两者相等抵消
18+
# 删除：dp[i-1][j]相当于删除word1最后一个字符
19+
# 替换：dp[i-1][j-1]相当于替换word1最后一个字符为word2最后一个字符
20+
# 取三种操作中之前状态的最小操作数，每次操作后操作数需加1
21+
dp[i][j] = 1 + min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1])
22+
return dp[-1][-1]
23+
24+
# r o s
25+
# 0 1 2 3
26+
# h 1 1 2 3
27+
# o 2 2 1 2
28+
# r 3 2 2 2
29+
# s 4 3 3 2
30+
# e 5 4 4 3

‎leetcode/077.组合.py

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
class Solution(object):
2+
def combine(self, n, k):
3+
# 参数：数值，输出数组
4+
def dfs(num, output):
5+
# 终止条件，将满足条件的结果添加到全局数组，返回空结束当前递归
6+
if len(output) == k:
7+
res.append(output)
8+
return
9+
# 剪枝条件
10+
elif num > n:
11+
return
12+
# 数值和输出数组元素动态更新，调用递归逐步产生结果，递归完成后回溯，继续搜索下一个结果
13+
dfs(num + 1, output + [num])
14+
dfs(num + 1, output)
15+
16+
# 全局数组，存放所有结果
17+
res = []
18+
# 调用递归，设置初值
19+
dfs(1, [])
20+
return res

0 commit comments

Comments
 (0)