LC300. 最长递增子序列
- dp[i]含义：i 之前包括 i 的以nums[i]结尾的最长递增子序列的长度
int lengthOfLIS(vector<int>& nums)
{
int size = nums.size();
vector<int> dp(size, 1);
int maxLength = 1;
for (int i = 1; i < size; ++i)
{
for (int j = 0; j < i; ++j)
{
if (nums[i] > nums[j])
{
dp[i] = max(dp[i], dp[j] + 1);
}
}
if (dp[i] > maxLength)
maxLength = dp[i];
}
return maxLength;
}
参照题解，动态规划 + 二分法的做法，思路大概如下：
- 比如序列是78912345，前三个遍历完以后tail是789，这时候遍历到1，就得把1放到合适的位置，于是在tails二分查找1的位置，变成了189（如果序列在此时结束，因为res不变，所以依旧输出3），再遍历到2成为129，以此类推，最后tails数组的长度即最长的子序列
但是自己的binarySearch写得也太臃肿了，稍后对二分查找（包括==, >, <, >=, <= 的情况）进行优化
void binarySearch(vector<int>& tails, int target)
{
int left = 0, right = tails.size() - 1;
int index = 0;
if (target <= tails[0])
{
tails[0] = target;
return;
}
else if (target == tails[right])
{
return;
}
else if (target > tails[right])
{
tails.emplace_back(target);
return;
}
while (left <= right)
{
index = ((right - left) >> 1) + left;
if (index > 0 && tails[index] >= target && target > tails[index - 1])
{
tails[index] = target;
break;
}
else if (tails[index] > target)
right = index - 1;
else if (tails[index] < target)
left = index + 1;
}
}
int lengthOfLIS_Advanced(vector<int>& nums)
{
int size = nums.size();
vector<int> tails;
tails.emplace_back(nums[0]);
for (int i = 1; i < size; ++i)
{
binarySearch(tails, nums[i]);
}
return tails.size();
}
LC674. 最长连续递增序列
int findLengthOfLCIS(vector<int>& nums)
{
int size = nums.size();
int maxLength = 1;
int count = 1;
for (int i = 1; i < size; ++i)
{
if (nums[i] > nums[i - 1])
{
++count;
if (count > maxLength)
maxLength = count;
}
else
count = 1;
}
return maxLength;
}
LC718. 最长重复子数组
想了一段时间才写出来的做法：
对nums2进行multimap搜集，遍历nums1，对nums2中出现的相同元素进行往回判断，若确定为连续重复的子数组，则根据前一位的dp[i]值加1，即dp[index] = dp[index - 1] + 1
- dp[i]含义：对nums2数组，以下标为 i 结尾的子数组，此时的最长重复长度
开始把 dp[index] = max(dp[index], 1) 直接写成了dp[index] = 1，对例子nums1 = [1,2,3,2,1]，nums2 = [3,2,1,4,7,1,2]来说最后得到的dp = [1,2,3,0,0,1,1]，而最后一个dp[6]应该等于2的。
int findLength(vector<int>& nums1, vector<int>& nums2)
{
int size = nums2.size();
multimap<int, int> mmap;
vector<int> dp(size, 0);
int maxLength = 1;
for (int i = 0; i < size; ++i)
{
mmap.emplace(nums2[i], i);
}
for (int i = 0; i < nums1.size(); ++i)
{
auto it = mmap.find(nums1[i]);
for (int j = 0; j < mmap.count(nums1[i]); ++j, ++it)
{
int index = it->second;
if (index != 0 && i != 0 && nums2[index - 1] == nums1[i - 1])
{
dp[index] = dp[index - 1] + 1;
if (dp[index] > maxLength)
maxLength = dp[index];
}
else
dp[index] = max(dp[index], 1);
}
}
return maxLength;
}
如上的写法，如例子[1,0,0,0,1] [1,0,0,1,1]时会出错，对nums1的第3个0判断时，由于nums2中的第二个0进行判断 nums2[index - 1] == nums1[i - 1]) 成立，dp[2]就会变成4，导致出错。
看了Carl哥的题解后，总结下自己做法出现的问题：
上面做法，问题有两个问题
- 模拟的一维dp数组从前向后遍历了，题解中，对于二维dp数组中两层for循环都是从前向后的，当然没问题，如果压为dp一维滚动数组的话，应该是从后向前遍历。
- 在本题的推导公式中，不再像之前题目类似 dp[i] = max(dp[i], xxxx) 或 dp[i] [j] = max(dp[i - 1] [j], xxxx) 的格式，即本次位置的推导结果不是同上一次循环同一个位置推导得来的。举个例子，如下面的二维数组推导，格子值的推导是由左上角推来的，但与其正上方的格子没关系。所以当使用滚动数组时，若nums1[i] != nums2[j - 1]，不相等的时候要有赋0的操作。
////参照Carl哥思路，写的一版滚动数组
int findLength(vector<int>& nums1, vector<int>& nums2)
{
int size = nums2.size();
vector<int> dp(size + 1, 0);
int maxLength = 0;
for (int i = 0; i < nums1.size(); ++i)
{
for (int j = size; j >= 1; --j) //从后向前遍历
{
if (nums1[i] == nums2[j - 1])
{
dp[j] = dp[j - 1] + 1;
}
else
dp[j] = 0;
if (dp[j] > maxLength)
maxLength = dp[j];
}
}
return maxLength;
}
////二维数组版本
int findLength(vector<int>& nums1, vector<int>& nums2) {
vector<vector<int>> dp (nums1.size() + 1, vector<int>(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;
}