代码随想录算法训练营day53|1143.最长公共子序列1035.不相交的线53.最大子序和 剑指offer40、41

1143.最长公共子序列

题目链接

这类题的难点在于如何去表示这两个数组比较的状态，对于两个数组的比较状态，我们一般是定义一个二维的dp数组，之后就简单多了。还有需要注意的是，dp[i][j]表示的是[0,i-1]长度的nums[i]和[0,j-1]长度的nums[j]的最长公共子序列的长度，这有利于之后进行初始化以及遍历顺序。

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {int l1=text1.size();int l2=text2.size();vector<vector<int>> dp(l1+1,vector<int>(l2+1,0));for(int i=1;i<=l1;i++){for(int j=1;j<=l2;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[l1][l2];}
};

错因：对dp数组的含义掌握不清晰，递推公式前的判断条件写成了if(text1[i]==text2[j])。

1035.不相交的线

题目链接

就是在上一道题的基础上套了一个壳子，代码和思路一模一样。找相同的元素其实就是子序列问题，求最多的连线其实就是最长公共子序列问题。

class Solution {
public:int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {int l1=nums1.size();int l2=nums2.size();vector<vector<int>> dp(l1+1,vector<int>(l2+1,0));for(int i=1;i<=l1;i++){for(int j=1;j<=l2;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[l1][l2];}
};

53.最大子序和

题目链接

还是主要是明确dp数组的含义即可，题目让我们求最大连续子序和，所以dp数组的含义就是这个，关键是下标i表示哪个元素，dp[i]表示以nums[i]为结尾的最大连续子序和。

class Solution {
public:int maxSubArray(vector<int>& nums) {int len=nums.size();vector<int> dp(len,0);//dp[i]表示以nums[i]为结尾的最大连续子序和dp[0]=nums[0];int result=dp[0];for(int i=1;i<len;i++){//一种是延续之前的子序和，一种是重新开始计算dp[i]=max(dp[i-1]+nums[i],nums[i]);if(dp[i]>result) result=dp[i];}return result;}
};

剑指 Offer 40. 最小的k个数

题目链接

方法一：最直接的思路，先排序，再把前k个数放到res数组中。（具体的快排代码还需研究）

class Solution {
public:vector<int> getLeastNumbers(vector<int>& arr, int k) {vector<int> res;sort(arr.begin(),arr.end());for(int i=0;i<k;i++){res.push_back(arr[i]);}return res;}
};

方法二：使用大顶堆，也就是优先级队列。因为我们想获得最小的前k个元素，如果用小顶堆的话，每次弹出元素的时候会把堆顶元素弹出，最后剩下的其实是最大的k个元素，所以应该选大顶堆。

class Solution {
public:vector<int> getLeastNumbers(vector<int>& arr, int k) {vector<int> res(k);priority_queue<int> que;for(auto x:arr){que.push(x);if(que.size()>k) que.pop();}for(int i=k-1;i>=0;i--){res[i]=que.top();que.pop();}return res;}
};

和本题比较像的是栈与队列的347.前 K 个高频元素，可以看卡哥的讲解：视频链接

剑指 Offer 41. 数据流中的中位数

题目链接

思路：用一个大顶堆记录较小的数字，用小顶堆记录较大的数字，同时保证大顶堆里的元素数量-小顶堆元素数量=1/0。具体可以代入1,2,3,4理解一下。

class MedianFinder {
public:/ initialize your data structure here. */priority_queue<int> maxheap;priority_queue<int,vector<int>,greater<int>> minheap;MedianFinder() {}void addNum(int num) {//先全都插入大顶堆maxheap.push(num);//数目相差超过1了，就平衡一下if((maxheap.size()-minheap.size())>1){//确保相差是1或者是0，可以代入1,2,3,4理解一下minheap.push(maxheap.top());maxheap.pop();}if(minheap.size()>0&&maxheap.top()>minheap.top()){int maxval=maxheap.top();int minval=minheap.top();maxheap.pop();minheap.pop();maxheap.push(minval);minheap.push(maxval);}}double findMedian() {if((maxheap.size()+minheap.size())%2==1) return maxheap.top();else return (maxheap.top()+minheap.top())/2.0;}
};

错因：最后除以2的话，就是两个整数相加除以2，就会向下取整，需要除以2.0，这时c++会自动转为浮点数。