力扣面试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) {//初始化 将障碍改成-1for (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 < jfor (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);
}
}