昌平最好的网站建设,网站建设 中企动力 扬州,东莞网站建设手袋加工,二级消防工程师674. 最长连续递增序列
题目#xff1a;
给定一个未经排序的整数数组nums#xff0c;找到最长且 连续递增的子序列#xff0c;并返回该序列的长度。
dp数组含义#xff1a;
dp[i]#xff1a;以下标i为结尾的连续递增的子序列长度为dp[i]。
递推公式#xff1a;
怎么…674. 最长连续递增序列
题目
给定一个未经排序的整数数组nums找到最长且 连续递增的子序列并返回该序列的长度。
dp数组含义
dp[i]以下标i为结尾的连续递增的子序列长度为dp[i]。
递推公式
怎么推出来dp[i]呢从左到右遍历数组的时候如果后一个比前一个大则代表连续而且递增的关系又因为求的长度所以没符合一次就在后一位的dp基础上1
抽象为
ifnums[i]nums[i-1]dp[i]dp[i-1]1
for (int i 1; i nums.size(); i) {if (nums[i] nums[i - 1]) { // 连续记录dp[i] dp[i - 1] 1;}
} 总代码
class Solution {
public:int findLengthOfLCIS(vectorint nums) {if (nums.size() 0) return 0;int result 1;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;}
}; 718. 最长重复子数组
题目
给两个整数数组 A 和 B 返回两个数组中公共的、长度最长的子数组的长度。要求连续。
思路
没思路根据打印图倒推先看看dp数组含义
dp数组含义
dp[i][j] 以下标i - 1为结尾的A和以下标j - 1为结尾的B最长重复子数组长度为dp[i][j]。 特别注意 “以下标i - 1为结尾的A” 标明一定是 以A[i-1]为结尾的字符串
然后看图 看见图里但两个数组遇见相同的值了就长度就1其他的都是0可以看出dp[i][j]的状态继承dp[i-1][j-1]而来
然后看递推公式 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;} 这里的条件如果nums1的 i 和nums2的 j 在遍历的时候nums1[i-1]和nums2[j-1]的值相等了后续dp就1相当于连续而且上一步相等就1的意思我尝试了下A加了91B加01来推导
发现0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
这里的dp[i][j]也是继承dp[i-1][j-1]但是数组推导的结果变成了1大概意思就是这段代码记录下了每一个连续的公共子序列长度。然后把记录下的最长的长度拿出来返回即可。
全初始化为0方便遇见单个相同的子序列变成1
总代码
过程理解了但思路怎么来的不懂
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;}
};
1143.最长公共子序列
题目
给定两个字符串 text1 和 text2返回这两个字符串的最长公共子序列的长度。
一个字符串的 子序列 是指这样一个新的字符串它是由原字符串在不改变字符的相对顺序的情况下删除某些字符也可以不删除任何字符后组成的新字符串。
例如ace 是 abcde 的子序列但 aec 不是 abcde 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
若这两个字符串没有公共子序列则返回 0。
思路
dp数组含义
dp[i][j]长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j] if (text1[i - 1] text2[j - 1]) {dp[i][j] dp[i - 1][j - 1] 1;//找到一个相同的} else {dp[i][j] max(dp[i - 1][j], dp[i][j - 1]);//没找到} 依照遍历的哪一格上面 左面的的值相等dp值1不相等去两面中最大的那个dp值。
总代码
class Solution {
public:int longestCommonSubsequence(string text1, string text2) {vectorvectorint dp(text1.size() 1, vectorint(text2.size() 1, 0));for (int i 1; i text1.size(); i) {for (int j 1; j text2.size(); j) {if (text1[i - 1] text2[j - 1]) {dp[i][j] dp[i - 1][j - 1] 1;} else {dp[i][j] max(dp[i - 1][j], dp[i][j - 1]);}}}return dp[text1.size()][text2.size()];}
};
1035.不相交的线 题目给两个两个并排的数组把两数组里相同的数字用直线相连求最大的相连数不能同数组相连。
思路
相当于求718最长公共子序列这道题不改变原始顺序的最长公共子序列不求连续内相同数字直接相连 不会交叉至于为啥下面如果124是公共子序列那么原始顺序中44 22 就交叉了而按照第一段的说法就不会代码一样的力扣运行改下字符串名字 总代码
class Solution {
public:int maxUncrossedLines(vectorint A, vectorint B) {vectorvectorint dp(A.size() 1, vectorint(B.size() 1, 0));for (int i 1; i A.size(); i) {for (int j 1; j B.size(); j) {if (A[i - 1] B[j - 1]) {dp[i][j] dp[i - 1][j - 1] 1;} else {dp[i][j] max(dp[i - 1][j], dp[i][j - 1]);}}}return dp[A.size()][B.size()];}
}; 总结所以这些思路是怎么推出来的我都是倒退代码看遍历过程的。
