力扣小题， 力扣113.路径总和II力扣.111二叉树的最小深度 力扣.221最大正方形力扣5.最长回文子串更加优秀的算法:中心扩展算法

目录

力扣113.路径总和II

力扣.111二叉树的最小深度

 力扣.221最大正方形

力扣5.最长回文子串

更加优秀的算法:中心扩展算法

力扣113.路径总和II

这道题，让我明白回溯了到底啥意思

之前我找的时候，我一直在想，如果可以，请你对比一下这个代码和下面那个代码

我们这个相当于自动回溯，因为他是引用传递，所以说就不用维护了

/**
 * 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<List<Integer>>ret=new LinkedList<>();
    public  List<Integer>res=new LinkedList();
     int targetSum=0;
    public  List<List<Integer>> pathSum(TreeNode root, int _targetSum) {
        targetSum=_targetSum;
        dfs(root,0);
        return ret;
    }
    public  void dfs(TreeNode root,int count){  
        if(root==null)return;
        count+=root.val;
        res.add(root.val);
        if(count==targetSum&&root.left==null&&root.right==null){
            ret.add(new LinkedList<>(res));
        }
        dfs(root.left,count);
        dfs(root.right,count);
        res.removeLast();
    }
}

这个是错误代码，为什么这个是错误的，上面确实正确的呢，是因为

下面这个我们无法回溯，你回溯要有一个计数器那种，怎么维护这个计数器是关键，我假如使用下面的这个，我们回溯，减法的话，怎么减去呢，我如果使用减法回溯计数器，我就要知道他回溯前的节点是什么，可是我们无法知道回溯前 的节点是啥，所以下面这个错误 

/**
 * 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 static List<List<Integer>>ret=new LinkedList<>();
    public static List<Integer>res=new LinkedList();
    static int count=0;
    static int targetSum=0;
    public static List<List<Integer>> pathSum(TreeNode root, int _targetSum) {
        targetSum=_targetSum;
        dfs(root);
        return ret;
    }
    public static void dfs(TreeNode root){  
        if(root==null)return;
        count+=root.val;
        res.add(root.val);
        if(count==targetSum&&root.left==null&&root.right==null){
            ret.add((List<Integer>) res);
        }
        dfs(root.left);
        dfs(root.right);
       
        res.removeLast();
    }
}

力扣.111二叉树的最小深度

这个正常情况好想，你假如剪枝的话，就不是很好想了，看代码分析，

他的剪枝分在两个地方，第一个到了叶子结点，不再往后遍历，第二个是当前最大深度已经比最小的深度大了，就直接放弃就好了

class Solution {
    int ans = Integer.MAX_VALUE;
    public int minDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        dfs(root, 0);
        return ans;
    }

    private void dfs(TreeNode root, int cnt) {
        if(root == null) {
            return;
        }
        //记录每一层
        cnt++;
        if(cnt > ans) {
            //比最小值大，直接排除
            return;
        }
        //这一步可能就是假如左右端点都为空，那么我就不去遍历了。减去叶子结点的下面（因为我已经到达最下面的节点了。）
        if(root.left == root.right) {
            ans = Math.min(ans, cnt);
            return;
        }
        dfs(root.left, cnt);
        dfs(root.right, cnt);
    }
}

 力扣.221最大正方形

太久没写动规了，回顾一下

我们只需要会一个，也是最难的状态定义

这里定义i,j位置为以i,j为右下角的最大正方形边长

那么初始化这件事不知道你能不能想出来，右下角的话你的最左边一行，和最上边一行是不是都要初始化为1，假如哪个原先位置字符是1的话，你想一下，右下角，你怎么可以拿最左边和最上边为右下角呢

然后他的边长，我是这么想的，你看这个图，假如想要边长变大，是不是，你的左边，上面，以及你的对角线那个位置都要是1，不然你不可能是正方形(或者说，正方形的边长，那么dp[][]这些位置，肯定都要有值

class Solution {
    public int maximalSquare(char[][] matrix) {
        int n=matrix.length;
        int m=matrix[0].length;
       //dp[i][j] 在i,j位置，包含1的最大正方形,
       int[][]dp=new int[n][m];
         for(int i=0;i<n;i++){    
        if(matrix[i][0]=='1'){dp[i][0]=1;}
    }
    for(int j=0;j<m;j++){
        if(matrix[0][j]=='1'){dp[0][j]=1;}
    }
       int maxSide=0;
       for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){

            if(matrix[i][j]=='1'&&(i!=0&&j!=0)){
             dp[i][j]=Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;   
            }
            maxSide=Math.max(maxSide,dp[i][j]);
        }
       }

       return maxSide*maxSide;
    }
}

力扣5.最长回文子串

这个题，你首先明确状态转移方程

boolean[][]dp 他是i位置开头，j位置结尾，那我问你，我两边相等，我是不是要检查中间，然后后面就这么些，前面的判断是因为，一个字符，或者两个字符，我可以直接给他判定为回文

  public static String longestPalindrome(String s) {
        int n=s.length();
        //dp[i][j]:设置以i位置开头，j位置结尾的dp
        int len=1;
        int begin=0;
        //判断i位置开头，j位置结尾的dp。
        boolean[][]dp=new boolean[n][n];
        //检查，从后往前找，因为 [i,j] =[i+1][j-1]
        for(int i=n-1;i>=0;i--){
            for(int j=i;j<n;j++){
                if(s.charAt(i)==s.charAt(j)){
                    if(i==j||i+1==j){
                        //a ,aa 两个字符或者一个字符的情况  babad
                        dp[i][j]=true;
                    }
                    else{
                        //中间有字符，接下来看看i+1和j-1这个位置看看，为啥要到这个位置看，我今天才搞明白，
                        // 是因为我需要看你里面是不是回文字符串，假如他俩下标不挨着，那么就看看中间有没有不是回文的
                        //换句话说，计算机思路先检查外面，再检查里面。
                        dp[i][j]=dp[i+1][j-1];
                    }
                }
                //假如发现当前i,j位置是true,就说明是回文
                if(dp[i][j]==true&&j-i+1>len){
                    //随时更新开始值和最长长度
                    len=j-i+1;
                    begin=i;
                }
            }
        }
        return s.substring(begin,begin+len);
    }

更加优秀的算法:中心扩展算法

以每个点作为中心去计算他的回文数。

class Solution {
    public String longestPalindrome(String s) {
        //中心拓展算法
        int n=s.length();
        char[]a=s.toCharArray();
        String c="";
        int max=0;
        for(int i=0;i<n;i++){
            int left=i-1;
            int right=i+1;
            while(left>=0&&right<n){
                if(a[left]==a[right]){
                    left--;
                    right++; 
                }else{
                    break;
                }
            }
            
            if(right-left-1>max){
                c=s.substring(left+1,right);
                max=right-left-1;

            }
            left=i;
            right=i+1;
             while(left>=0&&right<n){
                if(a[left]==a[right]){
                    left--;
                    right++; 
                }else{
                    break;
                }
            }
           
            if(right-left-1>max){
                c=s.substring(left+1,right);
                max=right-left-1;
            }
        }
            return c;
    }
}

差距不大，算法一致，快了10ms差不多

class Solution {
    public String longestPalindrome(String s) {
        //中心拓展算法
        int n=s.length();
        char[]a=s.toCharArray();
        String c="";
        int max=0;
        for(int i=0;i<n;i++){
            int left=i-1;
            int right=i+1;
            //我直接 aba 这种
            while(left>=0&&right<n){
                //两个相等就不变指针
                if(a[left]==a[right]){
                    left--;
                    right++; 
                }else{
                    //不等就退出循环
                    break;
                }
            }
            //因为出来的话俩个都是不等，所以   kabac   left=k    right=c 你减一下
            if(right-left-1>max){
                c=s.substring(left+1,right);
                max=right-left-1;
            }
            //aa这种
            left=i;
            right=i+1;
             while(left>=0&&right<n){
                if(a[left]==a[right]){
                    left--;
                    right++; 
                }else{
                    break;
                }
            }
           
            if(right-left-1>max){
                c=s.substring(left+1,right);
                max=right-left-1;
            }
        }
            return c;
    }
}