题目2:买卖股票的最佳时机II
力扣https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2zsx1/解法1:贪心算法(我是看别人这么写的)
int maxProfit(int* prices, int pricesSize){
int money = 0;
for(int i = 1, j = 0; i < pricesSize; i++)
{
if(prices[j] < prices[i])
{
money = money + prices[i] - prices[j];
j = i;
}
else
j++;
}
return money;
}
我写这个算法的思路比较简单,就是找明天是不是比今天高一点,高一点就挣钱,低一点就不投入,累计求和,即可得到最大利润值。
但是我发现一个更简单的
很显然,这个更简单,当然和我的逻辑相同。但是呢,我写的不够简洁,如果把 j 换成 i + 1,就和上面这个相似了。
更新后的代码如下:
int maxProfit(int* prices, int pricesSize){
int money = 0;
for(int i = 0; i < pricesSize - 1; i++)//注意这里,和上面的代码也有区别
{
if(prices[i] < prices[i + 1])
{
money = money + prices[i + 1] - prices[i];
}
}
return money;
}
官方的理解也很简单,就是从整体的角度考虑,将每一天的收益考虑到,这个收益可能是正,0或者负,只要正的全部相加即可,求出最大收益。
解法2:另外还有一种解法,是利用动态规划
今天存在两种情况,一种是我没有持有股票,另一种是我持有股票。而昨天也有相同的状态。那么今天收益就是1.我昨天没有股票,今天我也没有,收益为0;2.我昨天没有股票,今天我买了,收益为今天的股价,是个负值。惨~~~;3.昨天我持有股票,今天我卖了,收益为今天的股价减昨天的股价;4.昨天我持有股票,今天我还是持有,收益为0。
而第一天是否持有股票,可以利用穷举,毕竟也只有两种结果。
根据第一天来判断第二天,根据第二天来判断第三天,直到最后一天。最后一天显然,没有持有股票的情况是相较于持有股票收益更高。
官方题解:
题目1:删除排序数组中的重复项
没做出来。。。。。我好菜。
官方的解释就是分别用两个指针,一个遍历指向不同的元素,另一个找到最近的相同位置的元素值,然后就是元素替代。好简单。。。。。我居然不会做。。。留下菜狗的眼泪。