代码随想录算法训练营第二十七天|Day27 贪心算法

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; 
}

学习反思

1. 这段代码使用了贪心算法的思想。通过在连续的价格上涨阶段买入股票，在连续的价格下降阶段卖出股票，可以获得最大利润。因此，我们只需要关注连续的上涨阶段，并计算上涨的差价即可。

2. 程序使用一个循环遍历了整个价格数组。在循环中，通过比较当前价格和前一个价格的大小关系，判断是否是上涨的阶段。如果是上涨阶段，则将上涨价格的差值累加到最大利润上。

3. 最后，返回最大利润。

4. 这段代码的时间复杂度为O(n)，其中n为价格数组的大小。

45.跳跃游戏II

思路

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; 
}

学习反思

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);
}

学习反思

1. 该代码使用了C语言的宏定义来定义计算绝对值的函数abs(a)，其中使用了三目运算符来判断a的正负。

2. 代码中定义了一个sum函数，用于计算数组中元素的和。通过遍历数组并累加元素的值来实现。

3. 定义了一个比较函数cmp，用于qsort函数进行排序时使用。该比较函数首先将要比较的元素转成指针形式，再通过解引用符*来获取元素的值，然后计算绝对值，最后通过减法比较两个元素的绝对值大小。

4. 在largestSumAfterKNegations函数中，首先使用qsort函数对数组进行排序，排序的依据是绝对值从大到小。这样排序之后，负数会排在数组的前面，正数会排在数组的后面。

5. 然后通过遍历数组，若当前元素小于0并且k大于0，就将当前元素取反，并将k减一。这个过程实际上就是将数组中前k个负数取反的操作。

6. 如果循环结束后k仍然大于0，说明数组中所有的元素都已经取反了，此时将绝对值最小的元素取反即可。

7. 最后，通过调用sum函数计算最终数组的和，并返回。

8. 这段代码的时间复杂度为O(nlogn)，其中n为数组的大小，主要的开销在于排序操作。