回溯 组合 排列 生成 算法题目
77. 组合
给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。
示例:
输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
解法1: 回溯 递归
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
if k > n:
return []
if k == n:
return [list(range(1, n+1))]
result = []
def huisu(start, temp):
if len(temp) == k:
result.append(temp.copy())
return
for i in range(start, n+1):
temp.append(i)
huisu(i+1, temp)
temp.pop()
return
huisu(1, [])
return result
39. 组合总和
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
- 所有数字（包括
target）都是正整数。 - 解集不能包含重复的组合。
示例 1：
输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
[7],
[2,2,3]
]
解法1: 回溯 递归
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
result = []
def digui(target, target_list):
for item in candidates:
if target - item == 0:
tem = target_list+[item]
if sorted(tem) not in result:
result.append(sorted(tem))
elif target - item > 0:
digui(target-item, target_list+[item])
else:
pass
digui(target, [])
return result
46. 全排列
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
解法1: 递归
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
def digui(numlist, S=[]):
if len(S) == n:
out.append(S)
return
for i in range(len(numlist)):
digui(numlist[:i] + numlist[i+1:], S+[numlist[i]])
return
out = []
n = len(nums)
digui(nums, [])
return out
全排列 II
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]
解法1: 全排列 + 去重复； 968ms
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
def digui(numlist, S=[]):
if len(S) == n:
if S not in out:
out.append(S)
return
for i in range(len(numlist)):
digui(numlist[:i] + numlist[i+1:], S+[numlist[i]])
return
out = []
n = len(nums)
digui(nums, [])
return out
解法2: 排序 + 递归 + 去重复； 52 ms
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
nums.sort()
n = len(nums)
res = []
def digui(nums, temp):
if len(temp) == n:
res.append(temp)
return
for i in range(len(nums)):
if i+1 < len(nums) and nums[i] == nums[i+1]:
continue
digui(nums[:i]+nums[i+1:], temp + [nums[i]])
digui(nums, [])
return res
31. 下一个排列 **
实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须 原地 修改，只允许使用额外常数空间。
优秀题解
示例 1：
输入：nums = [1,2,3,4,6,5]
输出：[1,2,3,5,4,6]
解法1:
123456
123465
123546
...
654321
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
i = len(nums) - 2
while 0 <= i and nums[i] >= nums[i+1]:
i = i - 1
if i >= 0:
j = len(nums) - 1
while j >= 0 and nums[i] >= nums[j]:
j = j - 1
nums[i], nums[j] = nums[j], nums[i]
left = i + 1
right = len(nums) - 1
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
return nums
267. 回文排列 II
给定一个字符串 s ，返回其通过重新排列组合后所有可能的回文字符串，并去除重复的组合。
如不能形成任何回文排列时，则返回一个空列表。
示例 1：
输入: "aabb"
输出: ["abba", "baab"]
示例 2：
输入: "abc"
输出: []
解法1:
class Solution:
def generatePalindromes(self, s: str) -> List[str]:
s_dict = {}
for item in s:
if item not in s_dict:
s_dict[item] = 1
else:
s_dict[item] += 1
odd_count = 0
odd_str = ""
new_s_dict = {}
for k, v in s_dict.items():
if v % 2 != 0:
odd_count += 1
if odd_count > 1:
return []
else:
new_s_dict[k] = (v-1) // 2
odd_str = k
else:
new_s_dict[k] = v // 2
proce_str = ""
for k, v in new_s_dict.items():
proce_str += k*v
res_temp = []
n = len(proce_str)
def digui(strs, temp=""):
if len(temp) == n:
res_temp.append(temp)
return
for i in range(len(strs)):
if i+1<len(strs) and strs[i]==strs[i+1]:
continue
digui(strs[:i]+strs[i+1:], temp+strs[i])
return
digui(proce_str, "")
new_res = []
for item in res_temp:
new_res.append(item+odd_str+item[::-1])
return new_res
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
