1.剑指offer47 --礼物的最大价值
class Solution { public int maxValue(int[][] grid) { int m = grid.length, n = grid[0].length; int[][] dp = new int[m+1][n+1]; for(int i = 0;i<=m;i++){ dp[i][0] = 0; } for(int j = 0;j<=n;j++){ dp[0][j] = 0; } for(int i = 1;i<=m;i++){ for(int j = 1;j<=n;j++){ dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1]; } } return dp[m][n]; } }
2.剑指offer48--最长不含重复字符的子字符串
class Solution { public int lengthOfLongestSubstring(String s) { HashSet<Character> set= new HashSet<>(); int n = s.length(); int res = 0; for(int i = 0, j = 0;j<n;j++){ while(!set.isEmpty()&&set.contains(s.charAt(j))){ set.remove(s.charAt(i)); i++; } set.add(s.charAt(j)); //System.out.println(set.size()); res = Math.max(res,set.size()); } return res; } }
3.剑指offer60--n个骰子的点数
class Solution { //该题直接用深度优先遍历,时间复杂度是6的n次方,可以用动态规划来优化 //假设有四个骰子,当想要遍历到和为4与6时 //计算和为4,可以计算前三个和为1,2,3 //计算和为6,也需要计算前三个和为1,2,3 //所以可以用动态规划的最优子结构来优化 public double[] dicesProbability(int n) { int[][] dp = new int[12][70]; for(int i = 1;i<=6;i++){ dp[1][i] = 1; } for(int i = 2;i<=n;i++){ for(int j = i;j<=6*i;j++){ for(int k = 1;k<=6;k++){ if(j-k<0){ break; } dp[i][j] += dp[i-1][j-k]; } } } int cnt = 0; for(int i = n;i<=6*n;i++){ cnt += dp[n][i]; } double[] res = new double[5*n+1]; for(int i = n;i<=6*n;i++){ res[i-n] = dp[n][i]/(cnt*1.0); } return res; } }
4.剑指offer63--股票的最大利润
class Solution { public int maxProfit(int[] prices) { int min = 0x3f3f3f3f, n = prices.length,res = 0; for(int i = 0;i<n;i++){ min = Math.min(min,prices[i]); res =Math.max(res,prices[i] - min); //System.out.println(res); } return res; } }
标签:--,Solution,class,2023.3,int,算法,length,public From: https://www.cnblogs.com/lyjps/p/17168170.html