算法

时间、空间复杂度

对于一个程序问题我们也许可以用很多种不同的算法去解决，当然对于同一个问题，使用不同的算法，也许最终得到的结果是一样的，但在过程中消耗的资源和时间却会有很大的区别。

那么我们应该如何去衡量不同算法之间的优劣呢？

主要还是从算法所占用的「时间」和「空间」两个维度去考量。

• 时间维度：是指执行当前算法所消耗的时间，我们通常用「时间复杂度」来描述。

• 空间维度：是指执行当前算法需要占用多少内存空间，我们通常用「空间复杂度」来描述。

对于算法消耗的时间和空间我们也可以用两种不同的方法来分析。

1.事后分析法

事后分析法就是将一个算法执行一遍，在执行结束或者说在执行的整个过程中，我们去计算这个程序执行所消耗的时间和内存空间，来分析这个算法的好坏。

但是这种分析方法有着很大的局限性我们一般不使用。

原因：由于不同的机器的性能或者架构的不同以及算法执行时间和数据规模的有密切关系，所以不同的数据规模，不同的机器下算法运行的时间不同，我们无法做到用统一的标准计算运行时间和消耗的空间。

例如：在一台i9的机器上执行较差的算法所消耗的时间可能比在一台i3的机器上执行较好的算法所用的时间更短。

        两个算法在不同数据规模的执行消耗时间的长短可能截然相反。

2.事前分析法

因此，另一种更为通用的方法就出来了：「 大O符号表示法 」，即 T(n) = O(f(n))

说明：大O符号表示法不同于上面的事后分析法，它不去计算具体消耗的时间和空间，而是表示了数据规模与消耗时间和空间的一种正比关系。

for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}

通过「 大O符号表示法 」，这段代码的时间复杂度为：O(n) ，为什么呢?

在 大O符号表示法中，时间复杂度的公式是： T(n) = O( f(n) )，其中f(n) 表示每行代码执行次数之和，而 O 表示正比例关系，这个公式的全称是：算法的渐进时间复杂度。

几个原则

1. 去掉常数项 :2(n^2) =n^2
2. 一段代码取时间复杂度最高的一项

test(n) {
  //时间复杂度n^3
 for(int i = 0; i < n ; i++){
   for(int i = 0; i < n ; i++){
     for(int i = 0; i < n ; i++){
            print(n);
     }
   }
 }
 //时间复杂度n^2
 for(int i = 0; i < n ; i++){
   for(int i = 0; i < n ; i++){
     print(n);
   }
 }
 //时间复杂度n
 for(int i = 0; i < n ; i++){
   print(n);
 }
 int a = 1 + 2;
}

这段代码的时间复杂度为n2+n,因为当n足够大时，n3相比太小，可以忽略不计。

3.常见复杂度

o(1)

i = i + 1;

o(n)

test(n){
  for(int i = 0 ;i < n;i++){
    print(i);
  }
}

o(n^2)

test(n){
  for(int i = 0 ;i < n;i++){
    print(i);
    for(int j = 0 ;j < n;j++){
      print(i);
    }
  }
}

o(log2n)

test(n) {
  int i = 1;
  while (i <= n) {
    i = 2 * i;
  }
}

随着循环次数的增加，i的值变化如下

根据对数函数的公式 2的i次方等于n,i等于log2n

二、空间复杂度

既然时间复杂度不是用来计算程序具体耗时的，那么我也应该明白，空间复杂度也不是用来计算程序实际占用的空间的。空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度，同样反映的是一个趋势，我们用 S(n) 来定义。

空间复杂度比较常用的有：O(1)、O(n)、O(n²)，我们下面来看看：

• 空间复杂度 O(1)

如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1)
举例：

int i = 1;
int j = 2;
++i;
j++;
int m = i + j;

代码中的 i、j、m 所分配的空间都不随着处理数据量变化，因此它的空间复杂度 S(n) = O(1)

• 空间复杂度 O(n)

我们先看一个代码：

int[] m = new int[n]
for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}

这段代码中，第一行new了一个数组出来，这个数据占用的大小为n，这段代码的2-6行，虽然有循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，即 S(n) = O(n)

注意：除此以外，当我们在算法中使用到递归的时候也要注意，n次递归计O(n)的空间复杂度，因为使用一次递归调用就会在方法栈中生成一个栈帧，占用常量大小的内存空间。

4. 常用算法的时间空间复杂度

排序算法

排序方法 平均情况 最好情况 最坏情况 辅助空间 稳定性

冒泡排序 O(n^2) O(n) O(n^2) O(1) 稳定

选择排序 O(n^2) O(n^2) O(n^2) O(1) 不稳定

插入排序 O(n^2) O(n) O(n^2) O(1) 稳定

希尔排序O(n*log(n))~O(n^2) O(n^1.3) O(n^2) O(1) 不稳定

堆排序 O(n_log(n)) O(n_log(n)) O(n*log(n)) O(1) 不稳定

归并排序 O(n_log(n)) O(n_log(n)) O(n*log(n)) O(n) 稳定

快速排序 O(n_log(n)) O(n_log(n)) O(n^2) O(1) 不稳

字符串

647. 回文子串【马拉车算法】

难度中等565

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

输入："abc"
输出：3
解释：三个回文子串: "a", "b", "c"

class Solution {
    //动态规划 时间：O(n^2) 空间：O(n^2)
    public int countSubstrings(String s) {
        int n = s.length();
        int count = 0;
        boolean[][] dp = new boolean[n][n];
        for(int i = 0; i < n; i++){
            for(int j = 0; j <= i; j++){
                 if (s.charAt(i) == s.charAt(j) && (i - j < 2 || dp[i-1][j+1])){
                    dp[i][j] = true;
                    count++;
                }
            }
        }
        return count;
    }
}

Manacher算法详解

代码

class Solution {
    //Manacher算法: 时间复杂度:O(n) 空间复杂度:O(n)
    public int countSubstrings(String s) {
        //1.字符串预处理
        StringBuilder ms = new StringBuilder();
        ms.append("$#");//$头字符
        for (char c : s.toCharArray()) {
            ms.append(c);
            ms.append("#");//#插入字符，让偶数回文串奇数化
        }
        int n = ms.length();
        ms.append("!");//!尾字符，头尾字符可以让我们在更新max时不需要关注边界
        //2.马拉车算法
        int[] p = new int[n];//p[i] 表示以i为中心的回文字符串的半径，注意当前半径应该是 length/2 + 1
        int pi = 0, max = 0, ans = 0; // 当前最靠右的回文字符串的中心pi,和它的半径max
        for(int i = 1; i < n; i++){
            //初始化当前i的p[i]
            p[i] = i < max ? Math.min(p[2*pi-i], max - i) : 1;
            //尝试max向右拓展
            while(ms.charAt(i-p[i]) == ms.charAt(i+p[i])){
                p[i]++;
            }
            if(i+p[i] > max){
                max = i + p[i];
                pi = i;
            }
            //加上当前i位置贡献的回文串个数
            ans += p[i]/2;
        }
        return ans;
    }
}

5740. 所有元音按顺序排布的最长子字符串(美丽字符串)

难度中等2

当一个字符串满足如下条件时，我们称它是 美丽的 ：

• 所有 5 个英文元音字母（'a' ，'e' ，'i' ，'o' ，'u'）都必须 至少 出现一次。
• 这些元音字母的顺序都必须按照 字典序 升序排布（也就是说所有的 'a' 都在 'e' 前面，所有的 'e' 都在 'i' 前面，以此类推）

比方说，字符串 "aeiou" 和 "aaaaaaeiiiioou" 都是 美丽的 ，但是 "uaeio" ，"aeoiu" 和 "aaaeeeooo" 不是美丽的 。

给你一个只包含英文元音字母的字符串 word ，请你返回 word 中 最长美丽子字符串的长度 。如果不存在这样的子字符串，请返回 0 。

子字符串 是字符串中一个连续的字符序列。

示例 1：

输入：word = "aeiaaioaaaaeiiiiouuuooaauuaeiu"
输出：13
解释：最长子字符串是 "aaaaeiiiiouuu" ，长度为 13 。

• 解题思路
  思路：判断字符种类和大小
  这5个元音字符是升序的，所以当字符串满足整体升序的同时字符种类达到5那么这个字符串就是美丽的。
  时间复杂度：O(n) 空间复杂度：O(1)

• 代码

class Solution {
    public int longestBeautifulSubstring(String word) {
        int ans = 0, type = 1, len = 1;
        for(int i = 1; i < word.length(); i++){
            if(word.charAt(i) >= word.charAt(i-1)) len++; //更新字符串长度
            if(word.charAt(i) > word.charAt(i-1)) type++; //更新字符种类
            if(word.charAt(i) < word.charAt(i-1)) { type = 1; len = 1;} //字符串不美丽，从当前字符重新开始
            if(type == 5) ans = ans > len ? ans : len;  //更新最大字符串
        } 
        return ans;
    }
}

数组

581. 最短无序连续子数组【双指针】

难度中等531

给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

请你找出符合题意的 最短 子数组，并输出它的长度。

示例 1：

输入：nums = [2,6,4,8,10,9,15]
输出：5
解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。

class Solution {
    // 最短无序连续子数组的左右边界是最
     //左右两端违背升序排列的两个节点之间的最大最小值
    public int findUnsortedSubarray(int[] nums) {
        int l = 0, r = 0;//左右边界
        int max = Integer.MIN_VALUE,  min = Integer.MAX_VALUE;//节点间的最大最小值
        //找最小值
        boolean flag = false;//节点
        for(int i = 1; i < nums.length; i++){
            if(nums[i] < nums[i-1]){
                flag = true;
            }
            if(flag){
                min = Math.min(min, nums[i]);
            }
        }
        //找最大值
        flag = false;//节点
        for(int i = nums.length - 2; i >= 0; i--){
            if(nums[i] > nums[i+1]){
                flag = true;
            }
            if(flag){
                max = Math.max(max, nums[i]);
            }
        }
        //找左右边界
        for(l = 0; l < nums.length; l++){
            if(nums[l] > min){
                break;
            }
        }
         for(r = nums.length -1; r >= 0; r--){
            if(nums[r] < max){
                break;
            }
        }
        return r - l < 0 ? 0 : r - l + 1;
    }
}

560. 和为K的子数组（前缀和）

难度中等882

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

示例 1 :

输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情。

class Solution {
    //思路：前缀和+map优化  时间:O(n) 空间：O(n)
    //前缀和：我们对数组中每个从数组头到当前位置求和记为当前位置的前缀和，
     //那么以当前位置结尾的和为k的子数组的个数就等于，map.getOrDefault(per_cur - k, 0);  
    public int subarraySum(int[] nums, int k) {
        int count  = 0;
        int sum = 0; //前缀和
        Map<Integer, Integer> map = new HashMap<>();// k存储前缀和， v存储前缀和出现的次数
        map.put(0, 1);//为了记录单独整数位k的情况
        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
            if(map.containsKey(sum - k)){
                count += map.get(sum - k);
            }
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return count;
    }
}

448. 找到所有数组中消失的数字(原地修改)

难度简单717

给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。

找到所有在 [1, n] 范围之间没有出现在数组中的数字。

您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。

示例:

输入:
[4,3,2,7,8,2,3,1]
输出:
[5,6]

智力题：原地修改
思路：题目要求我们满足O(1)的空间复杂度，O(n)的时间复杂度；
为了找出消失的数字，我们不可避免的需要空间去记录已经出现过的数字，这就很难满足O(1)的空间复杂度，所以我们考虑在原数组上进行修改
本题中的数字的特殊之处在于1 ≤ a[i] ≤ n ( n = 数组大小 ) ，所以对于其中任何一个数字a[i]，它都能与该数组中某个位置的索引index对应a[i]-1= index, 所以我们为了记录数字a[i]已经出现过，我们令a[index] += n; ( n = 数组大小 )
因为a[index] + n 大于数组n, （a[index] + n）%n = a[index] 所以我们既避免了对原数组操作造成的数据影响和数据覆盖又记录了已经出现过的数字; 最后整体思路是遍历两遍数组，第一遍记录出现过的数字，第二遍寻找没有被记录过的数字便找到了消失的数字

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        int n = nums.length;
        List<Integer> ans = new ArrayList<>();
        //第一次遍历：记录出现过的数字
        for(int num : nums){
            num = (num - 1) % n;
            nums[num] += n; 
        }
        //第二遍：找出消失的数字，并恢复原数组
        for(int i = 0; i < n; i++){
            if(nums[i] <= n){
                ans.add(i+1);
            }else{
                nums[i] %= n; 
            }
        }
        return ans;
    }
}

栈

739. 每日温度【单调栈】

难度中等737

请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

class Solution {
    //单调栈 时间复杂度：O(n) 空间复杂度：O(n)
      //思路：从前向后将元素入栈，将满足降序的元素直接入栈，遇到违背降序的元素说明他是气温升高的那一天，
      //将栈中所有小于它的元素出栈，并且求得天数差存入结果；最后将它入栈，继续向后
    public int[] dailyTemperatures(int[] T) {
        int[] ans = new int[T.length];
        Stack<Integer> stack = new Stack<>();//单调栈，存的是对应位置的索引值
        for(int i = 0; i < T.length; i++){
            while(!stack.isEmpty() && T[stack.peek()] < T[i]){
                ans[stack.peek()] = i - stack.pop();
            }
            stack.push(i);
        }
        return ans;
    }
}

42. 接雨水【单调栈】

难度困难2309

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

class Solution {
    //单调栈：时间复杂度：O(n) 空间复杂度：O(n)
     //思路：当前位置的水量为：distance*(Math.min(height[l], height[r])-height[cur]); 左右间距乘以两山头中较低的哪一个与当前山谷的差值
    public int trap(int[] height) {
        int ans = 0;
        Stack<Integer> stack = new Stack<>();//存的是数组索引，栈是单调递减的
        for(int r = 0; r < height.length; r++){
            while(!stack.isEmpty() && height[r] > height[stack.peek()]){
                int cur = stack.pop();
                if(stack.isEmpty()) break;
                int l = stack.peek();
                int distance = r - l -1;
                int h = distance*(Math.min(height[l], height[r])-height[cur]);
                ans += h;
             }
            stack.add(r);
        }
        return ans;
    }
}

84. 柱状图中最大的矩形【单调栈】

难度困难1337

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。

图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

示例:

输入: [2,1,5,6,2,3]
输出: 10

单调栈：时间复杂度O(n) 空间复杂度O(n)

思路：先说说暴力解法，对于柱形图中的每个柱子，我们都可以以它的高度为面积的高度，向左右两边拓找出满足以当前柱子为中心能拓展出的最大面积；我们枚举所有柱子，从中找最大值就求出了柱形图中的最大面积。

再考虑改进改解法，暴力解法的时间复杂度局限在于对每个柱子都要重新找一遍左右边界。所以我们考虑维护一个单调递增的栈，在枚举的过程中能够记录任意一个柱形图的左右两边界，这样就不用每次都去找一遍了。 那么单调栈怎么维护呢，如果当前数相对栈顶递增，那么直接入栈；如果不满足，那么我们就对栈做多次出栈，直到剩余的栈元素和当前满足递增那么就对当前数入栈并继续枚举下一个数。

在这个过程中我们什么时候做求面积的操作呢？并且对于一个柱子它的左右边界又是如何被记录了的呢？

答：我们在出栈操作的同时做求面积操作，注意；出栈操作中被出栈的那个元素就是我们当前面积的中心柱子，左边界就是在栈中的一个元素,右边界就是当前等待被入栈的那个元素；具体原因不做赘述，画图可以很直观的看到上面结论成立。

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int maxArea = 0;
        Stack<Integer> stack = new Stack<>();
        int[] hs = new int[n + 2];//对原数组做个处理，两边各加一个0，用于处理单调递增数组，和数组中最小元素左右边界问题
        for (int i = 1; i < n + 1; i++){
            hs[i] = heights[i - 1];
        }
        for (int i = 0; i < n + 2; i++) {
            while (!stack.isEmpty() && hs[stack.peek()] > hs[i]) {
                int cur = stack.pop();
                maxArea = Math.max(maxArea, (i - stack.peek() - 1) * hs[cur]);
            }
            stack.push(i);
        }
        return maxArea;
    }
}

树

543. 二叉树的直径【后序遍历】

难度简单688

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

示例 :
给定二叉树

          1
         / \
        2   3
       / \     
      4   5

返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

class Solution {
    //二叉树的后序遍历
    private int ans = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return ans-1;
    }
    public int dfs(TreeNode root){
        if(root == null) return 0;
        int l = dfs(root.left);
        int r = dfs(root.right);
        ans = Math.max((l + r + 1), ans);
        return Math.max(l, r)+1;
    }
}

538. 把二叉搜索树转换为累加树【反向中序遍历】

难度中等515

给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：

• 节点的左子树仅包含键 小于 节点键的节点。
• 节点的右子树仅包含键 大于 节点键的节点。
• 左右子树也必须是二叉搜索树。

注意：本题和 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同

示例 1：

输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

class Solution {
    //二叉树的反向中序遍历
    private int sum = 0;
    public TreeNode convertBST(TreeNode root) {
     if(root != null){
        convertBST(root.right);
        root.val += sum;
        sum = root.val;
        convertBST(root.left); 
     }
        return root;
    }
}

617. 合并二叉树【DFS】

难度简单680

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

示例 1:

输入: 
    Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
输出: 
合并后的树:
         3
        / \
       4   5
      / \   \ 
     5   4   7

注意: 合并必须从两个树的根节点开始。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    //二叉树的D遍历
      //不破坏原二叉树的前提下合并
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1 == null && root2 == null) return null;
        int v1 = 0, v2 = 0;
        TreeNode l1 = null, l2 = null, r1 = null, r2 = null;
        if(root1 != null) {
            v1 = root1.val;
            l1 = root1.left;
            r1 = root1.right;
         }
        if(root2 != null){
            v2 = root2.val;
            l2 = root2.left;
            r2 = root2.right;
        }
        TreeNode root = new TreeNode(v1 + v2);
        root.left = mergeTrees(l1, l2);
        root.right = mergeTrees(r1, r2);
        return root;
    }
}

112. 路径总和【DFS】

难度简单571

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。

叶子节点 是指没有子节点的节点。

示例 1：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true

class Solution {
    //回溯法： 深度优先遍历
    public boolean hasPathSum(TreeNode root, int targetSum) {
        return dfs(root, targetSum, 0);
    }
    public boolean dfs(TreeNode root, int targetSum, int sum){
        if(root == null) return false;
        sum = sum + root.val;
        if(root.left == null && root.right == null ) {
            return sum == targetSum ? true : false;
        }
        if(dfs(root.left, targetSum,sum)) return true;
        if(dfs(root.right, targetSum,sum)) return true;
        return false;
    }
}

113. 路径总和 II【DFS】

难度中等472

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

示例 1：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]

class Solution {
    //递归
    private List<List<Integer>> res = new LinkedList<>();
    private LinkedList<Integer> temp =new LinkedList<>();
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
       recur(root, sum);
       return res; 
    }
    private void recur(TreeNode root, int tar){
        if(root == null )  return ;
        temp.add(root.val);
        tar = tar - root.val;
        if(tar == 0 && root.left == null && root.right == null)  res.add(new LinkedList(temp));
        recur(root.left, tar);
        recur(root.right, tar);
        temp.removeLast();
    }
}

437. 路径总和 III【前缀和】

难度中等833

给定一个二叉树，它的每个结点都存放着一个整数值。

找出路径和等于给定数值的路径总数。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。

示例：

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1
返回 3。和等于 8 的路径有:
1.  5 -> 3
2.  5 -> 2 -> 1
3.  -3 -> 11

class Solution {
    //递归+前缀和：时间复杂度：O(n), 空间复杂度：O(n)
    //定义解释： 前缀和：指的是从根节点出发到达当前节点的路径中的所有节点的和，我们将前缀和存储在map中，key表示前缀和的值，value记录它值的个数
    //整体思路： 从根节点到达当前节点的这条路径中的满足路径和的子路径的个数为：map.get(curSum - target) 
    private int target; //目标值
    private Map<Integer, Integer> perfixSum;//记录前缀和
    public int pathSum(TreeNode root, int targetSum) {
        target = targetSum;
        perfixSum = new HashMap<>();
        //某个节点的前缀和恰好为target时应该计数为1
        perfixSum.put(0, 1);
        return recur(root, 0);
    }
    private int recur(TreeNode node, int curSum){
        if(node == null) return 0;
        //当前节点的前缀和
        curSum += node.val;
        //先计算满足当前节点的路径个数
        int cur = perfixSum.getOrDefault(curSum - target, 0);
        //再记录当前节点的前缀和
        perfixSum.put(curSum, perfixSum.getOrDefault(curSum, 0) + 1);
        int left = recur(node.left, curSum);
        int right = recur(node.right, curSum);
        //当前节点计算完毕，恢复状态
        perfixSum.put(curSum, perfixSum.get(curSum) - 1);
        return cur + left + right;
    }
}

动态规划

剑指 Offer 10- II. 青蛙跳台阶问题

难度简单148

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

输入：n = 2
输出：2

示例 2：

输入：n = 7
输出：21

示例 3：

输入：n = 0
输出：1

思路
如果前一次跳的是1级台阶，那么前n-1级台阶，跳法是f(n-1)
如果前一次跳的是2级台阶，那么前n-2级台阶，跳法是f(n-2)
可以得出总跳法为: f(n) = f(n-1) + f(n-2)
由题意可得：没有台阶的时候f(0) = 1，只有一级台阶的时候 f(1) = 1
可以发现最终得出的是一个斐波那契数列：

        | 1, (n=0) 
f(n) =  | 1, (n=1) 
        | f(n-1)+f(n-2)  (n>1,n为整数)

//时间复杂度：O(n) 空间复杂度：O(n)
class Solution {
    public int numWays(int n) {
        if(n == 0) return 1;
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i < n + 1; i++){
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
        }
        return dp[n];
    }
}
//空间优化 时间复杂度：O(1) 空间复杂度：O(n)
class Solution {
    public int numWays(int n) {
        int a = 1, b = 1, sum;
        for(int i = 0; i < n; i++){
            sum = (a + b) % 1000000007;
            a = b;
            b = sum;
        }
        return a;
    }
}

322. 零钱兑换

难度中等

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

示例 2：

输入：coins = [2], amount = 3
输出：-1

示例 3：

输入：coins = [1], amount = 0
输出：0

示例 4：

输入：coins = [1], amount = 1
输出：1

示例 5：

输入：coins = [1], amount = 2
输出：2

class Solution {
   //动态规划
   //状态：dp[i]表示凑成i所需的最少硬币个数
   //状态转移方程：dp[i] = min(dp[i], dp[i - coins[j]] + 1); 
   public int coinChange(int[] coins, int amount) {
       int[] dp = new  int[amount + 1];
       for(int i = 1; i <= amount; i++){
           dp[i] = amount + 1;//赋一个较大的初值
           for(int j = 0; j < coins.length;  j++){
               if(coins[j] <= i){
                   dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
               }
           }
       }
       return  dp[amount] > amount  ? -1 : dp[amount];
   }
}

279. 完全平方数

难度中等

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4

示例 2：

输入：n = 13
输出：2
解释：13 = 4 + 9

class Solution {
    //动态规划：该问题与青蛙跳台阶问题，找零问题 属于同一种类型
    //状态：dp[i]表示获得数字i所需的最少完全平方数的数目
    //状态转移方程：dp[i] = min(dp[i], dp[i - j * j] + 1); 其中j属于从1到小于i的最大平方根
    public int numSquares(int n) {
        int[] dp = new int[n+1];
        for(int i = 1; i <= n; i++){
            dp[i] = i;//当前i的最坏结果是全由1组成，即它本身
            for(int  j = 1; i - j*j>= 0; j++){
                dp[i] = Math.min(dp[i], dp[i - j*j] + 1);
            }
        }
        return dp[n];
    }
}

300. 最长递增子序列

难度中等1533

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

动态规划解法：

class Solution {
    //动态规划：时间O(n*n) 空间O(n)
    //状态：dp[i] 表示以nums[i]结尾的最长递增子序列的长度(包括nums[i])
    //状态转移方程：dp[i] = Math.max(dp[j]+1, 1); [其中j属于（0，i-1）,
                                               //还有一个先决条件是nums[i] > nums[j]] 
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int maxLength = 0;
        for(int i = 0; i < nums.length; i++){
            //初始值，最坏为1
            dp[i] = 1;
            //状态转移：从0~i-1的dp[j]比较
            for(int j = 0; j < i; j++){
                if(nums[j] < nums[i]){
                    dp[i] = Math.max(dp[j]+1, dp[i]);
                }
            }
            //更新最大值
            maxLength = Math.max(maxLength, dp[i]);
        }
        return maxLength;
    }
}

312. 戳气球

难度困难699

有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。

现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。

求所能获得硬币的最大数量。

示例 1：

输入：nums = [3,1,5,8]
输出：167
解释：
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins =  3*1*5    +   3*5*8   +  1*3*8  + 1*8*1 = 167

class Solution {
    //动态规划：时间O(n^3) 空间O(n^2)
    //状态：dp[i][j]表示戳破(i,j)这个开区间里面的所有气球所能获得的最大硬币数
    //状态转移方程:dp[i][j] = max( dp[i][k] + val[i]*val[k]*val[j] + dp[k][j] ) 
      //{其中k是（i,j）区间内部的任意数，我们从中选取使dp[i][j]最大的k,val是气球值}
    //整体思路：我们要求出当前区间的值dp[i][j] 之前先要获取dp[i][k]和dp[k][j],所以我们先需要求出(i,j)区间内所有dp[x][y]的值
      //{其中i <= x < y <= j}所以我们先从最小区间长度3开始,逐渐扩大区间；这样我们便能利用到前面已经求出的值来算当前值
    public int maxCoins(int[] nums) {
        int n = nums.length;
        int[] val = new int[n+2];//为了方便处理数组的两个边界，我们将数组扩大2
        int[][] dp = new int[n+2][n+2];//dp数组记录状态值dp[i][j]
        val[0] = val[n + 1] = 1; //边界值为1
        for(int i = 1; i < n + 1; i++){
            val[i] = nums[i-1];
        }
        //i,j分别表示区间左右边界，j的初始值为2是因为我们从最小区间(0,2)开始计算，此时dp[0][2]=dp[0][1]+x+dp[1][2]=0+x+0
        for(int j = 2; j < n + 2; j++){
            for(int i = j - 2; i >= 0; i--){
                for(int k = j - 1; k > i; k--){
                    int sum = dp[i][k] + val[i]*val[k]*val[j] + dp[k][j];
                    dp[i][j] = Math.max(dp[i][j], sum);
                }
            }
        }
        return dp[0][n+1];
    }
}

10. 正则表达式匹配

难度困难2074

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

• '.' 匹配任意单个字符
• '*' 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

示例 1：

输入：s = "aa" p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。

class Solution {
    //动态规划：时间：O(n*m) 空间：O(n*m)， 以下思路画状态数组比较直观
    //状态：boolean dp[i][j] 表示 s 的前 i 个是否能被 p 的前 j 个匹配; 
        //注意此处的描述，i,j 是个数不是索引值 即第i对应的字符是 s.charAt(i-1)
    //状态转移方程：             dp[i-1][j-1]   s[i] == p[j] || p[j] ='.'
                                               //结尾字符相等，那么当前结果由子问题dp[i-1][j-1]决定
    //             dp[i][j] =   true           p[j] == '*' && dp[i][j-2] == true; 
                                               //'*'直接将前面一个字符消除的情况
    //                          dp[i-1][j]    p[j] == '*' && (s[i] == p[j-1] || p[j-1] == '.')                                               //'*'前面的字符能和s[i]相等的情况
    //                          false         其他情况
    public boolean isMatch(String s, String p) {
        if(s == null || p == null) return false;
        int m = s.length(), n = p.length();
        boolean[][] dp = new boolean[m+1][n+1];
        //初始化dp
        dp[0][0] = true; //两个空字符串可以匹配
        for(int j = 2; j <= n; j+=2){//当s为空时
           if(p.charAt(j-1) == '*'){
               dp[0][j] = dp[0][j-2];
           }
        }
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(s.charAt(i-1) == p.charAt(j-1) || p.charAt(j-1) == '.'){
                    dp[i][j] = dp[i-1][j-1];
                }else if(p.charAt(j-1) == '*'){
                    if(dp[i][j-2]){
                        dp[i][j] = true;
                    }else if(s.charAt(i-1) == p.charAt(j-2) || p.charAt(j-2) == '.'){
                        dp[i][j] = dp[i-1][j];
                    }
                }
            }
        }
        return dp[m][n];
    }
}

72. 编辑距离

难度困难1579

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

• 插入一个字符
• 删除一个字符
• 替换一个字符

示例 1：

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

class Solution {
    //动态规划：类似于正则表达式匹配
     //状态：dp[i][j] 表示Word1和Word2的前i,j个字符组成的子字符串匹配需要的最少操作
     //状态转移方程：            min(dp[i-1][j-1]-1, dp[i][j-1], dp[i-1][j])+1    w1[i] == w2[j]
     //              dp[i][j] = 
     //                        min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j])+1      w1[i] != w2[j]
     //思路说明：i,j子字符串匹配时我们对于当前两个结尾的字符有替换、删除、插入三种选择；由于插入操作可以拆解为删除和更新的组合，所以可以不考虑
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        if(n*m == 0) return n + m;
        int[][] dp = new int[m+1][n+1];
        //初始化
        for(int i = 0; i <= m; i++){
            dp[i][0] = i;
        }
        for(int i = 0; i <=n; i++){
            dp[0][i] = i;
        }
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                int left = dp[i][j-1];
                int down = dp[i-1][j];
                int left_down = dp[i-1][j-1];
                if(word1.charAt(i-1) == word2.charAt(j-1)){
                    left_down--;
                }
                dp[i][j] = Math.min(Math.min(left, down), left_down)+1;
            }
        }
        return dp[m][n];
    }
}

01背包问题

问题描述：

给定 n 件物品，物品的重量为 w[i]，物品的价值为 c[i]。现挑选物品放入背包中，假定背包能承受的最大重量为 V，问应该如何选择装入背包中的物品，使得装入背包中物品的总价值最大？

详细解答看这篇文章。

416. 分割等和子集

难度中等755

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

class Solution {
    //动态规划：背包问题的变式
    //背包问题是从有限个带有重量和价值的商品中选出几个，使容量有限的背包装下的商品的价值最大
    //在此题目中的思路可以变换为，判断从有限的带有重量的商品中是否可以选出几个商品，使容量（target）有限的背包恰好装满
    //状态: dp[i][j] 表示对于从数组前（0，i）中选出任意个数字是否刚好能够等于j，初始值为false； i对应nums[i],表示商品， j表示当前背包的容量
    //状态转移方程：dp[i][j] = dp[i-1][j](不取nums[i])) or dp[i-1][j-nums[i]](取nums[i]);
    //为了空间优化我们只用dp[j]来记录状态，i值手动调节
    public boolean canPartition(int[] nums) { 
        int n = nums.length;
        int sum = 0;
        //求和
        for(int num : nums){
            sum += num;
        }
         //判奇,奇数不满足对半分
        if((sum & 1) == 1) return false;
        //取target
        int target = sum / 2;
        //定义状态数组
        boolean[] dp = new boolean[target + 1];
        //将背包容量为0时的状态定义为true，虽然不满组状态定义，但是方便了列状态转移方程
        dp[0] = true;
        //先取第一个商品nums[0],做个初始化
        if(nums[0] <= target) dp[nums[0]] = true;
        for(int i = 1; i < n; i++){
            if(dp[target]) return true;
            for(int j = target; j >= nums[i]; j--){
                dp[j] = dp[j] || dp[j - nums[i]];
            }
        }
        return dp[target];
    }
}

494. 目标和

难度中等650

给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例：

输入：nums: [1, 1, 1, 1, 1], S: 3
输出：5
解释：
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
一共有5种方法让最终目标和为3。

class Solution {
    //动态规划:01背包问题
    //状态：dp[i][j]  保存满足目标和为j的方法数
        //说明：将nums[0]~nums[i]这部分数做个求和，其中每个num数都有加和减两种选择，我们在dp[i][j]中保存和sum = j 的方法数
    //状态转移方程：dp[i][j] = dp[i-1][j-nums[i]] + dp[i-1][j+nums[i]]
        //dp[i-1][j-nums[i]]是选择加上当前数，dp[i-1][j+nums[i]]是选择减掉当前数nums[i]
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;//数组求和最大值
        for(int num : nums)  sum += num;
        if(Math.abs(target) > sum) return 0;
        int[] dp = new int[2*sum+1];
        //初始化状态
        if(nums[0] <= sum){
            dp[sum - nums[0]] += 1;//减当前数
            dp[sum + nums[0]] += 1;//加当前数
        }
        for(int i = 1; i < nums.length; i++){
            int[] dp_temp = new int[2*sum+1] ;//
            for(int j = 0; j <= sum*2; j++){
                if(j-nums[i] >= 0){
                    dp_temp[j] += dp[j-nums[i]];
                }
                if(j+nums[i] <= sum*2){
                    dp_temp[j] += dp[j+nums[i]];
                }
            }
            dp = dp_temp;
        }
        return dp[sum + target];
    }
}