秦皇岛市网站建设_网站建设公司_MongoDB_seo优化

LeetCode 300 最长递增子序列

题目链接：300.最长递增子序列

文档讲解：代码随想录

视频讲解：最长递增子序列

思路与感想：这道题目我先根据题意要求最长递增子序列的长度，确定了dp值应该就是这个最大长度，然后考虑dp[i]中的i究竟代表什么意思，考虑到递推公式累加的时候肯定是最长递增子序列中新遍历的这个元素可以被合法添入子序列末尾，那与之比较的应该是上一个阶段子序列元素中的末尾，由此确定要想实现累加，取决于子序列中旧末尾元素和可能成为新末尾的元素之间的大小，所以我猜想这个dp[i]的含义就是以nums[i]为末尾元素的子序列的最大长度。原本以为明确了dp数组确定递推公式就很简单了，后面却想错了，目光只局限在了dp[i]和dp[i - 1]上面了，还是没有深刻理解到dp数组的含义，末尾元素不一定要是当前遍历元素的前一个元素，只要是下标0到i-1都是可以的，但我们需要求dp[0] + 1到dp[i - 1] + 1这i个值里面的最大值，即最长递增子序列。加一就是把第i个元素也算上，然后有一个if条件只有元素i大于元素j才进行递推。在遍历的过程中随时记录dp[i]的最大值，这个时候不一定是最后一个元素为末尾的时候最大，所以要在所有dp值里面找最大值。

收获：1.子序列问题的递推公式

class Solution { public int lengthOfLIS(int[] nums) { if (nums.length <= 1) { // 特殊情况处理 return nums.length; } int[] dp = new int[nums.length]; // dp[i]表示严格递增子序列中末尾元素为nums[i]的最长长度 Arrays.fill(dp,1); // 初始化dp只有一个元素长度就为1 int result = 1; // 记录最大长度 for (int i = 1; i < nums.length; i++) { for (int j = 0; j < i; j++) { // 递推dp[i]需要遍历nums[0]到nums[i - 1] if (nums[i] > nums[j]) { // 对于末尾元素小于nums[i]的才进行递推更新dp[i] dp[i] = Math.max(dp[i],dp[j] + 1); // 这个过程实际上是在遍历0到i - 1，末尾元素小于nums[i]的情况下，它们各自dp值的最大值，即dp[j]的最大值，而不是比较dp[i]和dp[j] + 1，每个+1是因为加了元素i这个末尾元素 } } result = Math.max(result,dp[i]); //更新最大长度 } return result; } }

LeetCode 674 最长连续递增序列

题目链接：674.最长连续递增序列

文档讲解：代码随想录

视频讲解：最长连续递增序列

思路与感想：这道题目很简单因为子序列是要求连续的。于是我定义了result和size两个变量，只要元素i大于元素i-1的话size就自增，反之size就重置为1，然后每次遍历一个元素处理完size后result都实时更新成最大值。写完这种模拟的方法后再去想动态规划写法，其实也一下子就写出来了，把dp[i]的下标定义为最后一个元素为nums[i]的时候子序列的长度即可，因为是连续的所有只要考虑元素i和它前一个元素i-1大小即可，只有当元素i大于i - 1的时候才递推dp[i] = dp[i - 1] + 1，我最初的代码还写了else dp[i] = 1，其实这步没必要因为初始化的时候每个dp值都为1了。这道题目跟上一道题的区别在于子序列是不是要求连续，上一题理解起来很困难，而且我一开始的做法只想着比较i和i-1，其本质上就是把子序列当成要求连续来写了，但实际上上一题是可以不连续的，所以才要把i之前的dp值都遍历一遍求最大值。但这一道题要求连续所以只需要比较元素i和i-1即可，满足就加1，不满足重头再来累计。

收获：1.子序列连续与不连续递推公式的差别

// 动态规划 class Solution { public int findLengthOfLCIS(int[] nums) { int result = 1; // 记录最终结果 int size = 1; // 记录当前子序列大小 for (int i = 1; i < nums.length; i++) { if (nums[i] > nums[i - 1]) { // 如果当前元素比前一个元素大就加入子序列，size++ size++; } else { size = 1; // 如果不是的话就得重置子序列长度 } result = Math.max(result,size); // 每次都更新result保证其为最大值 } return result; } }

// 模拟法 class Solution { public int findLengthOfLCIS(int[] nums) { int result = 1; // 记录最终结果 int size = 1; // 记录当前子序列大小 for (int i = 1; i < nums.length; i++) { if (nums[i] > nums[i - 1]) { // 如果当前元素比前一个元素大就加入子序列，size++ size++; } else { size = 1; // 如果不是的话就得重置子序列长度 } result = Math.max(result,size); // 每次都更新result保证其为最大值 } return result; } }

LeetCode 718 最长重复子数组

题目链接：718.最长重复子数组

文档讲解：代码随想录

视频讲解：最长重复子数组

思路与感想：这道题目真的挺难，首先也就是这个二维的DP数组的含义虽然经过提示和之前题目的积累可以想出来，虽然想出来的比较直接就是以i，j结尾，但是也可以写出来照理说，不过递推公式就没想出来，一个是因为这个DP数组含义确实没太理清楚，另一个原因是二维DP的题目有段时间没做过有点不习惯，后面给我了递推公式我也想了好一会，一切都还是要建立在这两层for循环里面理解然后画图才清晰。接下来就是每次获得一个dp值就尝试更新result。卡哥把dp数组定义为以i-1和j-1结尾很巧妙，规避了初始化和循环的时候判断边界的操作冗余。这道题也有压缩DP数组的一维滚动数组的解法。相比于二维DP循环内递推的时候要多一个else让dp值为0，然后下一轮循环就鉴于上一轮留下了的数组进行计算，之所以可以这么做的原因就是每一个dp值是根据他的左上角那个即横纵坐标同时减一后那个dp值递推来的，要注意的是内层for循环要倒序，避免取到重复的值。

收获：1.重温二维DP和滚动数组压缩的写法；2.递推公式真难想

class Solution { public int findLength(int[] nums1, int[] nums2) { int[][] dp = new int[nums1.length + 1][nums2.length + 1]; // dp[i][j]的含义是在nums1数组中以i - 1为结尾，在nums2数组中以j - 1为结尾，公共长度最长的子数组长度 int result = 0; // 记录最长的长度 for (int i = 1; i <= nums1.length; i++) { for (int j = 1; j <= nums2.length; j++) { if (nums1[i - 1] == nums2[j - 1]) { // nums1[i - 1]和nums[j - 1]相同说明按照dp的定义，就可以更新dp[i][j]的值了。 dp[i][j] = dp[i - 1][j - 1] + 1; } result = Math.max(result,dp[i][j]); // 每次都更新result的值 } } return result; } }

今天算法难度一般，前两题都可以手撕，最后一题上难度了写不出来，序列问题感觉DP数组含义和递推公式都挺难想的，还是得慢慢沉淀。下午去健个身晚上回寝室接着学springboot然后看一看明天要讲的ppt，以前的内容有点忘了，不知道明天能不能讲好。今天花了大概五个小时。