力扣面试150题--三角形最小路径和 最小路径和 不同路径 最长回文子串

Day 98

题目描述

思路

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
       if(triangle.size()==1){
            return triangle.get(0).get(0);
        }
        int[]dp1=new int[triangle.get(triangle.size()-1).size()];
        int[]dp2=new int[triangle.get(triangle.size()-1).size()];
        dp1[0]=triangle.get(0).get(0);
        for (int i=1;i<triangle.size();i++){
            for (int j = 0; j < triangle.get(i).size(); j++) {
                if(j==0){
                    dp2[j]=dp1[j]+triangle.get(i).get(j);
                }
                else if(j==triangle.get(i).size()-1){
                    dp2[j]=dp1[j-1]+triangle.get(i).get(j);
                    dp1[j-1]=dp2[j-1];
                    dp1[j]=dp2[j];
                }
                else{
                    int a,b;
                    a=dp1[j]+triangle.get(i).get(j);
                    b=dp1[j-1]+triangle.get(i).get(j);
                    dp2[j]=Math.min(a,b);
                    dp1[j-1]=dp2[j-1];
                }
            }
        }
        int min=1000000;
        for (int i=0;i<triangle.get(triangle.size()-1).size();i++){
            if(dp2[i]<min){
                min=dp2[i];
            }
        }
        return min;
    }
}

题目描述

思路

class Solution {
    public int minPathSum(int[][] grid) {
         int m=grid.length;
        int n=grid[0].length;
        if(m==1 && n==1){
            return grid[0][0];
        }
        if(n>1){
            for(int i=1;i<n;i++){
                grid[0][i]+=grid[0][i-1];
            }
        }
        if(m>1){
            for(int i=1;i<m;i++){
                grid[i][0]+=grid[i-1][0];
            }
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                grid[i][j]=Math.min(grid[i][j]+grid[i-1][j],grid[i][j-1]+grid[i][j]);
            }
        }
        return grid[m-1][n-1];
    }
}

题目描述

思路

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
          //初始化 将障碍改成-1
        for (int i = 0; i < obstacleGrid.length; i++) {
            for (int j = 0; j < obstacleGrid[i].length; j++) {
                if (obstacleGrid[i][j] == 1) {
                    obstacleGrid[i][j] = -1;
                }
            }
        }
        int count = 1;
        for (int i = 0; i < obstacleGrid.length; i++) {
            if (obstacleGrid[i][0] == -1) {
                count=-1;
            }
            obstacleGrid[i][0] = count;
        }
        count=1;
        for (int i = 0; i < obstacleGrid[0].length; i++) {
            if (obstacleGrid[0][i] == -1) {
                count=-1;
            }
            obstacleGrid[0][i] = count;
        }
        //计算
        for (int i = 1; i < obstacleGrid.length; i++) {
            for (int j = 1; j < obstacleGrid[i].length; j++) {
                if (obstacleGrid[i][j] == -1) {
                    continue;
                }
                int a,b;
                a=obstacleGrid[i-1][j];
                b=obstacleGrid[i][j-1];
                if(a!=-1&&b!=-1){
                    obstacleGrid[i][j]=a+b;
                }
                if (a==-1&&b!=-1){
                    obstacleGrid[i][j]=b;
                }
                if (a!=-1&&b==-1){
                    obstacleGrid[i][j]=a;
                }
                if(a==-1&&b==-1){
                    obstacleGrid[i][j]=-1;
                }
            }
        }
        if(obstacleGrid[obstacleGrid.length-1][obstacleGrid[0].length-1]==-1){
            obstacleGrid[obstacleGrid.length-1][obstacleGrid[0].length-1]=0;
        }
        return obstacleGrid[obstacleGrid.length-1][obstacleGrid[0].length-1];
    }
}

题目描述

思路

dp思路

class Solution {
    public String longestPalindrome(String s) {
          int n = s.length();
        // 处理空字符串或单字符的情况
        if (n < 2) {
            return s;
        }
        
        // dp[i][j] 表示 s[i..j] 是否为回文子串
        boolean[][] dp = new boolean[n][n];
        int maxLen = 1;  // 最长回文子串的长度
        int start = 0;   // 最长回文子串的起始索引
        
        // 初始化：单个字符都是回文子串
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }
        
        // 遍历所有可能的子串，按子串长度从小到大处理
        // j 表示子串的右端点
        for (int j = 1; j < n; j++) {
            // i 表示子串的左端点，i < j
            for (int i = 0; i < j; i++) {
                // 两端字符不相等，一定不是回文
                if (s.charAt(i) != s.charAt(j)) {
                    dp[i][j] = false;
                } else {
                    // 两端字符相等的情况
                    // 如果子串长度 <= 2（j - i <= 1），一定是回文
                    // 否则取决于中间子串 s[i+1..j-1] 是否为回文
                    if (j - i <= 1) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                
                // 更新最长回文子串的信息
                if (dp[i][j] && (j - i + 1) > maxLen) {
                    maxLen = j - i + 1;
                    start = i;
                }
            }
    }
    return s.substring(start, start + maxLen);
}
}