113.路径总和 II

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

回溯-添加的角度

当前操作：维护一个sum，用目标值减去当前节点的值

子问题：进入左孩子或右孩子，用目标值减去其值

下一个子问题：same

/**
 * 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 {

    private List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        dfs(root,targetSum,new ArrayList<Integer>());
        return ans;
    }
    private void dfs(TreeNode node,int targetSum,List<Integer> list){
        if(node == null)
            return;
        targetSum-=node.val;
        list.add(node.val);
        if(node.left==null && node.right==null && targetSum==0){
            ans.add(list);
        }
		//因为传参是引用，所以第一个传入一个新的列表，避免对第二个产生影响
        dfs(node.left,targetSum,new ArrayList<>(list));
        dfs(node.right,targetSum,list);
    }

}

减少空间复杂度的话，可以用下面这种写法

/**
 * 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 {
    private List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        dfs(root,targetSum,new ArrayList<Integer>());
        return ans;
    }
    private void dfs(TreeNode node,int targetSum,List<Integer> list){
        if(node == null)
            return;
        
        targetSum-=node.val;
        list.add(node.val);
        if(node.left==null && node.right==null && targetSum==0){
            ans.add(new ArrayList(list));
        }else{
        dfs(node.left,targetSum,list);
        dfs(node.right,targetSum,list);
        }
        list.removeLast();
    }
    
}

就是相当于每个节点再递归返回之后，会退出list，这个退出在到达叶子节点之后，所以不会影响加入ans 的路径。

回溯-答案的角度

784. 字母大小写全排列

给定一个字符串s，通过将字符串s中的每个字母转变大小写，我们可以获得一个新的字符串。

返回所有可能得到的字符串集合。以任意顺序返回输出。

回溯

当前操作：对于当前位置 $i$ 的字符，如果是数字，那就下一个；不是数字，那么有两个选择（对应两个dfs），将其转为大写(小写)或不变。

子问题：对于 $i+1$ 位置的字符，进行与上面同样的操作

下一个子问题：same

那么传递的参数就是，当前路径path，当前位置i，字符串s

class Solution {
    public List<String> letterCasePermutation(String S) {
        char[] s = S.toCharArray();
        char[] path = new char[s.length];
        List<String> ans = new ArrayList<>();
        dfs(0,s,path,ans);
        return ans;
    }

    private void dfs(int i,char[] s,char[] path,List<String> ans){
        if(i==s.length){
            ans.add(new String(path));
            return;
        }
        if(s[i]>'Z'){
            path[i]=s[i];
            dfs(i+1,s,path,ans);

            path[i]=(char)(s[i]-'a'+'A');
            dfs(i+1,s,path,ans); 
        }
        else if(s[i]<='Z'&&s[i]>='A'){
            path[i]=s[i];
            dfs(i+1,s,path,ans);

            path[i]=(char)(s[i]-'A'+'a');
            dfs(i+1,s,path,ans); 
        }
        else{
            path[i]=s[i];
            dfs(i+1,s,path,ans);
        }

    }
}

也可以使用Character.isLetter()来判断是否为字母、使用Character.toUpperCase()、Character.toLowerCase() 来转化字符的大小写。

LCP 51. 烹饪料理

勇者背包内共有编号为0~4 的五种食材，其中materials[j] 表示第j 种食材的数量。通过这些食材可以制作若干料理，cookbooks[i][j] 表示制作第i 种料理需要第j 种食材的数量，而attribute[i]=[x,y] 表示第i 道料理的美味度x 和饱腹感y

在饱腹感不小于limit的情况下，请返回勇者可获得的最大美味度，如果无法满足饱腹感要求，则返回-1.

每道料理只能做一次，那么可以选择每个料理做或者不做

当前操作：做或不做这个 $i$ 料理（对应两个dfs），做的话就需要加上这个料理对应的美味度和饱腹感，然后减少对应的食材。不做的话，那就继续遍历下一个。

子问题：做或不做 $i+1$ 这个料理
·```

class Solution {
    private int ans=-1;
    public int perfectMenu(int[] materials, int[][] cookbooks, int[][] attribute, int limit) {

        dfs(0,0,materials,cookbooks,attribute,limit);
        return ans;
    }
    private void dfs(int i,int d,int[] materials, int[][] cookbooks, int[][] attribute, int limit){
        if(i==cookbooks.length){
            if(limit<=0){
                if(ans<d)
                    ans = d;
            }
            return;
        }
        dfs(i+1,d,materials,cookbooks,attribute,limit);
        if(able(i,materials,cookbooks)){
            limit-=attribute[i][1];
            d+=attribute[i][0];
            cook(i,materials,cookbooks);
            dfs(i+1,d,materials,cookbooks,attribute,limit);
            re(i,materials,cookbooks);
            
        }
        
    }

    private boolean able(int i,int[] materials,int[][] cookbooks){
        for(int j=0;j<cookbooks[i].length;j++){
            if(materials[j]<cookbooks[i][j])
                return false;
        }
        return true;
    }
    private void cook(int i,int[] materials,int[][] cookbooks){
        for(int j=0;j<cookbooks[i].length;j++){
            materials[j]-=cookbooks[i][j];
        }
    }
    private void re(int i,int[] materials,int[][] cookbooks){
        for(int j=0;j<cookbooks[i].length;j++){
            materials[j]+=cookbooks[i][j];
        }
    }    
}

2397.被列覆盖的最多行数

给你一个下标从 0 开始、大小为 $m x n$ 的二进制矩阵 $matrix$ ；另给你一个整数 $num_{Select}$ ，表示你必须从 $matrix$ 中选择的不同列的数量。
如果一行中所有的 $1$ 都被你选中的列所覆盖，则认为这一行被覆盖了。
形式上，假设 $s = \{c_1, c_2, ...., cnum_{Select}\}$ 是你选择的列的集合。对于矩阵中的某一行 row ，如果满足下述条件，则认为这一行被集合 $s$ 覆盖：
• 对于满足 matrix[row][col] == 1 的每个单元格 matrix[row][col] （0 <= col <= n - 1），col 均存在于 s 中，或者
• row 中不存在值为 1 的单元格。
你需要从矩阵中选出 $num_{Select}$ 个列，使集合覆盖的行数最大化。
返回一个整数，表示可以由 $num_{Select}$ 列构成的集合覆盖的最大行数。

回溯

当前操作：对于当前列，我们可以选择，也可以不去选择，如果选择了，选完了之后我们再判断多少个行被覆盖了。

其实不就是一个组合的问题么？从中选出numSelect个列号

下个子问题和下下个子问题相似。

维护一个集合s ，收集当前选择的列，

class Solution {
    private int ans=0;
    private Set<Integer> s = new HashSet<>();
    public int maximumRows(int[][] matrix, int numSelect) {        
        dfs(0,numSelect,matrix);
        return ans;
    }
    

    private void dfs(int i,int numSelect,int[][] matrix){
        int l = matrix[0].length;
        if(numSelect==0){
            ans = Math.max(isAns(matrix),ans);
            return;
        }
        if(i==l)
            return;
        s.add(i);
        dfs(i+1,numSelect-1,matrix);
        s.remove(i);
        dfs(i+1,numSelect,matrix);
        
    }

    private int isAns(int[][] matrix){
        int sum = 0;
        for(int i=0;i<matrix.length;i++){
            boolean flag = true;
            for(int j = 0;j<matrix[0].length;j++){
                if(matrix[i][j]==1 && !s.contains(j))
                    flag = false;
            }
            if(flag)
                sum+=1;
        }
        return sum;

    }
}

1239 串联字符串的最大长度

给定一个字符串数组 arr，字符串 s 是将 arr 的含有 不同字母 的 子序列 字符串连接所得的字符串。

请返回所有可行解 s 中最长长度。

子序列 是一种可以从另一个数组派生而来的数组，通过删除某些元素或不删除元素而不改变其余元素的顺序。

排列问题？但是多了一个要求，选择的元素中的字母不能重复。

排列问题应该怎么做？

那么就可以选或不选当前元素。。。

class Solution {
    private int ans = 0;
    public int maxLength(List<String> arr) {
        dfs(0, "", arr);
        return ans;
    }
    private void dfs(int i, String s, List<String> arr) {
        if (i == arr.size())
            return;
        String temp = arr.get(i);
        dfs(i + 1, s, arr);
        if (isDif(s.toCharArray(), temp.toCharArray())) {
            s += temp;
            dfs(i + 1, s, arr);
            ans = Math.max(s.length(), ans);
        }
    }
    private boolean isDif(char[] a, char[] b) {
        int[] a2 = new int[26];
        int[] b2 = new int[26];
        for (int i = 0; i < a.length; i++) {
            a2[a[i] - 'a']++;
        }
        for (int i = 0; i < b.length; i++) {
            b2[b[i] - 'a']++;
        }
        for (int i = 0; i < 26; i++) {
            if ((a2[i] > 0 && b2[i] > 0) || a2[i]>1 || b2[i]>1)
                return false;
        }
        return true;

  

    }

}

2212. 射箭比赛中的最大比分

Alice 和 Bob 是一场射箭比赛中的对手。比赛规则如下：

Alice 先射 numArrows 支箭，然后 Bob 也射 numArrows 支箭。
分数按下述规则计算：
1. 箭靶有若干整数计分区域，范围从 0 到 11 （含 0 和 11）。
2. 箭靶上每个区域都对应一个得分 k（范围是 0 到 11），Alice 和 Bob 分别在得分 k 区域射中 ak 和 bk 支箭。如果 ak >= bk ，那么 Alice 得 k 分。如果 ak < bk ，则 Bob 得 k 分
3. 如果 ak == bk == 0 ，那么无人得到 k 分。

例如，Alice 和 Bob 都向计分为 11 的区域射 2 支箭，那么 Alice 得 11 分。如果 Alice 向计分为 11 的区域射 0 支箭，但 Bob 向同一个区域射 2 支箭，那么 Bob 得 11 分。

给你整数 numArrows 和一个长度为 12 的整数数组 aliceArrows ，该数组表示 Alice 射中 0 到 11 每个计分区域的箭数量。现在，Bob 想要尽可能 最大化 他所能获得的总分。

返回数组 bobArrows ，该数组表示 Bob 射中 0 到 11 每个计分区域的箭数量。且 bobArrows 的总和应当等于 numArrows 。

如果存在多种方法都可以使 Bob 获得最大总分，返回其中 任意一种 即可。
[地址](2212. 射箭比赛中的最大得分 - 力扣（LeetCode）)

回溯

因为问题还是 bob 选那个区域，然后再是bob在该区域要射多少箭

显然，如果bob想要得分最大化，那么Alice射过的区域，bob要么不射，要么就射的比她还多，只用多射一个就可以了，由于共享的path是引用，还要恢复现场。

2698. 求一个整数的惩罚数

给你一个正整数 n ，请你返回 n 的 惩罚数 。

n 的 惩罚数 定义为所有满足以下条件 i 的数的平方和：

1 <= i <= n
i * i 的十进制表示的字符串可以分割成若干连续子字符串，且这些子字符串对应的整数值之和等于 i 。

2698. 求一个整数的惩罚数 - 力扣（LeetCode）

需要遍历从 $1\sim{n}$ ,然后对于 $i*i$ 表示的字符串进行切割，使用回溯求出分割出的字符串的集合，

46.全排列

46. 全排列 - 力扣（LeetCode）

对每个位置进行选择，由于每个位置每个数字都可以选一次，所以一次递归要用一个for 循环来实现对每个数选择的操作。

class Solution {

    private List<List<Integer>> ans = new ArrayList<>();

    public List<List<Integer>> permute(int[] nums) {
        boolean[] onPath = new boolean[nums.length];
        dfs(0, nums, new ArrayList<Integer>(), onPath);
        return ans;

    }

    private void dfs(int i, int[] nums, List<Integer> path, boolean[] onPath) {
        int n = nums.length;
        if (i == n) {
            ans.add(new ArrayList(path));
            return;
        }

        for (int j = 0; j < n; j++) {
            if (!onPath[j]) {
                path.add(nums[j]);
                onPath[j] = !onPath[j];
                dfs(i + 1, nums, path,onPath);
                path.remove(path.size() - 1);
                onPath[j] = false;
            }
        }

    }
}

78. 子集

78. 子集 - 力扣（LeetCode）

返回子集，那么问题就是对于当前集合，第 $i$ 个元素选或不选

class Solution {

    List<List<Integer>> ans = new ArrayList<>();

    public List<List<Integer>> subsets(int[] nums) {
      List<Integer> path = new ArrayList<>();
      dfs(0,nums,path);
      return ans;
    }

    private void dfs(int i,int[] nums,List<Integer> path){
      if(i==nums.length){
        ans.add(new ArrayList<>(path));
        return;
      }

      dfs(i+1,nums,path);

      path.add(nums[i]);
      dfs(i+1,nums,path);
      path.remove(path.size()-1);
    }
}

17.电话号码的字母组合

看题目就知道是排列了，由于一个位置有多种可能，所以要用一个for循环遍历一下。

class Solution {
    List<String> ans = new ArrayList<>();
    
    private String[] nums = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    public List<String> letterCombinations(String digits) {
      if(digits.length()==0)
        return ans;
      dfs(0,digits.toCharArray(),"");
      return ans;
        
    }
    private void dfs(int i,char[] digits,String path){

      if(i==digits.length){
          ans.add(path);
          return;
      }
      String temp = nums[digits[i]-'0'];
      for(char c : temp.toCharArray()){
          String temp1 = path + c;
          dfs(i+1,digits,temp1);
      }
    
    }
}

39.组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

39. 组合总和 - 力扣（LeetCode）

无限制重复被选取，那么原问题就是

选当前数
不选当前数

子问题：下一个数选什么

当前数
不选当前数

边界应该就是直到选的数的总和大于target 为止。（其实还有当前遍历位置大于候选数组长度）

class Solution {

    private List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<Integer> path = new ArrayList<>();
        dfs(0,target,candidates,path);
        return ans;
    }

    private void dfs(int i,int target,int[] candidates,List<Integer> path){
        if(target<0||i==candidates.length){
          if(target<0||target>0)
            return;
          ans.add(new ArrayList(path));
          return;
        }
        int elm = candidates[i];
        path.add(elm);
        dfs(i,target-elm,candidates,path);
        path.removeLast();

        dfs(i+1,target,candidates,path);
    }


}

22. 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

n 就是左右括号的个数，一共有2n 个位置可供选择，且最后一个位置必然不是左括号，且当前填入的右括号个数必然小于等于左括号的个数

class Solution {
    private char[] parentheses = {'(',')'};
    private List<String> ans = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        
        char[] path = new char[n*2];
        dfs(0,0,0,n,path);
        return ans;
    }
    private void dfs(int i,int left,int right,int n,char[] path){
        if(left==n&&right==n){
          ans.add(new String(path));
          return;
        }
        if(left<n){
          path[i]=parentheses[0];
          dfs(i+1,left+1,right,n,path);
        } 
        if(right<left){
          path[i]=parentheses[1];
          dfs(i+1,left,right+1,n,path);
        }
    }
}

79. 单词搜索

79. 单词搜索 - 力扣（LeetCode）

想办法遍历一个二维字符网格，找到一个对应单词。

原问题：对于当前字符，是否加入到path[i] 中，如果它等于word[i] ，那么就加入。

子问题：下一个遍历的位置如何确定？一共有上下左右四个方向，选过的不能选，越界的不能选，

终止条件：无字符可选，当前path已经等于word

class Solution {
    private boolean ans = false;

    public boolean exist(char[][] board, String word) {
        
        
        int m = board.length;
        int n = board[0].length;
        for(int i=0;i<m;i++){
          boolean[][] chosen = new boolean[m][n];
          char[] path = new char[word.length()];
          for(int j =0;j<n;j++){
            if(ans)
              return ans;
            dfs(0,i,j,path,board,word,chosen);
          }
        }
        return ans;

    }

    private void dfs(int k,int i,int j,char[] path,char[][] board,String word,boolean[][] chosen){

        int m = board.length;
        int n = board[0].length;
        if(k==word.length() || ans==true || i==m || j==n || i<0 || j<0){
          String temp = new String(path);
          if(temp.equals(word))
              ans = true;
          return;
        }
        if(chosen[i][j])
          return;


        path[k] = board[i][j];
        if(path[k]!=word.charAt(k))
          return;
        chosen[i][j]=true;
        dfs(k+1,i+1,j,path,board,word,chosen);
        dfs(k+1,i-1,j,path,board,word,chosen);
        dfs(k+1,i,j+1,path,board,word,chosen);
        dfs(k+1,i,j-1,path,board,word,chosen);
        chosen[i][j]=false;
        
    }

}

时间复杂度有点爆炸。。。

131. 分割回文串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

分割子串，对于位置i ，假设左边已经分割过了，那么右边就要进行遍历，从而确认下一个分割位置。每得到一个子串，就判断是否回文，不回文的就直接退出递归。

class Solution {


    private List<List<String>> ans = new ArrayList<>();
    public List<List<String>> partition(String s) {
      List<String> list = new ArrayList<>();

      dfs(0,s,list);
      return ans;
        
    }

    private void dfs(int i,String s,List<String> list){
      if(i==s.length()){
        ans.add(new ArrayList<>(list));
        return;
      }
      for(int j=i;j<s.length();j++){
        String temp = s.substring(i,j+1);
        if(isParlindrome(temp.toCharArray())){
          list.add(temp);
          dfs(j+1,s,list);
          list.remove(list.size()-1);
        }
      }


    }
    private boolean isParlindrome(char[] arr){
      int left = 0;
      int right = arr.length-1;
      while(left<right){
        if(arr[left]!=arr[right]){
          return false;
        }
        left++;
        right--;
      }
      return true;
    }
}

51. N皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

会攻击同一行、同一列或者同一斜线上的棋子，也就是说棋子不能在同一行、同一列或者同一斜线上。又因为有 n 个皇后，可以知道如果将 n-1 个皇后分别放在 n-1 行或列上，那么第
n 个棋子，不能放在这 n-1 行或列上，必须放在第 n 行或列上。也就是说，我们要使得每一个行或列都有一个棋子。

那么我们可以设置一个 n 维数组，代表每一行，反正每一行都是要放一个棋子的，所以只用考虑每一行，需要在哪一列放棋子。其实这就是列号的全排列，这样转化问题，我们可以确定一个行和列上是不会出现两个棋子的，只需要考虑斜线上还会不会出现重复。

那么如何判断他们是否在同一条斜线上面呢？根据直线函数可以知道，在同一条斜线上，斜率肯定是相等的。也就是说对于两个点 (r,c) 和 (i,j)，只需要判断 r-i == c-j 或 r-i = j-c 即可（一个斜率是 +1，一个是 -1）。

class Solution {

    List<List<String>> ans = new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        
        boolean[] onPath = new boolean[n];
        int[] col = new int[n];
        List<String> list = new ArrayList<>();
        dfs(0,col,n,list,onPath);
        return ans;
    }

    private void dfs(int i,int[] col,int n,List<String> list,boolean[] onPath){
        if(i==n){
          String dot = ".";
          for(int k=0;k<n;k++)
            list.add(dot.repeat(col[k])+"Q"+dot.repeat(n-col[k]-1));
          ans.add(new ArrayList(list));
          list.clear();
          return;
        }

        for(int j=0;j<n;j++){
          if(!onPath[j]&&isValid(i,j,col)){
            col[i]=j;
            onPath[j] = true;
            dfs(i+1,col,n,list,onPath);
            onPath[j] = false;
          }
        }
    }
    private boolean isValid(int r,int c,int[] col){
        for(int i = 0; i < r ; i++){
            int j = col[i];
            if(r+c == i+j || r-c == i-j)
              return false;
          
        }
        return true;
    }
}

160. 相交链表

https://leetcode.cn/problems/intersection-of-two-linked-lists/solutions/2958778/tu-jie-yi-zhang-tu-miao-dong-xiang-jiao-m6tg1
灵神太强了。。。

141. 环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。否则，返回 false 。

21.合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回

直觉是使用四个指针，分别表示两个链表的范围，将 $left1<=left2$ 到 $right1<=right2$ 这个范围的元素插入到第一个链表中，

138. 随机链表的复制

148. 排序链表

很自然的想法是，将其转化成列表，然后再转换成链表。

23.合并 K 个升序链表

这和合并两个链表又什么区别呢？

暴力解决确实没什么区别，但是使用分治后效率会大大提升，这个步长设置很巧妙啊。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        int n = lists.length;
        if(n==0)
            return null;
        for(int step=1;step<=n;step*=2)
            for(int i = 0;i<n-step;i+=step*2){
                lists[i] = mergeList(lists[i],lists[i+step]);
            }
        return lists[0];
    
    }

    private ListNode mergeList(ListNode list1,ListNode list2){
        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        while(list1!=null&list2!=null){
            if(list1.val<list2.val){
                cur.next = list1;
                list1 = list1.next;
            }
            else{
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        cur.next = list1==null?list2:list1;
        return dummy.next;

    }
}

小根堆

因为每个局部链表都是有序的，那么新并的链表的第一个节点，必然是某个链表的头节点。

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
        for (ListNode head : lists) {
            if (head != null) {
                pq.offer(head); // 把所有非空链表的头节点入堆
            }
        }

        ListNode dummy = new ListNode(); // 哨兵节点，作为合并后链表头节点的前一个节点
        ListNode cur = dummy;
        while (!pq.isEmpty()) { // 循环直到堆为空
            ListNode node = pq.poll(); // 剩余节点中的最小节点
            if (node.next != null) { // 下一个节点不为空
                pq.offer(node.next); // 下一个节点有可能是最小节点，入堆
            }
            cur.next = node; // 把 node 添加到新链表的末尾
            cur = cur.next; // 准备合并下一个节点
        }
        return dummy.next; // 哨兵节点的下一个节点就是新链表的头节点
    }
}

226. 翻转二叉树

递归即可

/**
 * 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 {
    public TreeNode invertTree(TreeNode root) {
        invert(root);
        return root;
    }

    private void invert(TreeNode node){
        if(node==null)
            return;
        
        invert(node.left);
        invert(node.right);
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;
        return;
    }
}

101. 对称二叉树

对比大神的脑袋，我发现我还是得继续前进。。。

543. 二叉树的直径

二叉树的直径是指树中任意两个节点之间最长路径的长度。

列举一下，两个树如果在同一个分支，那么它们的路径长度就是深度之差，如果在左右子树中，那么就是到根节点的路径长度之和。

也就是说，实际上只用维护左右子树的最大深度，如果只有一个子树，那么就是其最大深度，如果有两个子树，那么就是左右子树深度之和。

/**
 * 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 {
    int max = Integer.MIN_VALUE;
    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return max;

    }

    private int dfs(TreeNode node){
        if(node == null)
            return 0;
        
        int left = dfs(node.left);
        int right = dfs(node.right);
        max = Math.max(left+right,max);
        return Math.max(left,right)+1;
    }
}

102. 二叉树的层序遍历

肯定要使用队列了，但是这个输出要求，要把同一层的节点放在一个列表里面。

那么问题就是，我要先让一层节点全出去了，然后再开始入队？那么应该再用一个队列存放这个节点，或者

108. 将有序数组转换成为二叉搜索树

问题：给你一个整数数组nums ，其中元素已经按照升序排列，请你将其转换为一棵平衡的二叉搜索树

二叉搜索树的性质是，左子树的值均小于当前节点的值，右子树的节点均大于当前节点的值。

可以用二分查找找到中间的节点作为根节点。然后左边的再二分查找，右边再二分查早。

ok，可以用分治法去解决。

/**
 * 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 {
    public TreeNode sortedArrayToBST(int[] nums) {
        int left = 0;
        int right = nums.length-1;
        TreeNode dummy = new TreeNode();
        dummy = binarySearch(nums,left,right);
        return dummy;

    
    }

    private TreeNode binarySearch(int[] nums,int left,int right){
        if(left>right){
            return null;
        }
        
        int mid = (right-left)/2+left;
        TreeNode node = new TreeNode(nums[mid]);
        node.left = binarySearch(nums,left,mid-1);
        node.right = binarySearch(nums,mid+1,right);
    
        return node;

    }
}

晕厥式做题🤣🤣🤣

98. 验证二叉搜索树

二叉搜索树的定义如下

节点的左子树只包含严格小于当前节点的数
节点的右子树只包含严格大于当前节点的数
所有左子树和右子树都是二叉搜索树

根据最后一点知道，可以使用递归。还有一点坑，如何解决右子树的最小值比根节点小的情况？

可以设置一个值，专门存储右子树的最小值，那么如何更新这个最小值呢，要设置成一个函数的参数，如果这个节点的右节点的小于rightMin，就更新这个右小值，如果这个节点的左节点大于leftMax，就更新这个左大值。

作为参数不太行，因为传参从下到上修改的话，对于值传递，参数不会变。。

应该用返回值，那么就是后序遍历，因为只有先遍历左右两棵子树才能得到左右子树的最大值和最小值。

199. 二叉树的右视图

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

很自然的想法是利用层序遍历获得每一层最后一个节点。但是灵神教过一个更加精妙的做法，我现在已经忘了。。。

算了，速度第一。。

加油加油，还有十天，再刷一遍应该没什么问题。

/**
 * 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 {
    public List<Integer> rightSideView(TreeNode root) {
        
        List<Integer> ans = new ArrayList<>();
        if(root==null)
            return ans;
        List<TreeNode> list = new ArrayList<>();
        list.add(root);
        while(list.size()!=0){
            int n = list.size();
            while(n>0){
                TreeNode node = list.removeFirst();
                if(node.left!=null)
                    list.add(node.left);
                if(node.right!=null)
                    list.add(node.right);
                if(n==1)
                    ans.add(node.val);
                n--;
            }
        }
        return ans;
        
    }

    
}

114. 二叉树展开为链表*

给你二叉树的根结点 root ，请你将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。

管他呢，先暴力，暴力不了。。。

236. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

如果两个节点在同一个路径上，那么就是第一个出现的节点，如果两个节点在同一个分支中，那么就是这个分支的根节点。

如何判断是不是在同一个路径上呢？分别对其进行深度遍历？

如果不在一个路径上，那么必然就是在两个分支中，那么如何找到最近的那个节点？

如果说在一条路径上，那么对于一个节点，左右子树总有一个返回是空的，都不满足，直到p节点或q节点才返回即可。如果在两个分支中，那么第一个满足左右都不为空的才是，对于这个满足的节点的父结点，它的另一个孩子节点返回必然是空。

所以这其中有一个共同点，就是已经遍历到p或q才返回。

第一种是只遍历到p或q，第二种是遍历到两个。

那么这两种情况如何区别的？如果在一条路径上，对于遍历到的p或q节点，其上面一个节点另一边必然返回空，所以必然不满足第二种的条件。

对于第二种呢，如果当前节点满足，那么遍历左子树和右子树就会返回p或q，最后返回当前节点。

105. 从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder,其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

先序遍历，第一个节点是根节点，

中序遍历，左右子树在根节点的两边

先找到一个根节点，然后再将inorder划分成左右两边。

437. 路径总和|||

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的路径的数目。

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

如果是第一档次的话，就是从根节点开始遍历了。

哎，又想回家种田了，但是天才都说，没天赋。。。也许差的就是这个吧。

124.二叉树中的最大路径和

二叉树中的路径被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

33. 搜索旋转排序数组

那就把数组扩展，把旋转位置前面的数扩展到数组后面就可以了。用求模运算实现。

但是这样做的话，我的第一个直觉是要找到旋转位置，用一次遍历找的话，时间复杂度都已经到了O(n) 了。。。而且用一次遍历的话，不是可以直接找到下标了吗。。

对于数组 4,5,6,7,0,1,2，寻找 0

这个找的方法其实很简单，因为旋转位置满足前一个数大于当前位置。

实际上不太简单。。。

在已知答案的情况下反推原因

nums[mid] 在 target 右侧的情况有以下几种

nums[mid]<=nums[-1] && target<=nums[mid] 即 mid和 target 都在第二段递增子数组中
nums[mid]<=nums[-1] && target > nums[-1] ，mid 在第二段， target 在第一段。
nums[mid]>nums[-1] && target<nums[mid] 都在第一段

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length-2;
        while(left<=right){
            int mid = (right-left)/2+left;
            if(isBlue(nums,target,mid))
                right = mid-1;
            else
                left = mid +1;

        }
        if(left==nums.length || nums[left] !=target)
            return -1;
        return left;
    }

    private boolean isBlue(int[] nums,int target,int mid){
        int n = nums.length-1;
        if(nums[mid]>nums[n]){
            return target>nums[n] && target<=nums[mid];
        }
        return target>nums[n] || nums[mid]>=target;
    }
}

153.寻找旋转排序数组中的最小值

上一个题目是在旋转排序数组中寻找特定的值，这个是寻找最小值，那么这两个有什么联系呢？

由上一题可以知道，通过比较 nums[mid] 和最后一个值的大小，可以知道 nums[mid] 在第一段递增数组中，还是在第二段递增数组中(如果大于最后一个值，那么在第一段中，反之则在第二段数组中)。

那么对于最小值呢，它必然小于最后一个值，同时它也小于左边的值

那么怎么收敛边界呢，如果它小于等于最后一个值，那么就可以设为 right ，如果大于最后一个值呢？那么它肯定在最小值的左边( 4,5,6,7,0,1,2 )。

class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length-1;
        int n = right;
        while(left<=right){
            int mid = (right-left)/2+left;
            if(nums[mid]>nums[n]){
                left = mid+1;
            }
            else
                right = mid -1;
        }
        return nums[left];
    }
}

二分查找法真是一个伟大的算法啊：）

4. 寻找两个正序数组的中位数

中位数是指在按非递减的顺序排列数组，其中间位置的数。

那么两个数组的中位数和合并后的数组的中位数有关系吗

1,2,3,4 ,1,3,5,7。一个是 2.5，一个是 4，合并后1,1,2,3,3,4,5,7，中位数是3。没什么关系

过了十分钟了，毫无头绪，遂看答案。orz 。真是每天都被大佬感动了

73. 矩阵置零

用两个数组来标志行和列是不是全零就可以了。

54. 螺旋矩阵

如何模拟螺旋这个方式？用四个值存储行和列的开始和结束？rb,re,cb,ce 。到达行的末尾，就re-=1 ，然后往下走；到达列的末尾，就ce-=1 ，然后往左走；到达行的开始，就rb+=1 ，然后往上走；到达列的开始就cb-=1

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        int rowb = 0;
        int columnb = 0;
        int rowe = matrix.length-1;
        int columne = matrix[0].length-1;
        int n = (rowe+1)*(columne+1);
        List<Integer> ans = new ArrayList<Integer>();

        int i = 0;
        while(ans.size()<n){
            for(i = columnb;i<=columne;i++){
                ans.add(matrix[rowb][i]);
            }
            rowb+=1;
            if(rowb>rowe)
                return ans;
            
        
            for(i =rowb;i<=rowe;i++){
                ans.add(matrix[i][columne]);
            }
            columne-=1;
            if(columne<columnb)
                return ans;

            for(i =columne;i>=columnb;i--){
                ans.add(matrix[rowe][i]);
            }
            rowe-=1;
            if(rowe<rowb)
                return ans;


            for(i = rowe;i>=rowb;i--){
                ans.add(matrix[i][columnb]);
            }
            columnb+=1;
            if(columnb>columne)
                return ans;

        }
        return ans;
    }
}

总之，先写出来再说，虽然不是很优雅，但是至少做出来了。

48.旋转图像

旋转图像，它们的位置关系是什么呢

灵感是直角坐标系，以左上角为支点顺时针90度，那确实是这个图像，可是题目要求原地旋转

3,1 -> 1,1 , 2,1 -> 1,2

好像看出一点规律了。顶角的是顺时针对应，好吧不是的。

哦哦，第一列倒序放在第一行，第二列倒序放在第二行。题目要求原地旋转图像，那么不能简单地对应存，还是需要想出更加精妙的算法。

比如说n=2
i,j= j,n-i 10->01,

居然可以用两次翻转实现，真是太美妙了。

240. 搜索二维矩阵II

每行的元素从左到右升序排列，每列的元素从上到下升序排序。

198.打家劫舍

原问题：对于第 i 个房子，抢或者不抢。

子问题：从前 i 个房子中得到的最大金额

下一个子问题：
不选第 i 个房子：从前 i-1 个房子中得到的最大金额
选：从第 i-2 个房子中得到的最大金额

状态转移方程 dfs[i] = max(dfs[i-1],dfs[i-2]+nums[i])

322. 零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币，以及一个整数
amount ，表示总金额，计算并返回可以凑成总金额所需的最少硬币个数。

当前操作：当前硬币 coin[i] 选或者不选

子问题：
选：amount-=coin[i] ，在i~n中有多少种组合方式
不选：amount 不变，在 i+1~n 中有多少种组合方式

状态转移方程 dfs[i,amount]=min(dfs(i-1,c),dfs(i,amount-coin[i]+1)

118. 杨辉三角

直截了当的 DP。

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ans = new ArrayList<>();
        ans.add(List.of(1));
        for(int i = 1;i<numRows;i++){
            List<Integer> list = new ArrayList<>();
            int a = 0;
            int b = 0;
            for(int j = 0;j<=i;j++){
                if(j-1<0)
                    a = 0;
                else
                    a = ans.get(i-1).get(j-1);
                if(j==i)
                    b = 0;
                else
                    b = ans.get(i-1).get(j);
                list.add(a+b);
            }
            ans.add(list);
        }
        return ans;
    }
}

：）这里就是梦开始的地方 mark

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ans = new ArrayList<>();
        ans.add(List.of(1));
        for (int i = 1; i < numRows; i++) {
            List<Integer> list = new ArrayList<>();
            int a = 0;
            int b = 0;
            for (int j = 0; j <= i; j++) {
                a = j - 1 < 0 ? 0 : ans.get(i - 1).get(j - 1);
                b = j == i ? 0 : ans.get(i - 1).get(j);
                list.add(a + b);
            }
            ans.add(list);
        }
        return ans;
    }
}

70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

当前操作：爬 1 个台阶还是爬 2 个台阶

子问题：对于当前位置 i ，有多少种方法到达终点。

边界：当前位置大于 n 或者恰好等于 n

状态转移方程 dp[i] = dp[i-1]+dp[i-2]

class Solution {
    public int climbStairs(int n) {
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 0;i<n-1;i++){
            dp[i+2] = dp[i+1]+dp[i];
        }
        return dp[n];
    }
}

746. 使用最小花费爬楼梯

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

当前操作：向上爬一个还是两个台阶

子问题：到达第 i 个问题的最小花费

下一个子问题：到达第i+1个台阶的最小花费

状态转移方程： dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n+1];
        for(int i = 0;i<n-1;i++){
            dp[i+2] = Math.min(dp[i]+cost[i],dp[i+1]+cost[i+1]);
        }
        return dp[n];
    }
}

我爱 DP ！！！

740. 删除并获得点数

给你一个整数数组 nums ，你可以对它进行一些操作。

每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除所有等于 nums[i] - 1 和 nums[i] + 1 的元素。

开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

当前操作：选择删除 num[i]，或者不删除，用一个HashMap存储？

子问题：对于不包含 num[i]、num[i]-1、num[i]+1 的数组，返回操作能获得的最大点数

状态转移方程： f[value] = max(f[value-2]+value*times,f[value-1])

但是这样要一个最大值长度的数组来存储

2466. 统计构造好字符串的方案数

给你整数 zero ，one ，low 和 high ，我们从空字符串开始构造一个字符串，每一步执行下面操作中的一种：

将 '0' 在字符串末尾添加 zero 次。
将 '1' 在字符串末尾添加 one 次。

以上操作可以执行任意次。

如果通过以上过程得到一个长度在 low 和 high 之间（包含上下边界）的字符串，那么这个字符串我们称为好字符串。

请你返回满足以上要求的不同好字符串数目。由于答案可能很大，请将结果对 $10^9+7$ 取余后返回。

当前操作，选择 0 添加 zero 次，还是选择 1 添加 one 次

其实可以确定长度在 low 和 high 之间需要多少个 zero 和one ， low <= zero*x+one*y <= high,可以遍历

。。。一看答案，居然是爬楼梯，太好了

dp[i] = dp[i-zero]+dp[i-one]

由于当 i<zero i <one 时，除了 i=0 时 dp[i]=1 ，其余全部为0

下面是将递归式化成了两步

dp[i] = dp[i-zero]
dp[i] = dp[i] + dp[i-one] (如果没有上一步的话，dp[i] 默认初始化是0，所以没有影响)。

class Solution {
    public int countGoodStrings(int low, int high, int zero, int one) {
        int MOD = 1000000007;
        int[] dp = new int[high+1];
        int ans = 0;
        dp[0] = 1;
        for(int i = 1;i<=high;i++){
            if(i>=zero)
                dp[i] = dp[i-zero];
            if(i>=one)
                dp[i]=(dp[i]+dp[i-one])%MOD;
            if(i>=low)
                ans=(ans+dp[i])%MOD;
        }
        

        return ans;

    }
}

279. 完全平方数

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

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

应该先找到1~sqrt(n)的全部平方数。

1	dp[i] = min(dp[i-1],dp[i-4],dp[i-9],...dp[i-..])+1;

class Solution {
    public int numSquares(int n) {
        int temp = (int)Math.sqrt(n);
        int[] square = new int[temp+1];
        for(int i=0;i<=temp;i++){
            square[i] = i*i;
        }
        int[] dp = new int[n+1];
        dp[0] = 0;
        for(int i =1;i<=n;i++){
            temp = Integer.MAX_VALUE;
            for(int j=1;j<=(int)Math.sqrt(i);j++){
                temp = Math.min(dp[i-square[j]],temp);
            }
            dp[i] = temp+1;
        }
        return dp[n];

    }
}

我的做法很直观，但是耗时比灵神的多了太多。时间复杂度居然一样？

灵神的做法：完全背包的变形，相当于完全平方数作为物品，选或者不选，每个完全平方数价值为 1,背包的容量就是 n。
dp[c] = min(dp[c],f[c-i*i]+1)

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n+1];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0] = 0;
        for(int i =1;i*i<=n;i++){
            for(int j=i*i;j<=n;j++){
                dp[j] = Math.min(dp[j-i*i]+1,dp[j]);
            }
        }
        return dp[n];

    }
}

错排问题（学习）

考虑一个有n 个元素的排列，若一个排列中所有元素都不在自己原来的位置上，那么这样的排列就称为原排列的一个错排。n 个元素的错排数记为D(n)

D(n) = (n-1)*(D(n-1)+D(n-2))

当n=1时，没有的选， D(n)=0

当n=2时，只有一种选法，就是互换 D(n)=1

看着像是可以用动态规划解决。

2915. 和为目标值的最长子序列的长度

给你一个下标从 0 开始的整数数组 nums 和一个整数 target 。

返回和为 target 的 nums 子序列中，子序列 长度的最大值 。如果不存在和为 target 的子序列，返回 -1 。

子序列 指的是从原数组中删除一些或者不删除任何元素后，剩余元素保持原来的顺序构成的数组。

当前操作：当前值 nums[i] 选择或者不选择

子问题：
1. 选择：从· 0~i-1 的数组，找和为 target-nums[i] 的子序列的长度的最大值
2. 不选择：从 0~i-1 的数组，找和为 target 的子序列的长度的最大值

边界条件是什么呢？

当target = 0 时，那么子序列长度就是0。

状态转移方程
dp[i][j] = Math.max(dp[i-1][j-nums[i]]+1,dp[i-1][j]

这是一个 01 背包问题,状态转移方程可以转化成
dp[j] = Math.max(dp[j-nums[i]]+1,dp[j]) ，

因为 dp[i+1] 只和 dp[i] 的两个元素有关，所以只用保证这两个不被修改即可，可以反向遍历，这样当前遍历到的元素之前的元素就不会被修改了。

416. 分割等和子集

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

既然只能分割成两个子集，且两个子集的元素和相等，那不就是找个子集，使得这个子集和等于原始的一半就行了么。。

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for(int x : nums){
            sum+=x;
        }
        if(sum%2!=0)
            return false;
        return dfs(0,nums,(int)sum/2);
        
        
    }
    public boolean dfs(int i,int[] nums,int target){
        if(i==nums.length){
            if(target!=0)
                return false;
            return true;
        }
        boolean choose = dfs(i+1,nums,target-nums[i]);
        boolean nchoose = dfs(i+1,nums,target);
        return choose||nchoose;
    }
}

回溯超时了。

记忆化搜索

状态转移方程，将数组比作物品，目标值比作容量，但是吧，好像只要有一个为 true 就可以返回了
dfs[i][j] = dfs[i-1][j-nums[i]]||dfs[i-1][j]

263. 丑数

丑数就是只包含质因数 2、3 、5 的正整数。那么我有一个问题

辗转相除法：
gcd(a,b) = gcd(b,a%b)

class Solution {
    public boolean isUgly(int n) {
        if(n<=0)
            return false;
        while(n%2==0)
            n/=2;
        while(n%3==0)
            n/=3;
        while(n%5==0)
            n/=5;
        return n==1;
    }
}

结合之前学的对 2 的幂的判断方法可以进一步优化。

class Solution {
    public boolean isUgly(int n) {
        if (n <= 0) {
            return false;
        }
        while (n % 3 == 0) {
            n /= 3;
        }
        while (n % 5 == 0) {
            n /= 5;
        }
        return (n & (n - 1)) == 0;
    }
}

很简单，很巧妙。

50 快速幂

https://leetcode.cn/problems/powx-n/solutions/2858114/tu-jie-yi-zhang-tu-miao-dong-kuai-su-mi-ykp3i

class Solution {
    public double myPow(double x, int n) {
        double ans = 1;
        long nn = n;
        if(nn<0){
            nn = -nn;
            x = 1/x;
        }
        while(nn!=0){
            if((nn&1)==1){
                ans *=x;
            }
            x*=x;
            nn>>=1;
        }
        return ans;
    }
}

2413. 最小偶倍数

给一个正整数 n ，返回 2 和 n 的最小公倍数。

如果 n 是一个奇数的话, 那么最小公倍数应该就是 2*n了吧。

如果 n 是一个偶数的话,那就是 n 本身了?

… 还真是, 不过其实想想也很好解释, n~ 2*n 这段里面,只有 n 和 2*n 是 n 的倍数，又因为 n 不是 n 的倍数，所以自然，最小公倍数就只有 2*n 了。

2236. 判断根节点是否等于子结点之和

。。。太简单了

1534 统计好三元组*

https://leetcode.cn/problems/count-good-triplets/solutions/3622921/liang-chong-fang-fa-bao-li-mei-ju-qian-z-apcv

很好的数学题，使我旋转

139. 单词拆分

完全背包的板子

当前操作：选或不选当前这个字符串 wordDict[i]

子问题：
选：对于去掉了 wordDict[i] 的字符串 s ，选或不选下一个字符串
不选：对于字符串 s 选或不选下一个字符串

df[i][j] = df[i][j-word[i]] || df[i-1][j]

边界条件 ：什么都不选，且 j 也为空，自然就是 true ，所以 dp[0][0]= true

可是这里的 j 它是一个字符串，那么数组存肯定不行，那么使用什么呢？

好吧，看了答案，应该转换思维，对于不同方式切割字符串，判断当前切割出的子串是否在 wordDict 之中。

$dp[i] = dp[j]\ \ \&\&\ \ isSubstring(j...i-1)$

300. 最长递增子序列

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

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

当前操作：是否将 nums[i] 添加到子序列中。

子问题：对于位置 i+1的最长递增子序列的长度？

$dp[i] = max(dp[i-1],)$

这么拆解好像并不能得到最优子结构。这个问题相当于什么，我们要在数组 nums 中选择若干数字，使其满足长度最大且递增。要使这个序列相对顺序不变，可以通过从顺序遍历一遍即可。

区别于 01背包问题，我们要选择物品，使当前价值最大。这里第二个索引是背包的容量。而对于当前问题，我们好像没有背包容量的限制。

当然，可以通过回溯实现一个算法，通过选或不选每个数字，同时添加约束，有效的叶结点是严格递增（即添加的下一个节点大于当前叶结点）。