leetcode-初级算法-数组

题目2:买卖股票的最佳时机II

力扣leetcode-初级算法-数组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;
}

我写这个算法的思路比较简单,就是找明天是不是比今天高一点,高一点就挣钱,低一点就不投入,累计求和,即可得到最大利润值。

但是我发现一个更简单的

leetcode-初级算法-数组

 很显然,这个更简单,当然和我的逻辑相同。但是呢,我写的不够简洁,如果把 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。

而第一天是否持有股票,可以利用穷举,毕竟也只有两种结果。

根据第一天来判断第二天,根据第二天来判断第三天,直到最后一天。最后一天显然,没有持有股票的情况是相较于持有股票收益更高。

官方题解:

力扣leetcode-初级算法-数组https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/solution/mai-mai-gu-piao-de-zui-jia-shi-ji-ii-by-leetcode-s/

题目1:删除排序数组中的重复项

没做出来。。。。。我好菜。

官方的解释就是分别用两个指针,一个遍历指向不同的元素,另一个找到最近的相同位置的元素值,然后就是元素替代。好简单。。。。。我居然不会做。。。留下菜狗的眼泪。

 

上一篇:Java 多线程系列02


下一篇:Java入门学习笔记(二)if语句for循环之类的