# dataStructure

**Repository Path**: daiyizheng_admin/data-structure

## Basic Information

- **Project Name**: dataStructure
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2021-04-27
- **Last Updated**: 2021-10-08

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

https://blog.csdn.net/oneby1314/article/details/107591323

# Summary
## 动态规划（来自于[labuladong](https://labuladong.gitbook.io/algo/mu-lu-ye-3/mu-lu-ye/hui-su-suan-fa-xiang-jie-xiu-ding-ban)总结）
### 什么是动态规划
- 首先，动态规划问题的一般形式就是求最值。
- 求解动态规划的核心问题是穷举。

### 问题
1. 重叠子问题
2. 状态转移方程（最关键）
3. 最优子结构

### 步骤
- 明确「状态」
- 明确「选择」
- 明确 dp函数/数组的定义
- 明确 base case 
按上面的套路走，最后的结果就可以套这个框架：
```text
# 初始化 base case
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 求最值(选择1，选择2...)
```
### 案例
### 斐波那契额数列
```text
斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给你 n ，请计算 F(n) 。

示例 1：

输入：2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1
示例 2：

输入：3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2
示例 3：

输入：4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3

提示：
0 <= n <= 30
```
**暴力求解**
```java
class Solution{
      public int fib(int N){
        if(N==1 || N==2){return 1;}
        return  fib(N-1) + fib(N-2);
      }
}
```
假设n=20, 我们可以画出递归树
![](./images/home-01.png)
PS：但凡遇到需要递归的问题，最好都画出递归树，这对你分析算法的复杂度，寻找算法低效的原因都有巨大帮助。

**递归树的计算流程：**
计算原问题f(20) --> 需要计算子问题f(19)和f(18),然后计算f(19),需要计算子问题f(18)和f(17)，以此类推。。。。

**递归算法的时间复杂度**
- 首先计算子问题个数，即递归树中节点的总数。子问题个数为 O(2^n)。
- f(n - 1) + f(n - 2) 一个加法操作，时间为 O(1)。
- 算法的时间复杂度为二者相乘，即 O(2^n)，指数级别，爆炸。
###优化
**带备忘录的递归解法**
```java
class Solution{
    public fib(int N){
        if(N<1){
            return 0;
        }
    int[] memo = new int[N+1];
    return ; 
    }
    public  int helper( int [] memo, int n) {
        if (n == 1 || n == 2) return 1;
        // 已经计算过
        if (memo[n] != 0) {return memo[n];}
        memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
        return memo[n];
    }
}
```
**递归树**
![](./images/home-2.png)
带「备忘录」的递归算法，把一棵存在巨量冗余的递归树通过「剪枝」，改造成了一幅不存在冗余的递归图，极大减少了子问题（即递归图中节点）的个数。

**dp 数组的迭代解法**
把这个「备忘录」独立出来成为一张表，就叫做 DP table 吧，在这张表上完成「自底向上」的推算。
```java
class Solution {
   public int fib(int N){
    if (N < 1) return 0;
    if (N == 1 || N == 2){ return 1; }
    int[] dp = new int[N+1];
    dp[1] = 1;
    dp[2] = 1;
    for (int i = 0; i<=N;i++){
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[N]; 
   }
 }
```
![](./images/home-03.png)
**最后细节优化**
根据斐波那契数列的状态转移方程，当前状态只和之前的两个状态有关，其实并不需要那么长的一个 DP table 来存储所有的状态，只要想办法存储之前的两个状态就行了。所以，可以进一步优化，把空间复杂度降为 O(1)：
```java
class Solution{
  public int fib(int N){
      if (n < 1) return 0;
      if (n == 2 || n == 1) 
          return 1;
      int prev = 1, curr = 1;
      for (int i = 3; i <= n; i++) {
          int sum = prev + curr;
          prev = curr;
          curr = sum;
      }
      return curr;
   }
}
```

### 凑零钱问题
```text
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
你可以认为每种硬币的数量是无限的。
示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1
```
题目理解：给你 k 种面值的硬币，面值分别为 c1, c2 ... ck，每种硬币的数量无限，再给一个总金额 amount，问你最少需要几枚硬币凑出这个金额，
**暴力递归**
要符合「最优子结构」，子问题间必须互相独立。

**如何列出正确的状态转移方程？**
1、确定 base case，这个很简单，显然目标金额 amount 为 0 时算法返回 0，因为不需要任何硬币就已经凑出目标金额了。
2、确定「状态」，也就是原问题和子问题中会变化的变量。由于硬币数量无限，硬币的面额也是题目给定的，只有目标金额会不断地向 base case 靠近，所以唯一的「状态」就是目标金额 amount。
3、确定「选择」，也就是导致「状态」产生变化的行为。目标金额为什么变化呢，因为你在选择硬币，你每选择一枚硬币，就相当于减少了目标金额。所以说所有硬币的面值，就是你的「选择」。
4、明确 dp 函数/数组的定义。我们这里讲的是自顶向下的解法，所以会有一个递归的 dp 函数，一般来说函数的参数就是状态转移中会变化的量，也就是上面说到的「状态」；函数的返回值就是题目要求我们计算的量。就本题来说，状态只有一个，即「目标金额」，题目要求我们计算凑出目标金额所需的最少硬币数量。所以我们可以这样定义 dp 函数：

dp(n) 的定义：输入一个目标金额 n，返回凑出目标金额 n 的最少硬币数量。

**伪码**
```text
# 伪码框架
def coinChange(coins: List[int], amount: int):

    # 定义：要凑出金额 n，至少要 dp(n) 个硬币
    def dp(n):
        # 做选择，选择需要硬币最少的那个结果
        for coin in coins:
            res = min(res, 1 + dp(n - coin))
        return res

    # 题目要求的最终结果是 dp(amount)
    return dp(amount)
```
加上 base case 即可得到最终的答案。显然目标金额为 0 时，所需硬币数量为 0；当目标金额小于 0 时，无解，返回 -1：

```java
class Solution{
    public int coinChange(int [] coins, int amount){
        return dp(amount, coins);
    }
    public int dp(int n, int [] coins){
      
        if (n == 0){ return 0;}
        if (n < 0){ return -1;}
        // 求最小值，所以初始化为正无穷
        int res = Integer.MAX_VALUE;
        for(int coin:coins){
            int subproblem = dp(n - coin, coins);
            //子问题无解，跳过
            if(subproblem==-1){continue;}
            res = Math.min(res, subproblem+1);
        }
        return res!= Integer.MAX_VALUE?res:-1;
    }
}
```
注意：直接递归，LeetCode会超时。
![](./images/home-04.png)
这个问题其实就解决了，只不过需要消除一下重叠子问题，比如 amount = 11, coins = {1,2,5} 时画出递归树看看：
![](./images/home-05.png)
子问题总数为递归树节点个数，是 O(n^k)，每个子问题中含有一个 for 循环，复杂度为 O(k), 总时间复杂度为 O(k * n^k)
**带备忘录的递归**
```java
/**
自顶向下解法
**/
class Solution{
    private int[] memo;//备忘录
    public int coinChange(int [] coins, int amount){
        memo = new int[amount+1];
        Arrays.fill(memo, -666);
        return dp(amount, coins);
    }
    public int dp(int n, int [] coins){
      
        if (n == 0){ return 0;}
        if (n < 0){ return -1;}
        //查备忘录，防止重复查
        if(memo[n]!=-666){
            return memo[n];
        }
        // 求最小值，所以初始化为正无穷
        int res = Integer.MAX_VALUE;
        for(int coin:coins){
            int subproblem = dp(n - coin, coins);
            //子问题无解，跳过
            if(subproblem==-1){continue;}
            res = Math.min(res, subproblem+1);
        }
        //把计算存入备忘录中
        memo[n] = res!= Integer.MAX_VALUE?res:-1;
        return memo[n];
    } 
}
```
**dp 数组的迭代解法**
可以自底向上使用 dp table 来消除重叠子问题，dp 数组的定义和刚才 dp 函数类似，也是把「状态」，也就是目标金额作为变量。不过 dp 函数体现在函数参数，而 dp 数组体现在数组索引：
dp 数组的定义：当目标金额为 i 时，至少需要 dp[i] 枚硬币凑出。

```java
class  Solution{
    /**
     * 自底向上， 将dp索引作为金额
     **/
    public int coinChange1(int[] coins, int amount){
        int[] dp = new int[amount+1];
        //dp 数组全部初始化为特殊 amount + 1
        Arrays.fill(dp, amount + 1);
        // dp 数组的定义： 凑出总金额 amount , 至少需要 dp[amount] 枚硬币

        // base case
        dp[0] = 0;
        // 外层 for 循环在遍历在求所有状态的所以取值
        for (int i = 0; i<dp.length; i++){
            //内层 for 循环在求所有选择的最小值
            for (int coin:coins){
                //子问题无解，跳过
                if(i-coin<0){
                    continue;
                }
                dp[i] = Math.min(dp[i] , dp[i-coin]+1);
            }
        }
        //看看金额 amount , 能不能凑出来
        return (dp[amount] == amount+1)?-1:dp[amount];
    }
}
```
PS：为啥 dp 数组初始化为 amount + 1 呢，因为凑成 amount 金额的硬币数最多只可能等于 amount（全用 1 元面值的硬币），所以初始化为 amount + 1 就相当于初始化为正无穷，便于后续取最小值。
![](./images/home-06.png)

### 背包问题
1. 0-1背包：每类物品最多只能装一次
2. 多重背包：每类物品都有个数限制，第i类物品最多可以装num[i]次
3. 完全背包：每类物品可以无限次装进包内

**0-1背包问题**
```text
给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装
入背包中物品的总价值最大?
```
**第一步要明确两点，「状态」和「选择」**
状态就是「背包的容量」和「可选择的物品」，选择就是「装进背包」或者「不装进背包」。

**第二步要明确 dp 数组的定义。**
dp[i][j] = x 表示，对于前 i 个物品，当前背包的容量为 j 时的最佳价值。

**第三步，根据「选择」，思考状态转移的逻辑。**
- 如果不把 nums[i] 算入子集，或者说你不把这第 i 个物品装入背包，那么是否能够恰好装满背包，取决于上一个状态 dp[i-1][j]，继承之前的结果。
- 如果把 nums[i] 算入子集，或者说你把这第 i 个物品装入了背包，那么是否能够恰好装满背包，取决于状态 dp[i-1][j-nums[i-1]]。
- 首先，由于 i 是从 1 开始的，而数组索引是从 0 开始的，所以第 i 个物品的重量应该是 nums[i-1]，这一点不要搞混。

```java
class Solution{
    public int ZeroOnePack1(int N, int W, int [] weights, int[]values){
        //初始化动态规划数组
        int[][] dp = new int[N+1][W+1];
        //为了便于理解,将dp[i][0]和dp[0][j]均置为0，从1开始计算
        for (int i =1; i<=N;i++){
            //如果第i件物品的重量大于背包容量j,则不装入背包
           //由于weight和value数组下标都是从0开始,故注意第i个物品的重量为weights[i-1],价值为values[i-1]
            int w = weights[i-1];int v =values[i-1];
            for (int j=1; j<=W;j++){
                if(w>j){
                    dp[i][j] = dp[i-1][j];
                }else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w]+v);
                }
            }
        }
        //则容量为V的背包能够装入物品的最大值为
        return dp[N][W];
    }
}
```

**多重背包问题**

```java
class Solution {
    public int manyPack(int V,int N,int[] weight,int[] value,int[] num){
            //初始化动态规划数组
            int[][] dp = new int[N+1][V+1];
            //为了便于理解,将dp[i][0]和dp[0][j]均置为0，从1开始计算
            for(int i=1;i<N+1;i++){
                for(int j=1;j<V+1;j++){
                    //如果第i件物品的重量大于背包容量j,则不装入背包
                    //由于weight和value数组下标都是从0开始,故注意第i个物品的重量为weight[i-1],价值为value[i-1]
                    if(weight[i-1] > j){
                        dp[i][j] = dp[i-1][j];}
                    else{
                        //考虑物品的件数限制
                        int maxV = Math.min(num[i-1],j/weight[i-1]);
                        for(int k=0;k<maxV+1;k++){
                            dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-k*weight[i-1]]+k*value[i-1]);
                        }
                    }
                }
            }
    		/*//则容量为V的背包能够装入物品的最大值为
    		int maxValue = dp[N][V];
    		int j=V;
    		String numStr="";
    		for(int i=N;i>0;i--){
    			//若果dp[i][j]>dp[i-1][j],这说明第i件物品是放入背包的
    			while(dp[i][j]>dp[i-1][j]){
    				numStr = i+" "+numStr;
    				j=j-weight[i-1];
    			}
    			if(j==0)
    				break;
    		}*/
            return dp[N][V];
        }
}
```

**完全背包问题**
```java
class Solution{
    public  String completePack(int V, int N,int[] weight, int[] value){
        //初始化动态规划数组
        int[][] dp = new int[N+1][V+1];
        //为了便于理解,将dp[i][0]和dp[0][j]均置为0，从1开始计算
        for(int i=1;i<N+1;i++){
            for(int j=1;j<V+1;j++){
                //如果第i件物品的重量大于背包容量j,则不装入背包
                //由于weight和value数组下标都是从0开始,故注意第i个物品的重量为weight[i-1],价值为value[i-1]
                if(weight[i-1] > j){
                    dp[i][j] = dp[i-1][j];}
                else{
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-weight[i-1]]+value[i-1]);}
            }
        }
        //则容量为V的背包能够装入物品的最大值为
        int maxValue = dp[N][V];
        int j=V;
        String numStr="";
        for(int i=N;i>0;i--){
            //若果dp[i][j]>dp[i-1][j],这说明第i件物品是放入背包的
            while(dp[i][j]>dp[i-1][j]){
                numStr = i+" "+numStr;
                j=j-weight[i-1];
            }
            if(j==0){
                break;}
        }
        return numStr;
    }
}
```


### 最长公共子序列
```text
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：
输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。
```
**解题思路**
可以参考这篇blog [https://blog.csdn.net/hrn1216/article/details/51534607](https://blog.csdn.net/hrn1216/article/details/51534607)

**状态转移函数**
![](./images/home-07.png)

```java
class Solutin{
    public int longestCommonSubsequence(String text1, String text2){
        //求长度
        int row = text1.length();
        int col = text2.length();
        int[][] dp = new int[row+1][col+1];
        StringBuilder ans = new StringBuilder();
        for (int i=1;i<=row;i++){
            for(int j=1; j<=col;j++){
                char c1 = text1.charAt(i-1);//数组记录从1开始，字符串下标从0开始，所以需要-1；
                char c2 = text2.charAt(j-1);
                if(c1 == c2){
                    dp[i][j] = dp[i-1][j-1] +1;//当前字符相等时，在上对角的值的基础上+1；
                    ans.append(c1);
                }else {
                    //从左边和右边取最大值
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        System.out.println(ans.toString());
        return dp[row][col];
    }
}
```

## 回溯算法
回溯问题，实际上就是一个决策树的遍历过程。你只需要思考 3 个问题：
- 路径：也就是已经做出的选择。
- 选择列表：也就是你当前可以做的选择。
- 结束条件：也就是到达决策树底层，无法再做选择的条件。

**回溯算法的框架：**
```text
result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择
```
其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」

**全排列问题**
回溯算法直接画出如下这棵回溯树：
![](./images/home-08.png)
可以把「路径」和「选择」列表作为决策树上每个节点的属性
![](./images/home-09.png)
我们定义的 backtrack 函数其实就像一个指针，在这棵树上游走，同时要正确维护每个节点的属性，每当走到树的底层，其「路径」就是一个全排列。
**全排列代码**
```java
class Solution{
    public List<List<Integer>> permute(int[] nums) {
            List<List<Integer>> result=new ArrayList<>();
            List<Integer> l=new ArrayList<>();
            huisu(nums,l,result);
            return result;
        }
    public void huisu(int[] nums,List<Integer> l,List<List<Integer>> result){
        if (l.size()==nums.length){
            //指向新的一片地址空间使其变成不在跟随l改变而改变
            result.add(new ArrayList<Integer>(l));
            return;
        }else {
            for (int i = 0; i <nums.length ; i++) {
                //判断
                if (l.contains(nums[i]))continue;
                l.add(nums[i]);
                huisu(nums,l,result);
                //退回一格
                l.remove(l.size()-1);
            }
        }
    }
}
```

**集合划分**

**排列组合**


## 堆



## 二叉树



## 二分查找



## 广度优先搜索



## 哈希表





## 链表



## 设计




## 深度优先




## 数学



## 数组



## 贪心算法



## 位运算




## 字符串