# 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】考试得分组合

# 1岛屿数量





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

题目很好理解，dfs来一套即可：

（1）二维的，没考虑特殊情况；

（2）对每个网格dfs，每次dfs往上下左右搜

（3）grid是list，在python里面会是一个全局，第一次搜到记一次搜到了一块岛屿，后面的dfs都是为了扫清上下左右的岛屿；

（4）dfs三要素：

a 如何结束

b 如何递归

c 如何剪枝，这里不需要

```python
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        def dfs(x,y,flagfrist):
            if x<0 or x>=m or y<0 or y>=n:
                return 
            if grid[x][y]=="1":
                if flagfrist==0:
                    res.append(1)
                    flagfrist=1
                grid[x][y]="0"
                dfs(x-1,y,flagfrist)
                dfs(x+1,y,flagfrist)
                dfs(x,y-1,flagfrist)
                dfs(x,y+1,flagfrist)
        m=len(grid)
        n=len(grid[0])
        res=[]
        for i in range(m):
            for j in range(n):
                dfs(i,j,0)
        return len(res)
```

# 2 岛屿中面积最大值

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

写dfs，把重点放在结束条件和如何递归上，多考虑搜索数结构，

能定义为全局变量的就定义为全局变量，**需要往下一级递归的变量才定义为dfs函数的参数**，不然会陷入乱糟糟的传参中！ 

```python
class Solution:
    def maxAreaOfIsland(self, grid: List[List[str]]) -> int:
        def dfs(x,y):
            if x<0 or x>=m or y<0 or y>=n:
                return 
            if grid[x][y]==1:
                area.append(1)
                grid[x][y]=0
                dfs(x-1,y)
                dfs(x+1,y)
                dfs(x,y-1)
                dfs(x,y+1)
        m=len(grid)
        n=len(grid[0])
        res=0
        for i in range(m):
            for j in range(n):
                area=[]
                dfs(i,j)
                res=max(len(area),res)
        return res
```

【算法题目】【DFS】岛屿数量 岛屿中面积最大值

# 1 组合





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

数字都不同，dfs搜索：
```python
from typing import List
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def dfs(start):
            if len(sol) == k:
                res.append(sol[:])
                return
            if start == len(nums):
                return
            for i in range(start, len(nums)):
                sol.append(nums[i])
                dfs(i + 1)
                sol.pop()
        res = []
        sol = []
        nums = list(range(1, n + 1))
        dfs(0)
        return res
```

# 2 组合总和

39. 组合总和

[https://leetcode-cn.com/problems/combination-sum/comments/](https://leetcode-cn.com/problems/combination-sum/comments/)

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

```python
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        ans = []
        temp = []
        def recursion(idx, res):
            if idx >= len(candidates) or res >= target:
                if res == target:
                    ans.append(temp[:])
                return
            temp.append(candidates[idx])
            recursion(idx, res + candidates[idx]) 
            temp.pop()
            recursion(idx + 1, res)
        recursion(0, 0)
        return ans 
```

```python
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def dfs(index,sol_sum,sol): # 序号，加和，选取的列表
            if sol_sum==target:
                res.append(sol[:])
                return
            if index==n or sol_sum>target:
                return
            dfs(index, sol_sum+candidates[index], sol+[candidates[index]]) # 选择上当前元素，继续搜
            dfs(index+1, sol_sum, sol) # 不选上当前元素，继续搜
        candidates.sort()
        n = len(candidates)
        res = []
        dfs(0,0,[])
        return res
```

```python
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def dfs(index,sol_sum,sol): # 序号，加和，选取的列表
            if sol_sum==target:
                res.append(sol[:])
                return
            if index==n or sol_sum>target:
                return
            # 解法1
            # dfs(index, sol_sum+candidates[index], sol+[candidates[index]]) # 选择上当前元素，继续搜
            # dfs(index+1, sol_sum, sol) # 不选上当前元素，继续搜
            # 解法2
            for i in range(index,n):
                sol_sum+=candidates[i]
                sol+=[candidates[i]]
                dfs(i, sol_sum, sol) # 基于此继续选择，传i，下一次就不会选到i左边的数
                sol_sum-=candidates[i]
                sol.pop()
        candidates.sort()
        n = len(candidates)
        res = []
        dfs(0,0,[])
        return res
```

# 3 组合总和2

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

[https://leetcode-cn.com/problems/combination-sum/comments/](https://leetcode-cn.com/problems/combination-sum/comments/)
```python
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        def dfs(pos: int, rest: int):
            nonlocal sequence
            if rest == 0:
                ans.append(sequence[:])
                return
            if pos == len(freq) or rest < freq[pos][0]:
                return
            dfs(pos + 1, rest)
            most = min(rest // freq[pos][0], freq[pos][1])
            for i in range(1, most + 1):
                sequence.append(freq[pos][0])
                dfs(pos + 1, rest - i * freq[pos][0])
            sequence = sequence[:-most]
        freq = sorted(collections.Counter(candidates).items())
        ans = list()
        sequence = list()
        dfs(0, target)
        return ans
```

# 4 子集

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

[https://leetcode-cn.com/problems/subsets/](https://leetcode-cn.com/problems/subsets/)

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

[https://leetcode-cn.com/problems/subsets-ii/](https://leetcode-cn.com/problems/subsets-ii/)

【算法题目】【DFS】组合，组合总和1,2

面试官真是太资深，只有再深入学习才行了：





1 决策树、支持向量机、贝叶斯分类器 的数学知识；

2 mse损失函数反向传播推导，与权重联系；

3 项目事情；

4 coding：C++ 内存泄漏解决；

5 coding：python 一维maxpooling的时间复杂度优化；

【BIGO】 算法岗位面试

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