旅游网站优化方案,免费加速器看国外网站,怎么创建自己网站平台,湖北省住房与城乡建设部网站300.最长递增子序列 完成 思路#xff1a;
本题dp[i]代表[0,i]数组的最长递增子序列#xff0c;一开始的想法也是两层for循环#xff0c;但总觉得这题不该这么烦。然后看了随想录的题解#xff0c;也是两层for循环#xff0c;所以有了想法就要去尝试。
本题初始化也是个…300.最长递增子序列 完成 思路
本题dp[i]代表[0,i]数组的最长递增子序列一开始的想法也是两层for循环但总觉得这题不该这么烦。然后看了随想录的题解也是两层for循环所以有了想法就要去尝试。
本题初始化也是个坑应该把dp数组初始化为1从语义上也很好理解因为无论数组元素如何排列最长递增子序列至少是1。另外如果初始化为0递推公式 dp[i] Math.max(dp[i], dp[j]1) 在取 dp[j]1 时如果 dp[j] 0结果也不对。
代码
class Solution {// dp[i] 表示[0,i]数组的最长递增子序列public int lengthOfLIS(int[] nums) {int[] dp new int[nums.length];Arrays.fill(dp, 1);int res 1;for (int i 1; i nums.length; i) { //遍历元素for (int j 0; j i; j) { // 计算dp[i]if(nums[i]nums[j]){// 和前面所有元素比较需要保留dp[i]本身的值取最大dp[i] Math.max(dp[i], dp[j]1);}// 取所有dp[i]的最大值res Math.max(res, dp[i]);}}return res;}
}674. 最长连续递增序列 完成 代码
贪心
class Solution {public int findLengthOfLCIS(int[] nums) {int res 1;int temp 1;for (int i 1; i nums.length; i) {if(nums[i]nums[i-1]){temp;}else{temp1;}res Math.max(res, temp);}return res;}
}动态规划
class Solution {public int findLengthOfLCIS(int[] nums) {int[] dp new int[nums.length];Arrays.fill(dp, 1);int res 1;for (int i 1; i dp.length; i) {if(nums[i]nums[i-1]) dp[i] dp[i-1]1;res Math.max(res, dp[i]);}return res;}
}718. 最长重复子数组 完成 思路
涉及到两个数组比较状态的保存一维dp就不够用了需要用到二维dp数组。
代码
dp[i][j] 代表 [0-i]的nums1数组和[0-j]的nums2数组的公共最长子数组的长度。
class Solution {// dp[i][j] 代表 [0-i]的nums1数组和[0-j]的nums2数组的公共最长子数组的长度public int findLength(int[] nums1, int[] nums2) {int[][] dp new int[nums1.length1][nums2.length1];int res 0;for (int i 0; i nums1.length; i) if (nums1[i] nums2[0]) dp[i][0] 1;for (int j 0; j nums2.length; j) if (nums1[0] nums2[j]) dp[0][j] 1;for (int i 0; i nums1.length; i) {for (int j 0; j nums2.length; j) {if(nums1[i]nums2[j] i0 j0){dp[i][j] dp[i-1][j-1]1;}res Math.max(res, dp[i][j]);}}return res;}
}dp[i][j] 代表以i-1结尾的nums1数组和以j-1结尾的nums2数组的公共最长子数组的长度。
class Solution {public int findLength(int[] nums1, int[] nums2) {int result 0;int[][] dp new int[nums1.length 1][nums2.length 1];for (int i 1; i nums1.length 1; i) {for (int j 1; j nums2.length 1; j) {if (nums1[i - 1] nums2[j - 1]) {dp[i][j] dp[i - 1][j - 1] 1;result Math.max(result, dp[i][j]);}}}return result;}
}
