高端大气的企业网站,网站建设主管的策划案,二手网站建设论文,logo在线生成器免费文章目录 一、300.最长递增子序列二、674.最长连续递增序列三、718.最长重复子数组 一、300.最长递增子序列
题目链接
代码如下#xff1a;
class Solution {
public:int lengthOfLIS(vectorint nums) {if (nums.size() 1) return nums.size();vector
class Solution {
public:int lengthOfLIS(vectorint nums) {if (nums.size() 1) return nums.size();vectorint dp(nums.size(), 1); // 以每个数字为结尾的最长递增子序列至少为1int result 0; // 这里初始化0或1都可以因为前面for (int i 1; i nums.size(); i) {for (int j 0; j i; j) {if (nums[i] nums[j]) dp[i] max(dp[i], dp[j] 1); // 遍历i-1以内的所有数字如果有比nums[i]小的就可以在以该数字为结尾的最长递增子序列后加上1个nums[i]组成以nums[i]为结尾的新的最长递增子序列。在i-1之前可能有很多数字小于nums[i],所以要取能组成的最长子序列}if (dp[i] result) result dp[i]; // 最后的结果不在dp[nums,size() - 1]中因为可能最长的递增子序列不是以最后一个数字为结尾的所以要取以所有数字为结尾的最长递增子序列的最大值}return result;}
};二、674.最长连续递增序列
题目链接
代码如下
class Solution {
public:int findLengthOfLCIS(vectorint nums) {if (nums.size() 1) return nums.size(); // 若只有一个数字直接返回1不会继续执行如果没有数字直接返回0,不会继续执行。这样写是和题300保持一致不会混淆int result 0;vectorint dp(nums.size(), 1);for (int i 1; i nums.size(); i) {if (nums[i] nums[i - 1]) dp[i] dp[i - 1] 1;if (dp[i] result) result dp[i];}return result;}
};//if (nums.size() 0) return 0;
//int result 1;
// 如果是这样写result就应该初始化为1因为如果result0输入只有一个数字不会进入下面的for循环结果输出0了但正确应该是1。三、718.最长重复子数组
题目链接
代码如下
class Solution {
public:int findLength(vectorint nums1, vectorint nums2) {vectorvectorint dp (nums1.size() 1, vectorint(nums2.size() 1, 0));int result 0;for (int i 1; i nums1.size(); i) {for (int j 1; j nums2.size(); j) {if (nums1[i - 1] nums2[j - 1]) {dp[i][j] dp[i - 1][j - 1] 1;} if (dp[i][j] result) result dp[i][j];}}return result;}
};
