力扣(2024.06.18)
1. 39——组合总和
(图片来源网络,侵删)
给你一个无重复元素的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有不同组合,并以列表形式返回。你可以按任意顺序返回这些组合。candidates 中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同,则两种组合是不同的。 对于给定的输入,保证和为 target 的不同组合数少于 150 个。
标签:数组,回溯
代码:
class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: def backtrack(candidates, target, sum, start, res, path): if sum == target: res.append(path.copy()) return for i in range(start, len(candidates)): if sum + candidates[i] > target: break sum = sum + candidates[i] path.append(candidates[i]) backtrack(candidates, target, sum, i, res, path) sum = sum - candidates[i] path.pop() res = [] path = [] candidates.sort() backtrack(candidates, target, 0, 0, res, path) return res
2. 40——组合总和2
给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次。注意:解集不能包含重复的组合。
标签:数组,回溯
代码:
class Solution: def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: def backtrack(candidates, target, sum, start, res, path): if sum == target: res.append(path.copy()) return for i in range(start, len(candidates)): if i > start and candidates[i] == candidates[i-1]: continue if sum + candidates[i] > target: break sum = sum + candidates[i] path.append(candidates[i]) backtrack(candidates, target, sum, i+1, res, path) sum = sum - candidates[i] path.pop() res = [] path = [] candidates.sort() backtrack(candidates, target, 0, 0, res, path) return res
3. 41——缺失的第一个正数
给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
标签:数组,哈希表
代码:
class Solution: def firstMissingPositive(self, nums: List[int]) -> int: n = len(nums) for i in range(n): if nums[i] = n + 1: nums[i] = n + 1 for num in nums: idx = abs(num) if idx 0: nums[idx - 1] = - nums[idx - 1] for i in range(n): if nums[i] > 0: return i + 1 return n + 1
文章版权声明:除非注明,否则均为主机测评原创文章,转载或复制请以超链接形式并注明出处。