LeetCode刷题实战300:最长递增子序列
程序IT圈
共 8529字,需浏览 18分钟
·
2021-06-23 20:53
示例
示例 1:
输入:nums = [10,9,2,5,3,7,101,18]
输出:4
解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。
示例 2:
输入:nums = [0,1,0,3,2,3]
输出:4
示例 3:
输入:nums = [7,7,7,7,7,7,7]
输出:1
解题
#pragma once
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define NAMESPACE_LENGTHOFLIS namespace NAME_LENGTHOFLIS {
#define NAMESPACE_LENGTHOFLISEND }
NAMESPACE_LENGTHOFLIS
// 动态规划
// 递推公式:dp[i]=max(dp[j])+1,其中0≤j<i且num[j]<num[i]
// 时间复杂度:O(n^2), 空间复杂度:O(n)
class Solution1
{
public:
int lengthOfLIS(vector<int>& nums)
{
int n=(int)nums.size();
if (n == 0) return 0;
vector<int> dp(n, 0);
int maxLen = 1;
for (int i = 0; i < n; ++i)
{
dp[i] = 1;
for (int j = 0; j < i; ++j)
{
if (nums[j] < nums[i])
{
dp[i] = max(dp[i], dp[j] + 1);
maxLen = max(maxLen, dp[i]);
}
}
}
//return *max_element(dp.begin(), dp.end());
return maxLen;
}
};
// 动态规划
// dp[i] = max(dp[j]) + 1, 其中 0 ≤ j < i 且 num[j] < num[i]
class Solution
{
public:
// 返回不小于目标值的位置
int search(vector<int> & nums, int target)
{
int l = 0;
int r = nums.size() - 1;
while(l < r)
{
int mid = (r + l) / 2;
if(target == nums[mid])
return mid;
else if(target > nums[mid])
l = mid + 1;
else if(target < nums[mid])
r = mid;
}
return l;
}
int lengthOfLIS(vector<int>& nums)
{
int len = nums.size();
vector<int> dp;
if(len <= 0) return 0;
dp.push_back(nums[0]);
for(int i = 1;i < len;i++)
{
if(nums[i] > dp[dp.size() - 1])
dp.push_back(nums[i]);
else
{
//auto it = lower_bound(dp.begin(), dp.end(), nums[i]);
//*it = nums[i];
int p = search(dp,nums[i]);
dp[p] = nums[i];
}
}
return dp.size();
}
};
以下为测试代码//
// 测试 用例 START
void test(const char* testName, vector<int>& nums, int expect)
{
Solution_1 s1;
int result1 = s1.lengthOfLIS(nums);
Solution_2 s2;
int result2 = s2.lengthOfLIS(nums);
if (expect == result1 && expect == result2)
cout << testName << ", solution passed." << endl;
else
cout << testName << ", solution failed. expect:" << expect << ", result1:" <<result1 << ", result2:" << result2 << endl;
}
// 测试用例
void Test1()
{
vector<int> nums = { 10,9,2,5,3,7,101,18 };
int expect = 4;
test("Test1()", nums, expect);
}
void Test2()
{
vector<int> nums = { 10,11,1,2,3,12,13,4 };
int expect = 5;
test("Test2()", nums, expect);
}
NAMESPACE_LENGTHOFLISEND
// 测试 用例 END
//
void LengthOfLIS_Test()
{
NAME_LENGTHOFLIS::Test1();
NAME_LENGTHOFLIS::Test2();
}
评论