做网站如何安全 博客,设计外贸网站,新的网站做淘宝客,关于电商平台目录
三、打家劫舍
LeetCode198#xff1a;打家劫舍
LeetCode213#xff1a;打家劫舍ii
LeetCode337#xff1a;打家劫舍iii#xff08;树形#xff09;
四、股票问题
时间不多了#xff0c;其他的先不写了
LeetCode121#xff1a;买卖股票的最佳时机
五、子序列…目录
三、打家劫舍
LeetCode198打家劫舍
LeetCode213打家劫舍ii
LeetCode337打家劫舍iii树形
四、股票问题
时间不多了其他的先不写了
LeetCode121买卖股票的最佳时机
五、子序列问题
5.1 子序列不连续
LeetCode300最长递增子序列不连续 LeetCode1143最长公共子序列不连续但有相对顺序
LeetCode1035不相交的线不连续但有相对顺序
5.2 子序列连续
LeetCode674最长连续递增子序列 LeetCode718最长重复子数组连续无顺序 LeetCode53最大子序和
LeetCode2乘积最大子数组和
5.3 编辑距离
LeetCode392判断子序列
LeetCode115不同的子序列
LeetCode583两个字符串的删除操作
LeetCode72编辑距离 5.4 回文问题
LeetCode647回文子串
LeetCode516最长回文子序列 三、打家劫舍
LeetCode198打家劫舍
相邻房屋被偷报警不触动警报装置的情况下能偷到的最高金额
思路当前状态和前面状态会有一种依赖关系那么这种依赖关系都是动规的递推公式。
dp[i]考虑下标i包括i以内的房屋最多可以偷窃的金额为dp[i]。递推公式如果偷第i房间那么dp[i] dp[i - 2] nums[i] 即第i-1房一定是不考虑的找出 下标i-2包括i-2以内的房屋最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。 如果不偷第i房间那么dp[i] dp[i - 1]即考虑i-1房。然后dp[i]取最大值即 dp[i] max(dp[i - 2] nums[i], dp[i - 1]); 初始化从递推公式可以看出递推的基础是dp[0]nums[0]dp[1]max(dp[0],dp[1]))
class Solution {public int rob(int[] nums) {if (nums null || nums.length 0) return 0;if (nums.length 1) return nums[0];int[] dp new int[nums.length];dp[0] nums[0];dp[1] Math.max(nums[0],nums[1]);for(int i2;inums.length;i){dp[i] Math.max(dp[i-1],dp[i-2]nums[i]);}return dp[nums.length-1];}
} LeetCode213打家劫舍ii
思路为了不使他成环考虑首元素不包含尾元素和尾元素不包含首元素两种情况。
class Solution {public int rob(int[] nums) {if (nums null || nums.length 0)return 0;int len nums.length;if (len 1)return nums[0];return Math.max(robAction(nums, 0, len - 1), robAction(nums, 1, len));}int robAction(int[] nums, int start, int end) {int x 0, y 0, z 0;for (int i start; i end; i) {y z;z Math.max(y, x nums[i]);x y;}return z;}
} LeetCode337打家劫舍iii树形
思路关键在于该节点是抢还是不抢。如果抢了当前节点两个孩子就不能动如果没抢当前节点就可以考虑抢左右孩子注意这里说的是“考虑”
树形dp返回长度为2的数组dp数组dp table以及下标的含义下标为0记录不偷该节点所得到的的最大金钱下标为1记录偷该节点所得到的的最大金钱
终止条件遍历到空节点遍历顺序显然是左右中后序遍历因为需要处理返回值
单层递归逻辑如果是偷当前节点那么左右孩子就不能偷如果不偷当前节点那么左右孩子就都可以偷至于到底偷不偷一定是选最大的相加
最终头结点就是 取下标0 和 下标1的最大值就是偷得的最大金钱。
class Solution {public int rob(TreeNode root) {int[] res new int[2];res robAction(root);return Math.max(res[0],res[1]);}public int[] robAction(TreeNode root){int[] res new int[2];if(rootnull) return res;int[] left robAction(root.left);int[] right robAction(root.right);//不偷当前节点偷左右孩子res[0] Math.max(left[0],left[1]) Math.max(right[0],right[1]);//偷当前节点不偷左右孩子res[1] root.val left[0] right[0];return res;}
} 四、股票问题
时间不多了其他的先不写了
LeetCode121买卖股票的最佳时机
首先贪心解法每次在最低点购入然后最高点抛出
class Solution {public int maxProfit(int[] prices) {// 找到一个最小的购入点int low Integer.MAX_VALUE;// res不断更新直到数组循环完毕int res 0;for(int i 0; i prices.length; i){low Math.min(prices[i], low);res Math.max(prices[i] - low, res);}return res;}
}
其次 动态规划使用一个二维dp数组dp[i][0]代表第i天持有股票所得现金dp[i][1]代表不持有
● 推导公式分为两种情况如果第i天持有股票则来源于两种情况1. 第i-1天就持有股票则所得现金不变2. 第i天买入股票所得现金为-prices[i]。如果第i天不持有股票则来源于两种情况1. 第i-1天就持有股票则卖出股票所得现金为prices[i]2. 第i天不持有股票所得现金不变
dp[i][0] max(dp[i - 1][0], -prices[i]); 和 dp[i][1] max(dp[i - 1][1], prices[i] dp[i - 1][0]);
● 初始化第0天持有股票则一定是买入股票dp[0][0] -prices[0]第0天不持有则dp[0][1]0
结果就是dp[prices.length-1][1]因为本题中不持有股票状态所得金钱一定比持有股票状态得到的多
class Solution {public int maxProfit(int[] prices) {if (prices null || prices.length 0) return 0;int length prices.length;// dp[i][0]代表第i天持有股票的最大收益// dp[i][1]代表第i天不持有股票的最大收益int[][] dp new int[length][2];int result 0;dp[0][0] -prices[0];dp[0][1] 0;for (int i 1; i length; i) {dp[i][0] Math.max(dp[i - 1][0], -prices[i]);dp[i][1] Math.max(dp[i - 1][0] prices[i], dp[i - 1][1]);}return dp[length - 1][1];}
} 五、子序列问题
子序列问题是动态规划解决的经典问题当前下标i的递增子序列长度其实和i之前的下表j的子序列长度有关系
5.1 子序列不连续
LeetCode300最长递增子序列不连续
思路dp[i]表示以nums[i]为结尾的最长递增子序列的长度。初始化都是1。
递推公式dp[i]等于j从0-i的最大升序列1
class Solution {public int lengthOfLIS(int[] nums) {int[] dp new int[nums.length];int res 1;//每个递增子序列的大小都最起码是1因为最少包含nums[i]Arrays.fill(dp, 1);for (int i 1; i dp.length; i) {//j会遍历0-i-1的每一个值来进行比较并更新dp[i]因此要和dp[i]本身取最大值//每次遍历如果是递增的就1不用连续递增不然就保持不变for (int j 0; j i; j) {if (nums[i] nums[j]) {dp[i] Math.max(dp[i], dp[j] 1);}}//然后也是取所有dp[i]里面最长的一个子序列res Math.max(res, dp[i]);}return res;}
} LeetCode1143最长公共子序列不连续但有相对顺序
思路1. dp[i][j]长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]; 取dp[len1][len2]2. 不同于最长重复子数组的定义如果相等就1如果不相等就还是为0在这里如果相等就1如果不相等则取text1[0,i-2]和text2[0,j-1]的最长公共子序列和text1[0,i-1]和text2[0,j-2]的最大值,即dp[i][j] max(dp[i - 1][j], dp[i][j - 1])3. 根据定义初始化为0
class Solution {public int longestCommonSubsequence(String text1, String text2) {int[][] dp new int[text1.length()1][text2.length()1];for(int i1;itext1.length();i){char char1 text1.charAt(i-1);for(int j1;jtext2.length();j){char char2 text2.charAt(j-1);if(char1 char2){dp[i][j] dp[i-1][j-1] 1;}else{dp[i][j] Math.max(dp[i][j-1], dp[i-1][j]);}}}return dp[text1.length()][text2.length()];}
}
一维dp由于用pre记录了上一个值所以不会出现重复叠加所以第二个循环j不用倒序
class Solution {public int longestCommonSubsequence(String text1, String text2) {int[] dp new int[text2.length()1];for(int i1;itext1.length();i){int pre dp[0];char char1 text1.charAt(i-1);for(int j1;jtext2.length();j){int cur dp[j];char char2 text2.charAt(j-1);if(char1 char2){dp[j] pre 1;}else{dp[j] Math.max(dp[j-1], dp[j]);}pre cur;}}return dp[text2.length()];}
} LeetCode1035不相交的线不连续但有相对顺序
思路其实问有几条不相交的线就是在字符串A中找到一个和字符串B相同的子序列不能改变相对顺序求子序列的长度。
本题说是求绘制的最大连线数其实就是求两个字符串的最长公共子序列的长度
基本上copy上一题代码即可ac
class Solution {public int maxUncrossedLines(int[] nums1, int[] nums2) {int[][] dp new int[nums1.length1][nums2.length1];for(int i1;inums1.length;i){for(int j1;jnums2.length;j){if(nums1[i-1] nums2[j-1]){dp[i][j] dp[i-1][j-1] 1;}else{dp[i][j] Math.max(dp[i][j-1], dp[i-1][j]);}}}return dp[nums1.length][nums2.length];}
} 5.2 子序列连续
LeetCode674最长连续递增子序列
思路因为本题要求连续递增子序列所以就只要比较nums[i]与nums[i - 1]而不用去比较nums[j]与nums[i] j是在0到i之间遍历。既然不用j了那么也不用两层for循环本题一层for循环就行比较nums[i] 和 nums[i - 1]。
class Solution {public int findLengthOfLCIS(int[] nums) {int[] dp new int[nums.length];int res 1;//每个递增子序列的大小都最起码是1因为最少包含nums[i]Arrays.fill(dp, 1);for (int i 1; i dp.length; i) {if(nums[i] nums[i-1]){dp[i] dp[i-1] 1;}//然后也是取所有dp[i]里面最长的一个子序列res Math.max(res, dp[i]);}return res;}
} LeetCode718最长重复子数组连续无顺序
给两个整数数组 A 和 B 返回两个数组中公共的、长度最长的子数组的长度。取最大res。
题目中说子数组其实就是连续子序列。
思路二维dp。动规五部曲——1. dp[i][j]代表以i-1为结尾的A和以j-1为结尾的B的最长重复子数组的长度记得数组的大小为nums.length1因为是从1开始的2. 递推公式当A[i - 1] 和B[j - 1]相等的时候dp[i][j] dp[i - 1][j - 1] 1;根据递推公式可以看出遍历i 和 j 要从1开始3. 初始化举例dp[1][1]dp[0][0]1则dp[0][0]0才能进行接下来的推导4. 遍历顺序和举例推导省略不提
为什么使用i-1下标作为判断而不使用i下标呢这是由于使用i-1可以直接从下标1开始进行判断更新dp数组而如果使用i就需要考虑到下标0的A和下标i的B相等的情况需要先对第一行/第一列进行初始化后再进行for循环多了一些步骤不够简洁
class Solution {public int findLength(int[] nums1, int[] nums2) {int res 0;int[][] dp new int[nums1.length1][nums2.length1];for(int i1;inums1.length1;i){for(int j1;jnums2.length1;j){if(nums1[i-1] nums2[j-1]){dp[i][j] dp[i-1][j-1] 1;res Math.max(res, dp[i][j]);}}}return res;}
}
一维dp滚动数组 重点在于不相等的时候记得给dp[j]赋0
class Solution {public int findLength(int[] nums1, int[] nums2) {int res 0;int[] dp new int[nums2.length1];for(int i1;inums1.length1;i){for(int jnums2.length;j0;j--){if(nums1[i-1] nums2[j-1]){dp[j] dp[j-1] 1;}else{ //当不相等时说明没有以i-1和j-1为最后一个元素的最长公共子数组所以为0dp[j] 0;}res Math.max(res, dp[j]);}}return res;}
} LeetCode53最大子序和
思路贪心的思路就是如果当前“连续和”为负数的时候立刻放弃从下一个元素重新计算“连续和”因为负数加上下一个元素 “连续和”只会越来越小。
照例我们通过动规五部曲来分析一下 dp定义dp[i]即包含nums[i]的最大子序和 递推公式dp[i]来源于两个方向一个是dp[i-1]nums[i]nums[i]加入当前子序和另一个是放弃之前的子序和重新开始计算连续子序和。dp[i] Math.max(dp[i - 1] nums[i], nums[i])也可以写成dp[i] dp[i - 1]0? nums[i] :dp[i-1] nums[i]; 初始化dp[0]nums[0] class Solution {public int maxSubArray(int[] nums) {if (nums.length 0) {return 0;}int res nums[0];int[] dp new int[nums.length];dp[0] nums[0];for (int i 1; i nums.length; i) {dp[i] Math.max(dp[i - 1] nums[i], nums[i]);res Math.max(res, dp[i]);}return res;}
}
类似的
LeetCode2乘积最大子数组和
class Solution {public int maxProduct(int[] nums) {int[] dp new int[nums.length]; //0-i个数获得最大的成绩int res nums[0];dp[0] nums[0];for(int i1; inums.length;i){dp[i] Math.max(dp[i-1]*nums[i], nums[i]);res Math.max(res, dp[i]);}return res;}
} 5.3 编辑距离
LeetCode392判断子序列
给定字符串 s 和 t 判断 s 是否为 t 的子序列。字符串的一个子序列是原始字符串删除一些也可以不删除字符而不改变剩余字符相对位置形成的新字符串。例如ace是abcde的一个子序列而aec不是。 思路类似1143 最长公共子序列区别在于1143是s、t都可以删去元素本题只删去字符串t里的 dp[i][j]指的是以i-1为结尾的字符串s和j-1为结尾的字符串t的相同子序列长度 如果s[i-1] t[j-1]则长度1——dp[i][j] dp[i - 1][j - 1] 1; 如果不相等相当于删去t[j-1]就长度不变——dp[i][j] dp[i][j - 1] 是否是子序列即dp[len1][len2] 是否 len1 class Solution {public boolean isSubsequence(String s, String t) {int length1 s.length(); int length2 t.length();int[][] dp new int[length11][length21];for(int i 1; i length1; i){for(int j 1; j length2; j){if(s.charAt(i-1) t.charAt(j-1)){dp[i][j] dp[i-1][j-1] 1;}else{dp[i][j] dp[i][j-1];}}}if(dp[length1][length2] length1){return true;}else{return false;}}
}
//压缩成一维dp
class Solution {public boolean isSubsequence(String s, String t) {int[] dp new int[s.length() 1];for (int i 1; i t.length(); i ) {// 需要使用上一轮的dp[j - 1]所以使用倒序遍历for (int j s.length(); j 0; j --) {if (t.charAt(i-1) s.charAt(j - 1)) {dp[j] dp[j - 1] 1;}}}return dp[s.length()] s.length();}
} LeetCode115不同的子序列
思路我们求的是 s 中有多少个 t而不是 求t中有多少个s所以只考虑 s中删除元素的情况即 不用s[i - 1]来匹配 的情况。相当于s中删除元素得到t有多少种方案
dp[i][j]以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。
递推公式
class Solution {public int numDistinct(String s, String t) {//以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]int[][] dp new int[s.length() 1][t.length() 1];//初始化dp[i][0]——以i-1为结尾的s可以随便删除元素出现空字符串的方案个数1删除全部元素//dp[0][j]空字符串s可以随便删除元素出现以j-1为结尾的字符串t的个数0for (int i 0; i s.length() 1; i) {dp[i][0] 1;}for (int i 1; i s.length() 1; i) {for (int j 1; j t.length() 1; j) {//相等包括用s[i-1]来匹配和不用s[i-1]来匹配已经存在的方案个数if (s.charAt(i - 1) t.charAt(j - 1)) {dp[i][j] dp[i - 1][j - 1] dp[i - 1][j];}else{ //不相等删除s字符串中的s[i-1]dp[i][j] dp[i - 1][j];}}}return dp[s.length()][t.length()];}
} LeetCode583两个字符串的删除操作
找到使得 word1 和 word2 相同所需的最小步数每步可以删除任意一个字符串中的一个字符。
思路1相比于115两个字符串都可以删除 dp[i][j]以i-1为结尾的字符串word1和以j-1位结尾的字符串word2想要达到相等所需要删除元素的最少次数。 递推当word1[i - 1] word2[j - 1]时继承上一个循环的dp不变——dp[i][j] dp[i - 1][j - 1]; 当word1[i - 1] 不等于 word2[j - 1]时包含三种情况删除word1[i-1]删除word2[j - 1]和同时删word1[i - 1]和word2[j - 1]即dp[i][j] min({dp[i - 1][j - 1] 2, dp[i - 1][j] 1, dp[i][j - 1] 1}); 因为 dp[i][j - 1] 1 dp[i - 1][j - 1] 2所以递推公式可简化为dp[i][j] min(dp[i - 1][j] 1, dp[i][j - 1] 1);只需考虑这两种情况 class Solution {public int minDistance(String word1, String word2) {int[][] dp new int[word1.length() 1][word2.length() 1];for (int i 0; i word1.length() 1; i) dp[i][0] i;for (int j 0; j word2.length() 1; j) dp[0][j] j;for (int i 1; i word1.length() 1; i) {for (int j 1; j word2.length() 1; j) {if (word1.charAt(i - 1) word2.charAt(j - 1)) {dp[i][j] dp[i - 1][j - 1];}else{dp[i][j] Math.min(dp[i - 1][j - 1] 2,Math.min(dp[i - 1][j] 1, dp[i][j - 1] 1));}}}return dp[word1.length()][word2.length()];}
} 思路2只要求出两个字符串的最长公共子序列长度即可那么除了最长公共子序列之外的字符都是必须删除的
lass Solution {public int minDistance(String word1, String word2) {int len1 word1.length();int len2 word2.length();int[][] dp new int[len1 1][len2 1];for (int i 1; i len1; i) {for (int j 1; j len2; j) {if (word1.charAt(i - 1) word2.charAt(j - 1)) {dp[i][j] dp[i - 1][j - 1] 1;} else {dp[i][j] Math.max(dp[i - 1][j], dp[i][j - 1]);}}}return len1 len2 - dp[len1][len2] * 2;}
} LeetCode72编辑距离
可以插入、删除、替换一个字符计算出将 word1 转换成 word2 所使用的最少操作数 。
思路dp[i][j] 表示以下标i-1为结尾的字符串word1和以下标j-1为结尾的字符串word2最近编辑距离为dp[i][j]。
递推公式
if (word1[i - 1] word2[j - 1])不操作 dp[i][j] dp[i - 1][j - 1];
if (word1[i - 1] ! word2[j - 1])增 word2加一个相当于word1减一个删 word1删一个dp[i][j] dp[i - 1][j] 1;word2删一个dp[i][j] dp[i][j - 1] 1;换 dp[i][j] dp[i - 1][j - 1] 1;所以总结就是 dp[i][j] min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) 1;选操作步骤最少的一个
初始化
dp[i][0] 以下标i-1为结尾的字符串word1和空字符串word2最近编辑距离为dp[i][0]。
那么dp[i][0]就应该是i对word1里的元素全部做删除操作即dp[i][0] i;同理dp[0][j] j;
for (int i 0; i word1.size(); i) dp[i][0] i;
for (int j 0; j word2.size(); j) dp[0][j] j; 代码
class Solution {public int minDistance(String word1, String word2) {int m word1.length();int n word2.length();int[][] dp new int[m1][n1];for(int i0;im;i) dp[i][0] i;for(int j0;jn;j) dp[0][j] j;for(int i1;im;i){for(int j1;jn;j){if(word1.charAt(i-1) word2.charAt(j-1)){dp[i][j] dp[i-1][j-1];}else{dp[i][j] Math.min(dp[i-1][j-1],Math.min(dp[i][j-1], dp[i-1][j])) 1;}}}return dp[m][n];}
} 5.4 回文问题
LeetCode647回文子串
给定一个字符串你的任务是计算这个字符串中有多少个回文子串。具有不同开始位置或结束位置的子串即使是由相同的字符组成也会被视作不同的子串。
思路如何递推呢我们在判断字符串S是否是回文那么如果我们知道 s[1]s[2]s[3] 这个子串是回文的那么只需要比较 s[0]和s[4]这两个元素是否相同如果相同的话这个字符串s 就是回文串。
所以定义bool类型的dp数组表示[i,j]子串是否是回文串
当s[i]!s[j]时 dp[i][j] false;
s[i]s[j]时是否是回文串要看子串的大小即i、j的差值1. 如果相同则true 2. 如果相差一也是 。 如果相差大于1则需要判断dp[i1][j-1]是否是回文串。
if (s[i] s[j]) {if (j - i 1) { // 情况一 和 情况二result;dp[i][j] true;} else if (dp[i 1][j - 1]) { // 情况三result;dp[i][j] true;}
}
初始化为false遍历顺序从下到上从左到右 class Solution {public int countSubstrings(String s) {char[] chars s.toCharArray();int len chars.length;boolean[][] dp new boolean[len][len];int result 0;for (int i len - 1; i 0; i--) {for (int j i; j len; j) {if (chars[i] chars[j]) {if (j - i 1) { // 情况一 和 情况二result;dp[i][j] true;} else if (dp[i 1][j - 1]) { //情况三result;dp[i][j] true;}}}}return result;}
} LeetCode516最长回文子序列
思路注意区分回文子串和回文子序列回文子串是要连续的回文子序列可不是连续的
dp[i][j]【i,j】范围内的最长回文子串
递推如果s[i]与s[j]相同那么dp[i][j] dp[i 1][j - 1] 2;如果s[i]与s[j]不相同说明s[i]和s[j]的同时加入 并不能增加[i,j]区间回文子序列的长度那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。dp[i][j] max(dp[i 1][j], dp[i][j - 1]);可以看出遍历还是从下到上从左到右
初始化dp[i][i] 1
public class Solution {public int longestPalindromeSubseq(String s) {int len s.length();int[][] dp new int[len 1][len 1];for (int i len - 1; i 0; i--) { // 从后往前遍历 保证情况不漏dp[i][i] 1; // 初始化for (int j i 1; j len; j) {if (s.charAt(i) s.charAt(j)) {dp[i][j] dp[i 1][j - 1] 2;} else {dp[i][j] Math.max(dp[i 1][j], dp[i][j - 1]);}}}return dp[0][len - 1];}
}
