算法刷题





```
22. 括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
```

```python
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def dfs(sol: str, left: int, right: int):
            if left == 0 and right == 0:
                res.append(sol[:])
                return
            if left == right:
                dfs(sol + "(", left - 1, right)  # 使用一个左括号
            elif left < right:
                if left:
                    dfs(sol + "(", left - 1, right)  # 剩余左括号小于右括号，可以选择性来个括号
                dfs(sol + ")", left, right - 1)
        res = []
        dfs("", n, n)
        return res
```

【算法题目】【奇怪的DFS】Python 括号生成

![在这里插入图片描述](/static/img/images/04920.png)





# DFS+剪枝：直接超时：
```python
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        def dfs(start, sol: List):
            # print(sol)
            if start > n:  # 结束条件，
                return
            if len(sol) >= 3:
                if sum(sol) == 0:
                    res.append(sol[:])
                return
            for i in range(start, len(nums)):
                if i > start and nums[i] == nums[i - 1]:  # 为了排除相同结果
                    continue
                sol.append(nums[i])
                dfs(i + 1, sol)
                sol.pop()
        nums.sort()
        n = len(nums)
        res = []
        dfs(0, [])
        return res
```

# 排序 + 双指针

双指针双向移动也能减少计算，拿到结果就能拜拜进行下一次，不像DFS没有太考虑数据的有序性，在DFS中的排序仅仅剪枝用了一下。

```python
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        nums.sort()
        ans = list()
        # 枚举 a
        for first in range(n):
            # 需要和上一次枚举的数不相同
            if first > 0 and nums[first] == nums[first - 1]:
                continue
            # c 对应的指针初始指向数组的最右端
            third = n - 1
            target = -nums[first]
            # 枚举 b
            for second in range(first + 1, n):
                # 需要和上一次枚举的数不相同
                if second > first + 1 and nums[second] == nums[second - 1]:
                    continue
                # 需要保证 b 的指针在 c 的指针的左侧
                while second < third and nums[second] + nums[third] > target:
                    third -= 1
                # 如果指针重合，随着 b 后续的增加
                # 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
                if second == third:  # 指针位置性
                    break
                if nums[second] + nums[third] == target:
                    ans.append([nums[first], nums[second], nums[third]])
        return ans
```

【算法题目】【DFS】Python 三数之和 DFS+剪枝 排序 + 双指针

# 题目




```
5. 最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
```

# 解答1 动态规划 转为最长子字符串（执行超时 200ms）

如果将字符串倒置，原问题变化到求最长子字符串问题：[https://blog.csdn.net/x1131230123/article/details/124176271](https://blog.csdn.net/x1131230123/article/details/124176271)。

下图是输入`"babad"`的dp，需要注意取的是第一次的i行j列。

![在这里插入图片描述](/static/img/images/04921.png)

```python
class Solution:
    def longestPalindrome(self, s: str) -> str:
        # 倒序字符串，求最长公共子串
        s1 = s[::-1]
        m, n = len(s), len(s1)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        maxlen = 0
        maxend = 0
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if s[i - 1] == s1[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = 0
                if maxlen < dp[i][j]: # 保留第一次最大的，字符串多个同长度回文只留第一次的
                    if n - j == i - dp[i][j]: # 判断回文位置，位置必须是同一个位置，比如输入acaabkaaca，回文不是acaa才行
                        maxlen = dp[i][j]
                        maxend = i
        return s[maxend - maxlen:maxend]
```

# 解答2 中心扩散 （1ms量级）

字符串非常长的时候，动态规划 $O(n^2)$ 的时间复杂度，计算量太大，而且停不下来，中心扩散法能够及时止住，时间复杂度虽然也是 $O(n^2)$ ，但期望下来小多了。

```python
class Solution:
    def expandAroundCenter(self, s, left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return left + 1, right - 1
    def longestPalindrome(self, s: str) -> str:
        start, end = 0, 0
        for i in range(len(s)):
            left1, right1 = self.expandAroundCenter(s, i, i)  # 奇数个，从本字符扩散
            left2, right2 = self.expandAroundCenter(s, i, i + 1)  # 偶数个，从本字符和下一个字符扩散
            if right1 - left1 > end - start:  # 保留最大的边界
                start, end = left1, right1
            if right2 - left2 > end - start:  # 保留最大的边界
                start, end = left2, right2
        return s[start: end + 1]
```

# 解答3 动态规划 直接

这个动态规划太难想了，建议别看了==
```python
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n < 2:
            return s
        max_len = 1
        begin = 0
        # dp[i][j] 表示 s[i:j] 是否是回文串
        dp = [[0] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = 1
        # 递推开始
        # 先枚举子串长度
        for L in range(2, n + 1):
            # 枚举左边界，左边界的上限设置可以宽松一些
            for i in range(n):
                # 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                j = L + i - 1
                # 如果右边界越界，就可以退出当前循环
                if j >= n:
                    break
                if s[i] != s[j]:
                    dp[i][j] = 0
                else:
                    if j - i < 3:
                        dp[i][j] = 1
                    else:
                        dp[i][j] = dp[i + 1][j - 1]
                # 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
                if dp[i][j] and j - i + 1 > max_len:
                    max_len = j - i + 1
                    begin = i
        return s[begin:begin + max_len]
```

【算法题目】【动态规划】Python 最长回文子串

# 1 巧妙的思路





看到了一个巧妙的思路：

python3
```python
class Solution:
    def trap(self, height: List[int]) -> int:
        ans = 0
        h1 = 0
        h2 = 0
        for i in range(len(height)):
            h1 = max(h1,height[i])
            h2 = max(h2,height[-i-1])
            ans = ans + h1 + h2 -height[i]
        return  ans - len(height)*h1
```

![在这里插入图片描述](/static/img/images/04927.png)

![在这里插入图片描述](/static/img/images/04928.png)

# 2 如何理解

将循环中这句话`ans = ans + h1 + h2 -height[i]`分开理解，对于所有的遍历过程中的所有`h1` ，当`h1` 小于最大值，就会减去`height[i]` ，这样就得到了左边的雨水+ 右边整个面积。下图的红色表示了最终的数值。

![在这里插入图片描述](/static/img/images/04929.png)

对于所有的遍历过程中的所有`h2` ，当`h2` 小于等于最大值，就会减去`height[i]` ，这样就得到了右边的雨水+ 左边整个面积。下图的橘色表示了最终的数值。

![在这里插入图片描述](/static/img/images/04930.png)

将上面的2个面积加起来，会得到 所有的雨水+ `len(height)*h1` 。


我真是服了。

# 3 动态规划

动态规划没这个思路简单。不写了。

【算法题目】【动态规划】接雨水

员工参加考试，判断题X10（每个2分），单选题X10（每个4分），多选题X5（每个八分）。只能顺序作答，答对得分，答错不得分。答错三道，中止考试。输入考试结果分数，输出答题可能情况个数。





1 需要dfs传递的参数才写成参数，能全局变量就尽量全局。

2 这题传了开始位置、错误次数、分数，三者都是停止条件。

3 搜索也分回溯或者不回溯。

不回溯：

python：
```python
def cal(score_in):
    def dfs(start, error, score):
        if start == n:
            return
        if error >= 3:
            return
        if score == score_in:
            res.append(1)  # 此搜索路径是对的，已经拼凑出
            return
        if score > score_in:
            return
        dfs(start + 1, error, score + nums[start])  # 本题做对
        dfs(start + 1, error + 1, score)  # 本题做错
    nums = [2] * 10 + [4] * 10 + [8] * 5
    n = len(nums)
    res = []
    dfs(0, 0, 0)
    return len(res)
```

回溯：
```python
def cal(score_in):
    def dfs(start, error, score):
        if start == n:
            return
        if error >= 3:
            return
        if score == score_in:
            res.append(1)  # 此搜索路径是对的，已经拼凑出
            return
        if score > score_in:
            return
        for i in range(start, len(nums)):
            score += nums[i]  # 本题对
            dfs(i + 1, error, score)
            score -= nums[i]  # 回溯
            error += 1
    nums = [2] * 10 + [4] * 10 + [8] * 5
    n = len(nums)
    res = []
    dfs(0, 0, 0)
    return len(res)
```

【算法题目】【DFS】考试得分组合

我是一个专注技术分享的博主,尤其爱搞深度学习和单片机电子。你现在看到的是我的个人博客网站。