休息了n天，最后7道！
1道medium+6道hard。
(hard)72. 编辑距离
最开始一眼没有任何思路，看题解的dp[i][j]表示word1的0~i-1构成的字符串变为word2的0~j-1构成的字符串所需要的最小步数才有思路。如果word1[i-1]=word2[j-1]，则dp[i][j]=dp[i-1][j-1]即不需要进行任何其他操作；否则如果删除当前位最优，则dp[i][j]=dp[i-1][j]+1，即删除一次之后变为word1[i-1]的状态再变为word2[j]；如果替换最优，则dp[i][j]=dp[i-1][j-1]+1，即替换一次之后当前位相同，则需要步数为dp[i-1][j-1]加上该次替换操作；最麻烦的则是插入，我最开始确实没想到插入的状态该怎么判断，但转念一想，在当前位添加word2[j-1]不就等同于判断word2删除j-1位之后和word1的情况吗？即dp[i][j]=dp[i][j-1]+1。所以方程如下：dp[i][j] = min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j])+1。初始化为dp[0][i]=i,dp[i][0]=i。因为任何空字符变为有i个字符的字符串都至少需要i步；
而后面发现，word1第i个字符的操作数只与i-1行的情况有关，那么就可以降维：假设当前i,j为x,y，则当j没跑到y之前时，dp[j]表示的都是上一次j的操作，即二维情况的dp[i-1][j]；而当j跑到y之后时，此时的dp[j]表示的是已经进行完本次操作之后的情况了，即dp[i][j]；那么降维就实现了：每次用一个tmp2记录还未改变的dp[j]即二维时的dp[i-1][j]，每跑完一个j时tmp=tmp2，这样就能实现当跑到j时，tmp=dp[i-1][j-1](因为tmp记录的是j=j-1时的dp[i-1][j])，然后dp[i][j]=min(tmp,dp[j],dp[j-1])+1。初始化dp[i]=i。每次i循环时dp[0]=dp[0]+1，等同于j=0时的dp方程。
代码如下：
class Solution {
public:
int minDistance(string word1, string word2) {
int n = word1.length();
int m = word2.length();
int tmp,tmp2;
for(int i = 0 ; i <= m ; i++)
dp[i] = i;
for(int i = 1 ; i <= n ; i++)
{
tmp = dp[0];
dp[0]++;
for(int j = 1 ; j <= m ; j++)
{
tmp2 = dp[j];
if(word1[i - 1] == word2[j - 1])
dp[j] = tmp;
else
dp[j] = min(min(dp[j] , dp[j - 1]) , tmp) + 1;
tmp = tmp2;
}
}
return dp[m];
}
private:
int dp[510];
};(hard) 4. 寻找两个正序数组的中位数
最开始没想到思路，看的题解，才知道其实并不需要像我所想的那样分别确定nums1和nums2的分割位置。正确思路其实很简单，即最终把nums1和nums2划分为l和r两块，在确保lnums1和lnums2的长度和为总长度一半时，且左边最大小于等于右边最小时，此时中位数=右边最小(总长度为奇数)/左边最大+右边最小除2(总长度为偶数)。
因为是两个有序数组，所以我们可以用pos1表示nums1切割位置，则nums2切割位置为总长度/2-pos1，这样可以确保lnums1和lnums2的长度和为总长度一半。而二分的边界l和r变化规则如下：如果nums1左边最大比nums2右边最小大，则表示当前位置肯定是过头了，r = pos1 - 1；如果nums2左边最大比nums1右边最小大，则表示pos1小了，l = pos1 + 1。否则则表示左边都比右边小，说明此时满足条件，可以跳出循环。
代码如下：
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size();
int m = nums2.size();
//确保是对短的数列进行二分
if(n > m)
return findMedianSortedArrays(nums2 , nums1);
int L1Max = 0;
int L2Max = 0;
int R1Min = 0;
int R2Min = 0;
int pos1 , pos2;
int l = 0;
int r = n;
int len = (m + n) >> 1;
while(l <= r)
{
//切割的第一个数列位置，(0~pos1-1)的pos1个数为left1
pos1 = (l + r + 1) >> 1;
//切割的第二个数列位置，因为要确保左右长度相等，则pos1+pos2=总长度/2.
pos2 = len - pos1;
L1Max = pos1 == 0 ? INT_MIN : nums1[pos1 - 1];
R1Min = pos1 == n ? INT_MAX : nums1[pos1];
L2Max = pos2 == 0 ? INT_MIN : nums2[pos2 - 1];
R2Min = pos2 == m ? INT_MAX : nums2[pos2];
/*if(!pos1)
L1Max = INT_MIN;
else
L1Max = nums1[pos1 - 1];
if(pos1 == n)
R1Min = INT_MAX;
else
R1Min = nums1[pos1];
if(!pos2)
L2Max = INT_MIN;
else
L2Max = nums2[pos2 - 1];
if(pos2 == m)
R2Min = INT_MAX;
else
R2Min = nums2[pos2];
*/
//切割位置过头了
if(L1Max > R2Min)
r = pos1 - 1;
//切割位置少了
else if(L2Max > R1Min)
l = pos1 + 1;
else
break;
}
//总长度为奇数
if((m + n) & 1)
return min(R1Min , R2Min);
//总长度为偶数
else
return (double)(max(L1Max , L2Max) + min(R1Min , R2Min)) / 2.0;
}
};(hard) 502. IPO
与其说是堆，我个人觉得更适合说是贪心？本质就是每次启动在当前资本下可启动的所有项目中利润最大的。
用优先队列存最大值即可。
代码如下：
class Solution {
public:
//选择条件：手上的w>=capital
int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
int n = profits.size();
vector<pair<int , int>> s;
for(int i = 0 ; i < n ; i++)
s.push_back({capital[i] , profits[i]});
sort(s.begin(), s.end(), [&](pair<int, int>& p1, pair<int, int>& p2){
return p1.first < p2.first; // 所有项目按照启动资金从小到大排序
});
int index = 0;
int tmp;
//p表示当前资本下所能获得的利润数列
priority_queue<int> p;
while(k)
{
tmp = index;
while(index < n && w >= s[index].first)
{
p.push(s[index].second);
index++;
}
if(p.empty())
break;
//每次取出当前资本下所能获得的最大利润
w += p.top();
p.pop();
k--;
}
return w;
}
};(medium)373. 查找和最小的 K 对数字
思路很简单，就是找nums1的下标i和nums2的下标j的组合。我采用的思路是定义一个优先队列。
先把i,0的组合放入队列(因为无论j为多少，i,j的组合的和肯定是大于等于i,0的)，然后每次看当前队列取出的j的值是否小于m-1，如果是则会把i,j+1放入队列。
代码如下：
class Solution {
public:
struct Node
{
int sum;
int s1 , s2;
bool operator < (const Node& other) const{
return sum > other.sum;
}
};
Node make(int sum , int s1 , int s2)
{
return (Node) {sum , s1 , s2};
}
vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
int n = nums1.size();
int m = nums2.size();
priority_queue<Node> p;
vector<vector<int>> ans;
for(int i = 0 ; i < n ; i++)
{
p.push(make(nums1[i] + nums2[0] , i , 0));
}
while(k && !p.empty())
{
Node tmp = p.top();
p.pop();
ans.push_back({nums1[tmp.s1] , nums2[tmp.s2]});
if(tmp.s2 + 1 < m)
p.push(make(nums1[tmp.s1] + nums2[tmp.s2 + 1] , tmp.s1 , tmp.s2 + 1));
k--;
}
return ans;
}
};(hard) 295. 数据流的中位数
两个优先队列，确保两个队列长度之差小于等于1，同时左边队列的最大值小于等于右边队列的最小值；求中位数则是若两个队列相等，则取左边最大值+右边最小值 / 2，否则是取长度更长的那个队列的堆顶值。代码如下：
class MedianFinder {
public:
MedianFinder() {
lsize = 0;
rsize = 0;
l = priority_queue<int>();
r = priority_queue<int>();
flag = 0;
}
void addNum(int num) {
flag = 0;
//维持左边队列最大值小于右边队列最小值
if(lsize == 0)
{
lsize++;
l.push(num);
return ;
}
if(num < l.top())
{
l.push(num);
lsize++;
if(lsize - rsize >= 1)
{
r.push(-l.top());
l.pop();
rsize++;
lsize--;
}
}
else
{
r.push(-num);
rsize++;
if(rsize - lsize >= 1)
{
l.push(-r.top());
r.pop();
lsize++;
rsize--;
}
}
}
double findMedian() {
//flag=1表示询问了多次相同队列情况下的中位数
if(flag)
return ans;
if(lsize == rsize)
{
ans = (double)(l.top() - r.top()) / 2.0;
}
else if(lsize > rsize)
{
ans = l.top();
}
else
{
ans = -r.top();
}
flag = 1;
return ans;
}
private:
priority_queue<int> l;
priority_queue<int> r;
int lsize;
int rsize;
bool flag;
double ans;
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();
* obj->addNum(num);
* double param_2 = obj->findMedian();
*/(hard)123. 买卖股票的最佳时机 III
不得不说不愧是hard难度的dp，想了两种方法效率都寄了，最后看题解才发现我最开始的想法是对的，只不过公式想复杂了(悲)。
dp[i][j]表示在第i天，若j=0则表示购买第一支股票后手上的资产，j=1则表示卖出第一支股票后手上的资产；若j=2则表示购买第二支股票后手上的资产，j=3则表示卖出第二支股票后手上的资产。则dp公式如下：
若j%2==0则表示购买，那么dp[i][j]可能是之前就买，也可能是i时再买，即dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]-prices[i])；若j%2==1则表示卖出，那么dp[i][j]可能是之前就卖，也可能是i时再卖，即dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+prices[i])；
代码如下：
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
int sum = 0;
/*
for(int i = 0 ; i < n ; i++)
{
for(int k = i + 1 ; k < n ; k++)
{
if(prices[k] < prices[i])
continue;
int ans = prices[k] - prices[i];
int tmp = 0;
for(int j = k + 1 ; j < n ; j++)
{
for(int t = j + 1 ; t < n ; t++)
{
tmp = max(tmp , prices[t] - prices[j]);
}
}
sum = max(sum , ans + tmp);
}
}n^4效率
*/
/*
//假设在i买入 j买入是最优的，则要确保prices[k]-prices[i](k>=i&&k<=j)+prices[t]-prices[j](t>=j&&t<n)是最大;若用dp[i][j]表示i买入 j买入的最优，pos为卖出i的位置，若prices[i]<prices[pos]，则：dp[i-1][j] = dp[i][j] + prices[i] - prices[i - 1] 否则：dp[i-1][j] = dp[i][j] + prices[i] - prices[pos] + prices[i] - prices[i - 1],pos=i
maxn[n - 1] = prices[n - 1];
for(int i = n - 2 ; i >= 0 ; i--)
{
maxn[i] = max(prices[i] , maxn[i + 1]);
}
for(int j = n - 1 ; j >= 0 ; j--)
{
int ans = maxn[j] - prices[j];
int dp = 0;
int tmp = 0;
int pos = j;
for(int i = j ; i >= 1 ; i--)
{
if(prices[i] < prices[pos])
dp = dp + prices[i] - prices[i - 1];
else
{
dp = dp + prices[i] - prices[pos] + prices[i] - prices[i - 1];
pos = i;
}
tmp = max(tmp , dp);
}
sum = max(sum , ans + tmp);
}n^2效率
*/
//初始化0的情况
for(int i = 0 ; i < 4 ; i=i+2)
{
dp[0][i] = -prices[0];
}
for(int i = 1 ; i < n ; i++)
{
//当前 之前卖/买 现在卖/买
dp[i][0] = max(dp[i - 1][0] , -prices[i]);
dp[i][1] = max(dp[i - 1][1] , dp[i - 1][0] + prices[i]);
dp[i][2] = max(dp[i - 1][2] , dp[i - 1][1] - prices[i]);
dp[i][3] = max(dp[i - 1][3] , dp[i - 1][2] + prices[i]);
}
return max(dp[n - 1][1] , dp[n - 1][3]);
}
private:
//int maxn[100001];
int dp[100001][4];
};(hard)188. 买卖股票的最佳时机 IV
规律完全同上，代码如下：
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
int n = prices.size();
for(int i = 0 ; i <= k ; i++)
{
dp[0][i << 1] = -prices[0];
}
for(int i = 1 ; i < n ; i++)
{
for(int j = 0 ; j <= k ; j++)
{
if(j)
{
int tmp = j << 1;
dp[i][tmp] = max(dp[i - 1][tmp] , dp[i - 1][tmp - 1] - prices[i]);
dp[i][tmp + 1] = max(dp[i - 1][tmp + 1] , dp[i - 1][tmp] + prices[i]);
}
else
{
dp[i][0] = max(dp[i - 1][0] , -prices[i]);
dp[i][1] = max(dp[i - 1][1] , dp[i - 1][0] + prices[i]);
}
}
}
int ans = 0;
for(int j = 0 ; j <= k * 2 ; j = j + 1)
{
ans = max(ans , dp[n - 1][j]);
}
return ans;
}
private:
int dp[1001][210];
};降维版的：
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
int n = prices.size();
for(int i = 0 ; i <= k ; i++)
{
dp[i << 1] = -prices[0];
}
int tmp = k << 1;
for(int i = 1 ; i < n ; i++)
{
for(int j = 0 ; j <= tmp ; j+=2)
{
if(j)
{
dp[j + 1] = max(dp[j + 1] , dp[j] + prices[i]);
dp[j] = max(dp[j] , dp[j - 1] - prices[i]);
}
else
{
dp[1] = max(dp[1] , dp[0] + prices[i]);
dp[0] = max(dp[0] , -prices[i]);
}
}
}
int ans = 0;
for(int j = 0 ; j <= tmp ; j = j + 1)
{
ans = max(ans , dp[j]);
}
return ans;
}
private:
int dp[210];
};