122. 买卖股票的最佳时机 II
题中有讲：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
解法一贪心：
后减前是正的利益就买，负的就不要，我们的兴趣点是连续的峰和谷。
关键是我们需要考虑到紧跟谷的每一个峰值以最大化利润。如果我们试图跳过其中一个峰值来获取更多利润，那么我们最终将失去其中一笔交易中获得的利润，从而导致总利润的降低。
例如，在上述情况下，如果我们试图通过考虑差异较大的点以获取更多的利润，获得的净利润总是会小与包含它们而获得的静利润，因为 C 总是小于 A+B。
int res=0;
for(int i=0;i<len-1;i++)
{
int dis=prices[i+1]-prices[i];
if(dis>0)
res+=dis;
}
return res;
解法二dp：
两个状态：0表示卖成钱，1表示买股票。
开始的状态设置为 ：
dp[0][0]：开始你没有手里没有支票所以不能卖，dp[0][0]=0
dp[0][1]：买了一次，那我们的总钞票就先减price[1];
当前状态
dp[i][0]：可以选择继续持上一个卖出状态，也可以选择由stock转为cash，卖出。
dp[i][1]：可以选择继续持上一个买进状态，也可以选择由cash转为stock，买进。
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len=prices.size();
int dp[len+10][2];
if(len<2)
return 0;
dp[0][0]=0;
dp[0][1]=-prices[0];
for(int i=1;i<len);i++)
{
dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]);
dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]);
}
return dp[len-1][0];
}
};
把dp[i][2]变为一维的两个数组
cash[2],stock[2];，空间复杂度没有发生变化都是O(n)
int cash[len+10];
int stock[len+10];
cash[0]=0;
stock[0]=-prices[0];
for(int i=1;i<len;i++)
{
cash[i]=max(cash[i-1],stock[i-1]+prices[i]);
stock[i]=max(stock[i-1],cash[i-1]-prices[i]);
}
return cash[len-1];
再优化成滚动数组,空间复杂度为O(1)
int cash,stock,precash,prestock;
cash=0;
stock=-prices[0];
precash=cash,prestock=stock;
for(int i=1;i<len;i++)
{
cash=max(cash,prestock+prices[i]);
stock=max(stock,precash-prices[i]);
precash=cash;
prestock=stock;
}
return cash;
392. 判断子序列
解法一：双指针
bool isSubsequence(char * s, char * t){
while (*s && *t) {
if (*s == *t)
s++;
t++;
}
return *s == '\0';
}
解法二：二分
右边界是0时候的处理
1.处理单字母时eg a，二分返回left=0，因为tag=-1，所以不能以vt[now][left]!=tag来判定，这样返回的是false
2.因为tag是变动的，假设第一次返回是记录首字母的位置tag=0，right=-1的时候，返回还是left=0，tag=0,就会出现死循环
//个人觉得这题大于等于或大于都可以，因为是个严格单调递增的字符串，那么保证位置只会出现一次
至于测试样例12的确很奇怪，把我的提交正确率降低了不少
把y都删了，请问为啥两个字符串可以匹配成功呢~
bool isSubsequence(string s, string t) {
vector<vector<int> >vt(26);
for(int i=0;i<t.size();i++)
vt[t[i]-'a'].push_back(i);
int tag=-1;
for(int i=0;i<s.size();i++)
{
int now=s[i]-'a';
int mid,left=0,right=vt[now].size()-1;
if(right==-1)return false;
//在原序列中查找第一个字母对应下标大于tag的位置是否存在
while(left<right)
{
mid=(left+right)/2;
if(vt[now][mid]>tag)
right=mid;
else
left=mid+1;
}
if(vt[now][left]<tag)
return false;
tag=vt[now][left];
}
return true;
}
1005. K 次取反后最大化的数组和
解法一：模拟
第一种：序列中没有负数，那一直对最小的数反转
第二种：负数的个数大于K，则只要对前K个负数取反即可
第三种：负数的个数小于K，则对所有负数(num)取反，取负数中的最大数与正数中最小数两者的较小值，根据剩下的K-num翻转次数对min操作.
解法二：贪心
这题最方便的就是用贪心✍
排完序后，从第一个数开始，取反和下一个数比较，如果比下一个数大了，就往下走，否则一直取反
class Solution {
public:
int largestSumAfterKNegations(vector<int>& A, int K) {
int sum=0,i=0;
sort(A.begin(),A.end());
while(i<A.size()&&K>0)
{
A[i]=-A[i];
if(A[i]>0&&A[i]>A[i+1])
i++;
K--;
}
for(int j=0;j<A.size();j++)
sum+=A[j];
return sum;
}
};
1029. 两地调度
注意这里的费用是两座城市的相对费用，从B市调往A市为A-B
class Solution {
public:
int twoCitySchedCost(vector<vector<int>>& costs) {
int sum=0;
vector<int>temp;
for(int i=0;i<costs.size();i++)
{
sum+=costs[i][0];//全部去A市
temp.push_back(costs[i][1]-costs[i][0]);
}
sort(temp.begin(),temp.end());
for(int i=0;i<temp.size()/2;i++)
sum+=temp[i];
return sum;
}
};
1217. 玩筹码
因为移动两个位置不需要代价，所以奇数位置移动到奇数位置和偶数位置移动到偶数位置的不需要钱，所以取奇取偶就相当于把奇数挪动要钱的数目和偶数挪动要钱的数目放邻居，比大小。
class Solution {
public:
int minCostToMoveChips(vector<int>& chips) {
int even=0,odd=0;
for(int i=0;i<chips.size();i++)
{
if(chips[i]%2==0)
odd++;
else
even++;
}
return min(odd,even);
}
};
1221. 分割平衡字符串
不晓得贪心在哪，就是个典型的出栈入栈问题8
class Solution {
public:
int balancedStringSplit(string s) {
int sum=0;
stack<char>st;
for(int i=0;i<s.size();i++)
{
if(st.empty())
{
st.push(s[i]);
sum++;
}
else
{
if(st.top()==s[i]) st.push(s[i]);
else st.pop();
}
}
return sum;
}
};
网友评论