class Solution { // 找某个元素的右边的元素的最大值，作差，比较差的大小,暴力法会超时 // 对于某一个具体的日子，在当天卖出股票所能获得的最大值，是当前的股票价格减去之前出现过的最小值 // 求整个过程的最大值 public int maxProfit(int[] prices) { int max = 0; int min = Integer.MAX_VALUE; for (int i = 0; i < prices.length; i++) { if (prices[i] < min) { min = prices[i]; } if (prices[i] - min > max) { max = prices[i] - min; } } return max; } }
Interview-Notes
class Solution { //动态规划 dp[]代表前i个字符能否由List里的字符串组成 //初始化dp[0] = 0; //遍历顺序：从左到右 //递推公式 //s.substring(start,endIndex) start是起始索引，endIndex是结束索引，不包括 // 排列而不是组合 public boolean wordBreak(String s, List<String> wordDict) { int n = s.length(); boolean[] dp = new boolean[s.length() + 1]; //代表s的前i个元素能否由字典中的元素组成 dp[0] = true; for (int i = 1; i <= n; i++) { for (String str : wordDict) { if (i >= str.length() && dp [i - str.length()] && s.substring(i - str.length(), i).equals(str)) { dp[i] = true; } } } return dp[n]; } }
class Solution { // 两种方法： 方法一:用两个变量，记录以某个索引为末尾的子数组的最大乘积和最小乘积 // 遍历 // 方法二：dpMax[i], dpMin[i]维护两个动态规划数组，一个用来记录最大值，一个用来记录最小值 public int maxProduct(int[] nums) { // int min = nums[0]; // int max = nums[0]; // 当前索引位置的乘积最大值 // int res = nums[0]; // 当前所有位置的乘积最小值 // for (int i = 1; i < nums.length; i++) { // if (nums[i] < 0) { // 如果nums[i] < 0 交换最大最小值 // int temp = max; // max = min; // min = temp; // } // max = Math.max(nums[i], nums[i]*max); // min = Math.min(nums[i], nums[i]* min); // res = Math.max(res,max); // } // return res; int n = nums.length; int[] dpMax = new int[n]; int[] dpMin = new int[n]; int res = nums[0]; dpMax[0] = nums[0];dpMin[0] = nums[0]; for (int i = 1; i < n; i++) { dpMax[i] = Math.max(nums[i],Math.max(nums[i]*dpMax[i-1],nums[i]*dpMin[i-1])); dpMin[i] = Math.min(nums[i], Math.min(nums[i] * dpMax[i-1],nums[i]*dpMin[i-1])); res = Math.max(res, dpMax[i]); } return res; } }
dp class Solution { //动态规划4步：1.确定dp数组及下标的含义 // 2.确定递推公式 // 3.dp数组如何初始化 // 4.确定遍历顺序 // 偷窃当前房屋，不偷窃当前房屋 // dp[i] 代表从0-i间房偷窃获得的最大值是多少 // dp[i] = Math.max(dp[i-1], dp[i-2] +nums[i]); // dp[0] = nums[0], dp[1] = Math.max(nums[1], nums[0]); // public int rob(int[] nums) { int n = nums.length; if (n == 1) { return nums[0]; } else if (n == 2) { return Math.max(nums[0], nums[1]); } int[] dp = new int[n]; dp[0] = nums[0]; dp[1] = Math.max(nums[0], nums[1]); for (int i = 2; i < n; i++) { dp[i] = Math.max(dp[i-1], dp[i - 2] + nums[i]); //对于每到一下个房间有两种可能，1.偷当前房间， 2.不偷当前房间 } return dp[n-1]; } } dfs+递归 class Solution { public int rob(int[] nums) { int n = nums.length; Integer[] memo = new Integer[n]; // 记忆化数组 return dfs(nums, 0, memo); } private int dfs(int[] nums, int i, Integer[] memo) { if (i >= nums.length) return 0; //超出边介 if (memo[i] != null) return memo[i]; // 偷当前房子 int take = nums[i] + dfs(nums, i + 2, memo); // 不偷当前房子 int notTake = dfs(nums, i + 1, memo); memo[i] = Math.max(take, notTake); return memo[i]; } }
class Solution { // 动态规划： dp[i][j]代表以nums[i][j] 为右下角能得到的正方形的最大值 // 递推公式： dp[i][j] = Math.min(dp[i-1][j], dp[i][j - 1], dp[i - 1][j - 1]) // 初始化 对i==0 || j==0的情况进行初始化 // 遍历顺序 从左到右，从上到下 public int maximalSquare(char[][] matrix) { int m = matrix.length; int n = matrix[0].length; int[][] dp = new int[m][n]; int maxSide = 0; for (int i = 0; i < m; i++) { if (matrix[i][0] == '1') { dp[i][0] = 1; maxSide = 1; } } for (int j = 0; j < n; j++) { if (matrix[0][j] == '1') { dp[0][j] = 1; maxSide = 1; } } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (matrix[i][j] == '1') { dp[i][j] = Math.min(dp[i - 1][j],Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1; maxSide = Math.max(maxSide, dp[i][j]); } } } return maxSide*maxSide; } }
class Solution { // 题目要求o(n)的时间复杂度 // 题目类型dp public int[] productExceptSelf(int[] nums) { //除nums[i]之外的所有数的乘积也就是将nums[i]当做1 // 可以计算这个数左乘积和右乘积 // 用三个数组分别存储前缀、后缀和乘积 // 对于元素nums[0]，我们设定初始值left[0] = 1; // 对于元素nums[nums.length - 1] 设定初始值right[nums.length - 1] = 1; int n = nums.length; int[] left = new int[n]; int[] right = new int[n]; int[] res = new int[n]; left[0] = 1;right[n - 1] = 1; for (int i = 1; i < n; i++) { left[i] = left[i-1] * nums[i-1]; } for (int j = n - 2; j >= 0; j--) { right[j] = right[j + 1] * nums[j + 1]; } for (int i = 0; i < n; i++) { res[i] = left[i] * right[i]; } return res; } }
class Solution { //dp[]数组代表和为n的完全平方数的最少数量 //递推公式 // dp[i] = Math.min(dp[i],dp[i-j*j] + 1) for all j*j <= i; // 完全背包 public int numSquares(int n) { // int[] dp = new int[n+1]; // dp[0] = 0; // for(int i = 1; i <= n; i++) { // int min = n; // for(int j = 1;j*j <= i; j++) { // min = Math.min(min,dp[i-j*j]); // } // dp[i] = min + 1; // } // return dp[n]; int[] dp = new int[n + 1]; Arrays.fill(dp,10001); dp[0] = 0; //dp[j] = Math.min(dp[j],dp[j-i*i] + 1); for (int i = 1; i*i<= n; i++) { for (int j = i*i; j <= n; j++) { dp[j] = Math.min(dp[j],dp[j- i*i] + 1); } } return dp[n]; } }
class Solution { // dp[i] 表示到以元素i结尾的的最长递增子序列的长度 public int lengthOfLIS(int[] nums) { int[] dp = new int[nums.length]; Arrays.fill(dp,1); for (int i = 1; i < nums.length; i++) { for (int j = 0; j < i; j++) { if (nums[i] > nums[j]) { dp[i] = Math.max(dp[i],dp[j] + 1); } } } int max = 0; for (int i = 0; i < nums.length; i++) { max = Math.max(dp[i],max); } return max; } }
class Solution { //动态规划 //动态规划四部曲：确定dp[]数组及下标对应的含义，递推公式、初始化、遍历顺序 // 三种状态： 持有股票，不持有股票并且处于冷冻期，不持有股票并且不处于冷冻期对应dp[i][0],dp[i][1],dp[i][2]; // 递推公式：dp[i][0] = dp[i-1][2] - prices[0]; // dp[i][1] = dp[i][0] + prices[i] dp[i][2] = dp[i-1][1]; public int maxProfit(int[] prices) { int n = prices.length; int[][] dp = new int[n][3]; dp[0][0] = -prices[0]; dp[0][1] = 0; dp[0][2] = 0; for (int i = 1; i < prices.length; i++) { dp[i][0] = Math.max(dp[i-1][0], dp[i-1][2] - prices[i]); dp[i][1] = dp[i-1][0] + prices[i]; dp[i][2] = Math.max(dp[i-1][2], dp[i-1][1]); } return Math.max(dp[n-1][1],dp[n-1][2]); } }
class Solution { // dp[i][j] 代表戳i到j之间内的气球能获得的硬币最大值 // 递推公式：dp[i][j] = Math.max (dp[i][k] + dp[k][j] + val[i]*val[j]*val[k], dp[i][j]) // k代表最后一次戳的气球 public int maxCoins(int[] nums) { int n = nums.length; int[][] dp = new int[n + 2][n + 2]; int[] val = new int[n + 2]; val[0] = val[n + 1] = 1; for (int i = 1; i <= n; i++) { val[i] = nums[i - 1]; } for (int len = 1; len <= n; len++) { // 可以戳的气球数量 for (int i = 1; i <= n - len + 1; i++) { // 可以戳的起点 int j = i + len - 1; // 终点 for (int k = i; k <= j; k++) { // 最后一个戳的气球 dp[i][j] = Math.max (dp[i][k-1] + dp[k + 1][j] + val[i-1]*val[j+1]*val[k], dp[i][j]); } } } return dp[1][n]; } }