我有云服务器如何建站,天眼官方网站,南京网站推广营销公司,网站建设php怎么安装文章目录 46. 全排列Solution 78. 子集Solution 17. 电话号码的字母组合Solution 39. 组合总和Solution 22. 括号生成Solution 46. 全排列
给定一个不含重复数字的数组 nums #xff0c;返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例#xff1a; 输入… 文章目录 46. 全排列Solution 78. 子集Solution 17. 电话号码的字母组合Solution 39. 组合总和Solution 22. 括号生成Solution 46. 全排列
给定一个不含重复数字的数组 nums 返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 输入nums [1,2,3] 输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Solution
class Solution:def permute(self, nums: List[int]) - List[List[int]]:def backtrack(path):if len(path) len(nums):res.append(path[:])returnfor num in nums:if num not in path:path.append(num)backtrack(path)path.pop()res []backtrack([])return res在backtrack函数中我们通过一个for循环来遍历nums中的所有元素并尝试将其添加到path的末尾。每当我们递归调用backtrack函数后我们就会移除path的最后一个元素并在下一次for循环迭代中尝试添加下一个元素。
78. 子集
给你一个整数数组 nums 数组中的元素 互不相同 。返回该数组所有可能的子集幂集。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 输入nums [1,2,3] 输出[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Solution
class Solution:def subsets(self, nums: List[int]) - List[List[int]]:def backtrack(start, path):res.append(path[:])for i in range(start, len(nums)):path.append(nums[i])backtrack(i 1, path)path.pop()res []backtrack(0, [])return res我们可以还使用位掩码bitmask的方法。
class Solution:def subsets(self, nums: List[int]) - List[List[int]]:n len(nums)output []for i in range(2**n):# generate bitmask, from 0..00 to 1..11bitmask bin(i)[2:].zfill(n)# append subset corresponding to that bitmaskoutput.append([nums[j] for j in range(n) if bitmask[j] 1])return outputbin(i)是 Python 的内置函数用于将整数 i 转换成二进制字符串。例如bin(3) 将返回 ‘0b11’。‘0b’ 是表示这是一个二进制数。
.zfill(n)是 Python 字符串的一个方法用于在字符串前面填充 0直到字符串的长度为 n。例如‘11’.zfill(3) 将返回 ‘011’。
17. 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。 示例 1 输入digits “23” 输出[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]
Solution
39. 组合总和
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target 找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同则两种组合是不同的。
对于给定的输入保证和为 target 的不同组合数少于 150 个。
示例 1 输入candidates [2,3,6,7], target 7 输出[[2,2,3],[7]]
Solution
class Solution:def combinationSum(self, candidates: List[int], target: int) - List[List[int]]:def backtrack(target, path, start):if target 0:res.append(path[:])returnfor i in range(start, len(candidates)):if candidates[i] target:continuepath.append(candidates[i])backtrack(target - candidates[i], path, i)path.pop()res []backtrack(target, [], 0)return res22. 括号生成
数字 n 代表生成括号的对数请你设计一个函数用于能够生成所有可能的并且 有效的 括号组合。
示例 1 输入n 3 输出[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]
Solution
class Solution:def generateParenthesis(self, n: int) - List[str]:def backtrack(s, left, right):if len(s) n * 2:res.append(.join(s))returnif left n:s.append(()left 1backtrack(s, left, right)s.pop()left - 1if left right:s.append())right 1backtrack(s, left, right)s.pop()right - 1res []backtrack([], 0, 0)return res
s是一个字符列表当你要将最终结果添加到res时你需要用 ‘’.join(s) 把s转换为字符串。
实际上left和right的值都可以自动“回溯”到他们在函数调用开始时的状态。
class Solution:def generateParenthesis(self, n: int) - List[str]:def backtrack(s, left, right):if len(s) n * 2:res.append(s)returnif left n:backtrack(s (, left 1, right)if right left:backtrack(s ), left, right 1)res []backtrack(, 0, 0)return res
