leetcode刷题,使用python
1, 组合总和 —— 0039 回溯 深度搜索
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
示例 1：
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。
from typing import List
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
def dfs(candidates, begin, size, path, res, target):
if target<0:
return
if target == 0:
res.append(path)
return
for index in range(begin, size):
dfs(candidates, index, size, path+[candidates[index]], res, target-candidates[index])
size = len(candidates)
if size == 0:
return []
path = []
res = []
dfs(candidates, 0, size, path, res, target)
return res
S = Solution()
candidates = [2,3,6,7]
target = 7
print(S.combinationSum(candidates, target))
#include<stdio.h>
#include<stdlib.h>
int candidatesSize_tmp;
int ansSize;
int combineSize;
int *ansColumnSize;
void dfs(int *candidates, int target, int **ans, int *combine, int idx)
{
if(idx == candidatesSize_tmp)
{
return;
}
if(target == 0)
{
int *tmp = malloc(sizeof(int) * combineSize);
int i = 0;
for(i=0; i<combineSize; i++)
{
tmp[i] = combine[i];
}
ans[ansSize] = tmp;
ansColumnSize[ansSize++] = combineSize;
return;
}
// 直接跳过
dfs(candidates, target, ans, combine, idx+1);
// 选择当前数
if(target-candidates[idx] >= 0)
{
combine[combineSize++] = candidates[idx];
dfs(candidates, target-candidates[idx], ans, combine, idx);
combineSize--;
}
}
/**
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *returnColumnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
int** combinationSum(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes)
{
candidatesSize_tmp = candidatesSize;
ansSize = combineSize = 0;
int **ans = malloc(sizeof(int*) * 1001);
ansColumnSize = malloc(sizeof(int) * 1001);
int combine[2001];
dfs(candidates, target, ans, combine, 0);
*returnSize = ansSize;
*returnColumnSizes = ansColumnSize;
return ans;
}
int main()
{
int candidates[4] = {2,3,6,7};
int candidatesSize = 4;
int target = 7;
int returnSize = 0;
int *returnColumnSizes;
int **ans = combinationSum(candidates, candidatesSize, target, &returnSize, &returnColumnSizes);
int i,j,k;
for(i=0; i<returnSize; i++)
{
k = returnColumnSizes[i];
for(j=0; j<k; j++)
{
printf("%d ", ans[i][j]);
}
printf("\n");
}
return 0;
}
2, 组合总和 II —— 0040 回溯 深度搜索
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。
示例 1：
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
from typing import List
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
#将数组进行升序排序
candidates.sort()
#结果列表
ans = []
#可能组合
tmp = []
def back_dfs(idx, total):
if total == target:
ans.append(tmp[::])
return
if total > target:
return
for i in range(idx, len(candidates)):
#限制同一层不能选中值相同的元素
#若有相同的元素, 优先选择靠前面的
if i >= idx+1 and candidates[i-1] == candidates[i]:
continue
total += candidates[i]
tmp.append(candidates[i])
#和39题不同, 这里直接进入递归下一层
#从当前索引的下一位开始选取, 避免重复选择同个索引的元素
back_dfs(i+1, total)
#回溯
tmp.pop()
total -= candidates[i]
total = 0
back_dfs(0, total)
return ans
S = Solution()
candidates = [10,1,2,7,6,1,5]
target = 8
print(S.combinationSum2(candidates, target))
3, 组合 —— 77 回溯 深度搜索
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。示例 1：
输入：n = 4, k = 2
输出：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
from typing import List
# 方法一：枚举下一个数选哪个
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
res = []
path = []
def dfs(i: int):
left = k - len(path)
if left == 0:
res.append(path.copy())
return
for j in range(i, left-1, -1):
path.append(j)
dfs(j-1)
path.pop()
dfs(n)
return res
# 方法二：选或不选
class Solution2:
def combine(self, n: int, k: int) -> List[List[int]]:
res = []
path = []
def dfs(i: int):
left = k - len(path)
if left == 0:
res.append(path.copy())
return
# 不选i
if i>left:
dfs(i-1)
# 选择i
path.append(i)
dfs(i-1)
path.pop()
dfs(n)
return res
n = 4
k = 2
S = Solution()
S2 = Solution2()
print(S.combine(n, k))
print(S2.combine(n, k))
4, 子集 —— 78 回溯
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
from typing import List
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
def dfs(idx, n):
if n < 0:
return
if n == 0:
res.append(path.copy())
return
for i in range(idx, len(nums)):
path.append(nums[i])
dfs(i+1, n-1)
path.pop()
path = []
res = []
length = len(nums)
if length == 0:
return []
for i in range(length+1):
dfs(0, i)
return res
S = Solution()
nums = [1,2,3]
print(S.subsets(nums))
5, 单词搜索 —— 79 回溯
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
from typing import List
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
def check(i:int, j:int, k:int) -> bool:
if board[i][j] != word[k]:
return False
if k == len(word) -1:
return True
visited.add((i, j))
result = False
for di, dj in directions:
newi, newj = i+di, j+dj
if 0<=newi<len(board) and 0<=newj<len(board[0]):
if (newi, newj) not in visited:
if check(newi, newj, k+1):
result = True
break
visited.remove((i, j))
return result
h, w = len(board), len(board[0])
visited = set()
for i in range(h):
for j in range(w):
if check(i, j, 0):
return True
return False
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
word = "ABCCED"
S = Solution()
print(S.exist(board, word))
6, 格雷编码 —— 89 归纳
n 位格雷码序列 是一个由 2n 个整数组成的序列，其中：
每个整数都在范围 [0, 2n - 1] 内（含 0 和 2n - 1）
第一个整数是 0
一个整数在序列中出现 不超过一次
每对 相邻 整数的二进制表示 恰好一位不同 ，且
第一个 和 最后一个 整数的二进制表示 恰好一位不同
给你一个整数 n ，返回任一有效的 n 位格雷码序列 。
示例 1：
输入：n = 2
输出：[0,1,3,2]
解释：
[0,1,3,2] 的二进制表示是 [00,01,11,10] 。
- 00 和 01 有一位不同
- 01 和 11 有一位不同
- 11 和 10 有一位不同
- 10 和 00 有一位不同
[0,2,3,1] 也是一个有效的格雷码序列，其二进制表示是 [00,10,11,01] 。 - 00 和 10 有一位不同
- 10 和 11 有一位不同
- 11 和 01 有一位不同
- 01 和 00 有一位不同
看了一个大佬的分析
from typing import List
class Solution:
def grayCode(self, n: int) -> List[int]:
res = []
res.append(0)
for i in range(n):
add = 1<<i #要加的数
length = len(res)
for j in range(length-1, -1, -1):
res.append(res[j]+add)
return res
S = Solution()
n = 2
print(S.grayCode(n))
7, 子集II —— 90 回溯
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
示例 1：
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
from typing import List
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
if not nums:
return []
def dfs(idx:int, path:List[int], res:List[List[int]], nums_sort:List[int]):
res.append(path.copy())
for i in range(idx, len(nums_sort)):
if i>idx and nums_sort[i] == nums_sort[i-1]:
continue
path.append(nums_sort[i])
dfs(i+1, path, res, nums_sort)
path.pop()
res = []
path = []
nums_sort = sorted(nums)
dfs(0, path, res, nums_sort)
return res
nums = [1,2,2]
S = Solution()
print(S.subsetsWithDup(nums))
8, 分割回文串 —— 0131 回溯
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
from typing import List
class Solution:
def partition(self, s: str) -> List[List[str]]:
length = len(s)
#判断s[i:j]是否是回文字符串
def IsPalingdroms(i:int, j:int) -> bool:
start = i
end = j
while start<end:
if(s[start] != s[end]):
return False
start += 1
end -= 1
isPalingdroms[i][j] = 1
return True
def backTracking(startIndex:int):
if startIndex>=length:
res.append(path.copy())
return
for i in range(startIndex, length):
if isPalingdroms[startIndex][i] or IsPalingdroms(startIndex, i):
subStr = s[startIndex:(i+1)]
path.append(subStr)
else:
continue
backTracking(i+1)
path.pop()
res = []
path = []
isPalingdroms = [[0]*length for _ in range(length)]
backTracking(0)
return res
s = "aab"
S = Solution()
print(S.partition(s))
9, Combination Sum II —— 216 回溯
Find all valid combinations of k numbers that sum up to n such that the following conditions are true:
Only numbers 1 through 9 are used.
Each number is used at most once.
Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.
Example 1:
Input: k = 3, n = 7
Output: [[1,2,4]]
Explanation:
1 + 2 + 4 = 7
There are no other valid combinations.
from typing import List
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
def dfs(idx:int, nums:int, target:int):
if nums == k and target == n:
res.append(path.copy())
return
if nums >= k:
return
if target >= n:
return
for i in range(idx, 10):
path.append(i)
dfs(i+1, nums+1, target+i)
path.pop()
res = []
path = []
dfs(1, 0, 0)
return res
S = Solution()
k = 3
n = 7
print(S.combinationSum3(k, n))
k = 3
n = 9
print(S.combinationSum3(k, n))
k = 9
n = 45
print(S.combinationSum3(k, n))
10, Binary Tree Paths —— 257 回溯
Given the root of a binary tree, return all root-to-leaf paths in any order.
A leaf is a node with no children.
Input: root = [1,2,3,null,5]
Output: ["1->2->5","1->3"]
from typing import List
from typing import Optional
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
if not root:
return []
def dfs(RNode: TreeNode, path:str):
if not RNode.left and not RNode.right:
if len(path) == 0:
res.append(path+str(RNode.val))
else:
res.append(path+"->"+str(RNode.val))
return
if RNode.left:
if len(path) == 0:
dfs(RNode.left, path+str(RNode.val))
else:
dfs(RNode.left, path+"->"+str(RNode.val))
if RNode.right:
if len(path) == 0:
dfs(RNode.right, path+str(RNode.val))
else:
dfs(RNode.right, path+"->"+str(RNode.val))
res = []
path = ""
dfs(root, path)
return res
S = Solution()
a = TreeNode(1)
b = TreeNode(2)
c = TreeNode(3)
d = TreeNode(5)
a.left = b
a.right = c
b.right = d
print(S.binaryTreePaths(a))
11, Additive Number —— 306 回溯
An additive number is a string whose digits can form an additive sequence.
A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.
Given a string containing only digits, return true if it is an additive number or false otherwise.
Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.
Example 1:
Input: "112358"
Output: true
Explanation:
The digits can form an additive sequence: 1, 1, 2, 3, 5, 8.
1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8
Example 2:
Input: "199100199"
Output: true
Explanation:
The additive sequence is: 1, 99, 100, 199.
1 + 99 = 100, 99 + 100 = 199
class Solution:
def isAdditiveNumber(self, num: str) -> bool:
if len(num)<3:
return False
def dfs(idx:int, first:int, second:int)->bool:
third = first+second
strThird = str(third)
lenThird = len(strThird)
if idx == len(num):
return True
if len(num) - idx < lenThird:
return False
if num[idx:(idx+lenThird)] == strThird:
return dfs(idx+len(strThird), second, third)
else:
return False
length = len(num)
for i in range(1, length-1):
for j in range(i+1, length):
strFirst = num[0:i]
strSecond = num[i:j]
first = int(strFirst)
second = int(strSecond)
if (len(strFirst)>1 and strFirst[0] == '0') or (len(strSecond)>1 and strSecond[0] == '0'):
continue
# print("{} {}".format(first, second))
if dfs(j, first, second):
return True
return False
S = Solution()
num = "112358"
print(S.isAdditiveNumber(num))
num = "199100199"
print(S.isAdditiveNumber(num))
num = "1023"
print(S.isAdditiveNumber(num))
num = "101"
print(S.isAdditiveNumber(num))
12, Restore IP Addresses —— 93 回溯
A valid IP address consists of exactly four integers separated by single dots. Each integer is between 0 and 255 (inclusive) and cannot have leading zeros.
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" are invalid IP addresses.
Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s. You are not allowed to reorder or remove any digits in s. You may return the valid IP addresses in any order.
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 = "101023"
Output: ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
from typing import List
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
length = len(s)
def judge(strNext:str, numNext:int) -> bool:
if len(strNext) >= 2:
if strNext[0] == "0":
return False
if numNext >= 0 and numNext <= 255:
return True
def dfs(nextIp: int, idx:int, tmp:str):
if nextIp == 4:
if length-idx > 3:
return
strNext = s[idx:length]
numNext = int(strNext)
if judge(strNext, numNext):
res.append(tmp + strNext)
return
if nextIp < 4:
tmplength = idx+4 if length > idx+4 else length
for i in range(idx+1, tmplength):
strNext = s[idx:i]
numNext = int(strNext)
if judge(strNext, numNext):
tmp2 = tmp + strNext + "."
dfs(nextIp + 1, i, tmp2)
res = []
for i in range(1, 4):
strFirst = s[0:i]
numFirst = int(strFirst)
if judge(strFirst, numFirst):
tmp = strFirst + "."
dfs(2, i, tmp)
return res
S = Solution()
s = "25525511135"
s2 = "010010"
s3 = "172162541"
print(S.restoreIpAddresses(s))
print(S.restoreIpAddresses(s2))
print(S.restoreIpAddresses(s3))
13,Unique Binary Search Trees II —— 95 回溯
Given an integer n, return all the structurally unique BST's (binary search trees), which has exactly n nodes of unique values from 1 to n. Return the answer in any order.
from typing import List
from typing import Optional
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
def generateTrees_InterVal(start:int, end:int):
if start>end:
return [None, ]
allTrees = []
# 枚举可行根节点
for i in range(start, end+1):
# 获得所有可行的左子树集合
leftTrees = generateTrees_InterVal(start, i-1)
# 获得所有可行的右子树集合
rigthTrees = generateTrees_InterVal(i+1, end)
# 从左子树集合中选出一棵左子树，从右子树集合中选出一棵右子树，拼接到根节点上
for j in leftTrees:
for k in rigthTrees:
currTree = TreeNode(i)
currTree .left = j
currTree .right = k
allTrees.append(currTree )
return allTrees
return generateTrees_InterVal(1, n) if n else []
14, Binary Watch —— 0401 回溯
A binary watch has 4 LEDs on the top to represent the hours (0-11), and 6 LEDs on the bottom to represent the minutes (0-59). Each LED represents a zero or one, with the least significant bit on the right.
For example, the below binary watch reads "4:51".
Given an integer turnedOn which represents the number of LEDs that are currently on (ignoring the PM), return all possible times the watch could represent. You may return the answer in any order.
The hour must not contain a leading zero.
For example, "01:00" is not valid. It should be "1:00".
The minute must be consist of two digits and may contain a leading zero.
For example, "10:2" is not valid. It should be "10:02".
Example 1:
Input: turnedOn = 1
Output: ["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]
Example 2:
Input: turnedOn = 9
Output: []
from typing import List
class Solution:
def readBinaryWatch(self, turnedOn: int) -> List[str]:
bArray = [1, 2, 4, 8, 16, 32]
def getNum(index, res, turnedOn, LimitturnedOn, type, resArray):
if turnedOn == LimitturnedOn:
resArray.append(res)
return
if index >= type:
return
for i in range(index, type):
curTurnOn = turnedOn + 1
getNum(i + 1, res + bArray[i], curTurnOn, LimitturnedOn, type, resArray)
if turnedOn == 0:
return ["0:00"]
if turnedOn>10:
return []
finalRes = []
hour = min(4, turnedOn)
for i in range(0, hour+1):
j = turnedOn-i
if j > 6:
continue
HourArray = []
MinuteArray = []
if i:
getNum(0, 0, 0, i, 4, HourArray)
if j:
getNum(0, 0, 0, j, 6, MinuteArray)
# print(HourArray)
# print(MinuteArray)
# print(len(HourArray))
# print(len(MinuteArray))
if i == 0:
for k in range(len(MinuteArray)):
if MinuteArray[k] < 10:
strMin = "0" + str(MinuteArray[k])
res = "0:" + strMin
finalRes.append(res)
elif MinuteArray[k] < 60:
res = "0:" + str(MinuteArray[k])
finalRes.append(res)
if j == 0:
for j in range(len(HourArray)):
if HourArray[j] < 12:
res = str(HourArray[j]) + ":00"
finalRes.append(res)
for j in range(len(HourArray)):
for k in range(len(MinuteArray)):
if HourArray[j] < 12:
if MinuteArray[k] < 10:
strMin = "0"+ str(MinuteArray[k])
res = str(HourArray[j])+":"+strMin
finalRes.append(res)
elif MinuteArray[k] < 60:
res = str(HourArray[j]) + ":" + str(MinuteArray[k])
finalRes.append(res)
# print(finalRes)
return finalRes
S = Solution()
print(S.readBinaryWatch(1))
print(S.readBinaryWatch(0))
print(S.readBinaryWatch(2))
print(S.readBinaryWatch(9))
print(S.readBinaryWatch(4))
