一、122 买卖股票最佳时机
题目介绍限制条件,必须卖了再买,而且当前交易一只股票。一开始想法是去遍历,找到每个区间段间的差值,然后再相加。看了解答,其实每一天的利润,都是可以用差值表示出来,每一天的利润最大,那么累加起来,总利润也是最大的。再思考怎么能最大化,只要每天的是正利润,那么就是递增的。
int maxProfit(int* prices, int pricesSize) {//可以计算每天的利润int result = 0;for(int i = 1; i < pricesSize; i++){int diff = prices[i] - prices[i - 1];//每一天的正利润相加if(diff >= 0){result += diff;}}return result;
}
二、55 跳跃游戏
题目意思是从下标index=0(第一个位置),跳跃数组上指定范围内的步数,能不能跳跃到最后一步。
每一步所在的数组值都是一个跳跃范围,代表了在此时,这个点能够达到的最大范围。再跳跃到最大范围的点上,找到此位置上的值,来确认范围是否覆盖。
每一次遍历数组,找到num[i] + i是不是最大值,每一次都更新最大值,判断最大值是不是到达边界。
bool canJump(int* nums, int numsSize) {int pos = 0;if(numsSize == 1){return true;}//注意这里是<= posfor(int i = 0; i <= pos; i++){pos = pos > i + nums[i] ? pos : i + nums[i];//printf("pos %d i%d \n", pos, i);if(pos >= numsSize -1){return true;}}return false;
}
三、45 跳跃游戏II
题目明确是能到达最后一个位置,求最小的步骤。
最少的步骤,就是每一步尽量选择最大的步长,且选择的位置 + 步长能够覆盖到最后一个位置。
注意:真正解题的时候,要从覆盖范围出发,不管怎么跳,覆盖范围内一定是可以跳到的,以最小的步数增加覆盖范围,覆盖范围一旦覆盖了终点,得到的就是最少步数!
遍历整个数组,拿到最远覆盖范围(每一次遍历需要更新),如果i到达上一次的最远范围,把当前最远范围给pre上一次最远范围。移动次数加1,如果当前最远范围已经能覆盖最后一个位置,那么就退出;
int jump(int* nums, int numsSize) {int next = 0;int cur = 0;int result = 0;for(int i = 0; i < numsSize; i++){next = next > nums[i] + i? next : nums[i] + i;if(i == cur){result++;cur = next;if(next >= numsSize - 1){break;}}}return result;
}