【刷题DAY26】39, 40, 131.md

发表于 | 分类于

39. 组合总和

题目链接：https://leetcode.cn/problems/combination-sum/

0x1 看到题目的第一想法

0x2 自己实现过程中遇到哪些困难

  • 剪枝那里不是直接return 是continue

0x3 今日学习的文章链接，或者视频链接

0x4 看完代码随想录之后的想法

  • 组合问题
    • 回溯

0x5 今日收获，记录一下自己的学习时长

  • 45min

40.组合总和II

题目链接：https://leetcode.cn/problems/combination-sum-ii/

0x1 看到题目的第一想法

0x2 自己实现过程中遇到哪些困难

  • 出现重复组合

0x3 今日学习的文章链接，或者视频链接

0x4 看完代码随想录之后的想法

  • candidate中有重复元素，要求结果组合中不能出现重复组合
    • 去重操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        path = []
        candidates.sort()
        def backtrack(candidates, startIdx, _sum, target):
            if(_sum == target):
                res.append(path[:])
                return
            for i in range(startIdx, len(candidates)):
                # 去重
                if(i > startIdx):
                    if(candidates[i] == candidates[i-1]):
                        continue
                        
                # 剪枝
                _sum += candidates[i]
                if(_sum > target):
                    _sum -= candidates[i]
                    continue
                

                path.append(candidates[i])
                backtrack(candidates, i+1, _sum, target)
                _sum -= candidates[i]
                path.pop()

        backtrack(candidates, 0, 0, target)
        return res

0x5 今日收获，记录一下自己的学习时长

  • 1h

131. 分割回文串

题目链接：https://leetcode.cn/problems/palindrome-partitioning/

0x1 看到题目的第一想法

0x2 自己实现过程中遇到哪些困难

  • 剪枝要用countinue，不能是直接return

0x3 今日学习的文章链接，或者视频链接

0x4 看完代码随想录之后的想法

  • python判断回文
    • 例如给定字符串”abcde”, 在已知”bcd”不是回文字串时, 不再需要去双指针操作”abcde”而可以直接判定它一定不是回文字串
    • s[0:n-1]是回文，s[0:n]才有可能是回文
      1
      tmp =?= tmp[::-1]
  • startIdx控制下一个回文子串的起始位置，i来寻找截止位置
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    class Solution:
        def partition(self, s: str) -> List[List[str]]:
            path = []
            res = []
            
            def backtrack(s, startIdx):
                if(startIdx >= len(s)):
                    res.append(path[:])
                for i in range(startIdx, len(s)):
                    tmp = s[startIdx: i+1]
                    print(tmp)
                    # 判断回文
                    # 剪枝
                    if(tmp != tmp[::-1]):
                        continue 
                    path.append(tmp)
                    backtrack(s, i+1)
                    path.pop()
                
            backtrack(s, 0)
            return res

    0x5 今日收获，记录一下自己的学习时长

  • 1.5h

待重点复习

40, 131

总结

  • 回溯
    • 去重
    • 分割回文串