有趣的地方

有趣的地方

算法打卡day23

今日任务:

1)39. 组合总和

2)40.组合总和II

3)131.分割回文串

39. 组合总和

题目链接:39. 组合总和 - 力扣(LeetCode)

给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。

说明:
所有数字(包括 target)都是正整数。
解集不能包含重复的组合。

示例 1:
输入:candidates = [2,3,6,7], target = 7,
所求解集为: [ [7], [2,2,3] ]

示例 2:
输入:candidates = [2,3,5], target = 8,
所求解集为: [ [2,2,2,2], [2,3,3], [3,5] ]

文章讲解:代码随想录 (programmercarl.com)

视频讲解:带你学透回溯算法-组合总和(对应「leetcode」力扣题目:39.组合总和)| 回溯法精讲!哔哩哔哩bilibili

思路:

  1. 定义一个回溯函数 backtrack,它接受两个参数:start 表示从候选数字列表中的哪个位置开始搜索,div 表示目标值与当前路径数字之差。

  2. 在回溯函数中,首先判断终止条件:

    • 如果 div 等于 0,说明当前路径上的数字组合的和等于目标值,将当前组合添加到结果列表中并返回。
    • 如果 div 小于 0,说明当前路径上的数字组合的和已经超过目标值,不再继续搜索,直接返回。
  3. 然后,使用一个循环遍历候选数字列表中的数字,从 start 位置开始:

    • 将当前数字添加到当前路径中。
    • 递归调用 backtrack 函数,传入更新后的 start 位置和更新后的 div 值(减去当前数字)。
    • 递归调用结束后,回溯,将当前数字从当前路径中移除。
  4. 最终,当所有可能的组合都搜索完毕后,返回结果列表。

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        self.candidates = candidates
        self.path = []
        self.result = []
        self.backtrack(0, target)
        return self.result

    def backtrack(self, start, div):
        # 终止条件
        if div == 0:  # 如果目标值为 0,将当前组合添加到结果列表中并返回
            self.result.append(self.path[:])
            return
        elif div < 0:  # 如果目标值为负数,直接返回,不再继续搜索
            return

        for i in range(start, len(self.candidates)):
            self.path.append(self.candidates[i])
            self.backtrack(i, div - self.candidates[i])
            self.path.pop()

改进:

我们可以先对列表排序,对于有序列表,剪枝效果更好

我们还可以直接传递path变量,而不是作为成员变量,在传递的过程可以采用隐式回溯 

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        self.candidates = candidates
        self.result = []
        self.backtrack(0, target, [])
        return self.result

    def backtrack(self, start, div, path):
        # 终止条件:目标值为 0,将当前组合添加到结果列表中并返回
        if div == 0:
            self.result.append(path[:])
            return

        # 递归层
        for i in range(start, len(self.candidates)):
            # 提前剪枝:如果当前候选数大于目标值,直接跳过
            if self.candidates[i] > div:
                break
            # 递归调用
            self.backtrack(i, div - self.candidates[i], path + [self.candidates[i]])

40.组合总和II

题目链接:40. 组合总和 II - 力扣(LeetCode)

给定一个候选人编号的集合 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] ]

示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
输出:
[ [1,2,2],
  [5] ]

提示:
1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30

文章讲解:代码随想录 (programmercarl.com)

视频讲解:回溯算法中的去重,树层去重树枝去重,你弄清楚了没?| LeetCode:40.组合总和II哔哩哔哩bilibili

思路:

已经做了上一题,这一题比较简单了,先排序,遍历列表,如果遇到重复的跳过

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        self.candidates = candidates
        self.result = []

        self.backtrack(0, target, [])
        return self.result

    def backtrack(self, start, div, path):
        # 终止条件
        if div == 0:
            self.result.append(path[:])
            return

        for i in range(start, len(self.candidates)):
            # 提前剪枝:如果当前候选数大于目标值,直接跳过
            if div < self.candidates[i]:
                break

            # 避免重复:如果当前候选数和前一个候选数相同,跳过本次循环
            if i > start and self.candidates[i] == self.candidates[i - 1]:
                continue

            self.backtrack(i + 1, div - self.candidates[i], path + [self.candidates[i]])

131.分割回文串

题目链接:131. 分割回文串 - 力扣(LeetCode)

文章讲解:代码随想录 (programmercarl.com)

视频讲解:带你学透回溯算法-分割回文串(对应力扣题目:131.分割回文串)| 回溯法精讲!哔哩哔哩bilibili

思路:

这一题难一点

  1. 我们可以使用回溯算法来生成所有可能的分割方案。
  2. 在每一步中,我们可以从当前位置开始向右扩展,检查以当前位置开头的所有子串是否为回文串。
  3. 如果是回文串,我们将该子串添加到当前路径中,并递归地处理剩余部分。
  4. 当处理到字符串末尾时,将当前路径添加到结果中。

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        self.s = s
        self.result = []
        self.backtrack(0, len(self.s), [])
        return self.result

    def backtrack(self, start, stop, path):
        # 终止条件:
        if start == len(self.s):
            self.result.append(path[:])
            return
        # 从当前位置开始向右扩展,检查以当前位置开头的所有子串是否为回文串
        for i in range(start,len(self.s)):
            # 判断以i为切分点,判断i之前(包含i)的字符串是否为回文串
            substring = self.s[start:i+1]
            if substring == substring[::-1]:
                path.append(substring)
                self.backtrack(i+1,len(self.s),path)
                path.pop()

感想:这一题后面还要再看看,不是很熟练

发表评论:

Powered By Z-BlogPHP 1.7.3

© 2018-2020 有趣的地方 粤ICP备18140861号-1 网站地图