122.买卖股票的最佳时机II
https://programmercarl.com/0122.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BAII.html
思路
int maxProfit(int* prices, int pricesSize) {int maxProfit = 0;for (int i = 1; i < pricesSize; i++) {if (prices[i] > prices[i - 1]) {maxProfit += prices[i] - prices[i - 1];}}return maxProfit;
}
学习反思
-
这段代码使用了贪心算法的思想。通过在连续的价格上涨阶段买入股票,在连续的价格下降阶段卖出股票,可以获得最大利润。因此,我们只需要关注连续的上涨阶段,并计算上涨的差价即可。
-
程序使用一个循环遍历了整个价格数组。在循环中,通过比较当前价格和前一个价格的大小关系,判断是否是上涨的阶段。如果是上涨阶段,则将上涨价格的差值累加到最大利润上。
-
最后,返回最大利润。
-
这段代码的时间复杂度为O(n),其中n为价格数组的大小。
55. 跳跃游戏
https://programmercarl.com/0055.%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8F.html
思路
bool canJump(int* nums, int numsSize) {int maxReach = 0; for (int i = 0; i < numsSize; i++) {if (i > maxReach) {return false;}maxReach = (maxReach > i + nums[i]) ? maxReach : (i + nums[i]);if (maxReach >= numsSize - 1) {return true;}}return false;
}
学习反思
-
这段代码使用了贪心算法的思想。通过遍历数组,依次更新能够跳跃的最远距离maxReach。如果maxReach能够到达数组末尾,就返回true;否则,返回false。
-
程序使用一个循环遍历整个数组,遍历过程中判断当前位置是否超过了maxReach。如果超过了maxReach,则说明无法到达当前位置,直接返回false。
-
在每个位置,更新maxReach的值。maxReach的更新规则是当前位置加上当前位置可以跳跃的最大距离,与之前的maxReach比较取较大值。
-
如果maxReach能够到达数组末尾,就返回true。
-
最后,如果整个循环结束仍然没有返回true,则说明无法到达数组末尾,返回false。
-
这段代码的时间复杂度为O(n),其中n为数组的大小。
45.跳跃游戏II
https://programmercarl.com/0045.%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8FII.html
思路
int jump(int* nums, int numsSize) {if (numsSize <= 1) {return 0; }int jumps = 0; int currentEnd = 0; int farthest = 0; for (int i = 0; i < numsSize - 1; i++) {farthest = (farthest > i + nums[i]) ? farthest : (i + nums[i]); if (i == currentEnd) { jumps++; currentEnd = farthest; if (currentEnd >= numsSize - 1) {break;}}}return jumps;
}
学习反思
-
这段代码使用了贪心算法的思想。通过遍历数组,依次更新最远能够到达的位置farthest。在每个位置,判断是否到达了当前跳跃的最远位置currentEnd。如果到达了currentEnd,就进行一次跳跃,跳跃次数加一,并更新currentEnd为farthest。
-
程序使用了一个循环遍历整个数组,遍历过程中判断是否到达了currentEnd。如果到达了currentEnd,就进行一次跳跃,并更新currentEnd为farthest。
-
在每个位置,更新farthest的值。farthest的更新规则是当前位置加上当前位置的跳跃长度,与之前的farthest比较取较大值。
-
如果当前能够到达最后一个位置,就提前返回跳跃次数。
-
最后,返回跳跃次数。
-
这段代码的时间复杂度为O(n),其中n为数组的大小。
1005.K次取反后最大化的数组和
https://programmercarl.com/1005.K%E6%AC%A1%E5%8F%96%E5%8F%8D%E5%90%8E%E6%9C%80%E5%A4%A7%E5%8C%96%E7%9A%84%E6%95%B0%E7%BB%84%E5%92%8C.html
思路
#define abs(a) (((a) > 0) ? (a) : (-(a)))
int sum(int *nums, int numsSize) {int sum = 0;int i;for(i = 0; i < numsSize; ++i) {sum += nums[i];}return sum;
}
int cmp(const void* v1, const void* v2) {return abs(*(int*)v2) - abs(*(int*)v1);
}
int largestSumAfterKNegations(int* nums, int numsSize, int k){qsort(nums, numsSize, sizeof(int), cmp);int i;for(i = 0; i < numsSize; ++i) {if(nums[i] < 0 && k > 0) {nums[i] *= -1;--k;}}if(k % 2 == 1)nums[numsSize - 1] *= -1;return sum(nums, numsSize);
}
学习反思
-
该代码使用了C语言的宏定义来定义计算绝对值的函数abs(a),其中使用了三目运算符来判断a的正负。
-
代码中定义了一个sum函数,用于计算数组中元素的和。通过遍历数组并累加元素的值来实现。
-
定义了一个比较函数cmp,用于qsort函数进行排序时使用。该比较函数首先将要比较的元素转成指针形式,再通过解引用符*来获取元素的值,然后计算绝对值,最后通过减法比较两个元素的绝对值大小。
-
在largestSumAfterKNegations函数中,首先使用qsort函数对数组进行排序,排序的依据是绝对值从大到小。这样排序之后,负数会排在数组的前面,正数会排在数组的后面。
-
然后通过遍历数组,若当前元素小于0并且k大于0,就将当前元素取反,并将k减一。这个过程实际上就是将数组中前k个负数取反的操作。
-
如果循环结束后k仍然大于0,说明数组中所有的元素都已经取反了,此时将绝对值最小的元素取反即可。
-
最后,通过调用sum函数计算最终数组的和,并返回。
-
这段代码的时间复杂度为O(nlogn),其中n为数组的大小,主要的开销在于排序操作。
总结
又是贪心算法的一天,加油!!!