C++第二阶段——数据结构和算法，之前学过一点点数据结构，当时是基于Python来学习的，现在基于C++查漏补缺，尤其是树的部分。这一部分计划一个月
(2024.1.30-2024.4.10已完结），任务量确实有点大，包括春节假期休息，总共用时两个月，主要利用代码随想录来学习，刷题使用力扣网站，不定时更新，欢迎关注！
文章目录
- 一、300.最长递增子序列
- 二、674. 最长连续递增序列
- 三、718. 最长重复子数组
- 四、1143.最长公共子序列
- 五、1035.不相交的线
- 六、53. 最大子数组和
- 七、392.判断子序列
- 八、115.不同的子序列
- 九、583. 两个字符串的删除操作
- 十、72. 编辑距离
- 十一、647. 回文子串
- 十二、516.最长回文子序列
一、300.最长递增子序列
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if(nums.size()==1) return 1;
vector<int> dp(nums.size(),1);
dp[0] = 1;
int result =0;
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);
}
}
if(dp[i]>result) result = dp[i];
}
return result;
}
};
二、674. 最长连续递增序列
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
if(nums.size()==1) return 1;
vector<int> dp(nums.size(),1);
int result =0;
for(int i=1;i<nums.size();i++){
if(nums[i]>nums[i-1]) dp[i] = max(dp[i],dp[i-1]+1);
if(dp[i]> result) result = dp[i];
}
return result;
}
};
三、718. 最长重复子数组
class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
if(nums1.size()==1&&nums2.size()==1&&nums1[0]!=nums2[0]) return 0;
if(nums1.size()==1&&nums2.size()==1&&nums1[0]==nums2[0]) return 1;
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;
}
};
四、1143.最长公共子序列
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
vector<vector<int>> dp(text1.size()+1,vector<int>(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.不相交的线
class Solution {
public:
int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
vector<vector<int>> dp(nums1.size()+1,vector<int>(nums2.size()+1,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;
else dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
}
}
return dp[nums1.size()][nums2.size()];
}
};
六、53. 最大子数组和
class Solution {
public:
int maxSubArray(vector<int>& nums) {
if(nums.size()==1) return nums[0];
vector<int> dp(nums.size(),0);
dp[0] = nums[0];
int result =nums[0];
for(int i=1;i<nums.size();i++){
dp[i] = max(dp[i-1]+nums[i],nums[i]);
if(dp[i]>result) result = dp[i];
}
return result;
}
};
七、392.判断子序列
class Solution {
public:
bool isSubsequence(string s, string t) {
vector<vector<int>> dp(s.size()+1,vector<int>(t.size()+1,0));
for(int i=1;i<=s.size();i++){
for(int j=1;j<=t.size();j++){
if(s[i-1]==t[j-1]) dp[i][j] = dp[i-1][j-1]+1;
else dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
}
}
if(dp[s.size()][t.size()]==s.size()) return true;
return false;
}
};
八、115.不同的子序列
class Solution {
public:
int numDistinct(string s, string t) {
vector<vector<uint64_t>> dp(s.size()+1,vector<uint64_t>(t.size()+1,0));
for(int j=0;j<s.size();j++){
dp[j][0] = 1;
}
for(int i=1;i<=s.size();i++){
for(int j=1;j<=t.size();j++){
if(s[i-1]==t[j-1]){
dp[i][j] = dp[i-1][j-1]+dp[i-1][j];
}
else{
dp[i][j] = dp[i-1][j];
}
}
}
return dp[s.size()][t.size()];
}
};
九、583. 两个字符串的删除操作
class Solution {
public:
int minDistance(string word1, string word2) {
vector<vector<int>> dp(word1.size()+1,vector<int> (word2.size()+1,0));
for(int i=1;i<=word1.size();i++){
for(int j=1;j<=word2.size();j++){
if(word1[i-1]==word2[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 word1.size()+word2.size()-2*dp[word1.size()][word2.size()];
}
};
十、72. 编辑距离
class Solution {
public:
int minDistance(string word1, string word2) {
if(word1.size()==0) return word2.size();
if(word2.size()==0) return word1.size();
vector<vector<int>> dp(word1.size()+1, vector<int>(word2.size()+1,0));
for(int i=0;i<=word1.size();i++) dp[i][0] = i;
for(int j=0;j<=word2.size();j++) dp[0][j] = j;
for(int i=1;i<=word1.size();i++){
for(int j=1;j<=word2.size();j++){
if(word1[i-1]==word2[j-1]){
dp[i][j] = dp[i-1][j-1];
}
else{
int temp = min(dp[i-1][j-1]+1,dp[i-1][j]+1);
dp[i][j]= min(
temp,
dp[i][j-1]+1 // 插入操作
);
}
}
}
return dp[word1.size()][word2.size()];
}
};
十一、647. 回文子串
class Solution {
public:
int countSubstrings(string s) {
vector<vector<bool>> dp(s.size(),vector<bool>(s.size(),false));
int result =0;
for(int i=s.size()-1;i>=0;i--){
for(int j=i;j<s.size();j++){
if(s[i]==s[j]){
if(j-i<=1){
dp[i][j] = true;
result ++;
}
else{
if(dp[i+1][j-1]){
dp[i][j]= true;
result++;
}
}
}
}
}
return result;
}
};
十二、516.最长回文子序列
class Solution {
public:
int longestPalindromeSubseq(string s) {
if(s.size()==1) return 1;
vector<vector<int>> dp(s.size(),vector<int>(s.size(),0));
for (int i = 0; i < s.size(); i++) dp[i][i] = 1;
for(int i=s.size()-1;i>=0;i--){
for(int j=i+1;j<s.size();j++){
if(s[i]==s[j]){
dp[i][j] = dp[i+1][j-1]+2;
}
else{
dp[i][j] = max(dp[i+1][j],dp[i][j-1]);
}
}
}
return dp[0][s.size()-1];
}
};
