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

​​​​​​代码随想录

思路

int cmp(int* a, int* b) {return *a - *b;
}
int findContentChildren(int* g, int gSize, int* s, int sSize){if(sSize == 0)return 0;qsort(g, gSize, sizeof(int), cmp);qsort(s, sSize, sizeof(int), cmp);int numFedChildren = 0;int i = 0;for(i = 0; i < sSize; ++i) {if(numFedChildren < gSize && g[numFedChildren] <= s[i])numFedChildren++;}return numFedChildren;
}

学习反思

代码的思路是首先对孩子的胃口数组和饼干的尺寸数组进行升序排序，然后遍历饼干数组，对每个饼干判断是否能满足孩子的胃口，如果能满足，则满足的孩子数量加1，并继续判断下一个孩子和下一个饼干。代码中使用了qsort函数对数组进行排序，排序的依据是cmp函数的返回值，cmp函数中使用了指针来比较两个元素的大小。最后返回满足孩子胃口的孩子数量。这段代码的时间复杂度是O(nlogn)

376. 摆动序列

https://programmercarl.com/0455.%E5%88%86%E5%8F%91%E9%A5%BC%E5%B9%B2.html

思路

int wiggleMaxLength(int* nums, int numsSize) {if (numsSize < 2) {return numsSize;}int up = 1, down = 1; for (int i = 1; i < numsSize; i++) {if (nums[i] > nums[i - 1]) {up = down + 1; } else if (nums[i] < nums[i - 1]) {down = up + 1; }}return up > down ? up : down; 
}

学习反思

代码的思路是使用两个变量up和down来分别记录当前位置的上升子序列的长度和下降子序列的长度。 初始时，将up和down都设置为1，表示至少有一个元素可以作为子序列的起点。然后从数组的第二个元素开始遍历，对于每个元素，与前一个元素进行比较。 如果当前元素比前一个元素大，说明可以将当前元素加入到上升子序列中，这时更新up的值为down+1。 如果当前元素比前一个元素小，说明可以将当前元素加入到下降子序列中，这时更新down的值为up+1。最后返回up和down中较大的值，即最长的摆动子序列的长度。时间复杂度是O(n)。

int maxSubArray(int* nums, int numsSize) {if (numsSize == 0) {return 0; }int maxCurrent = nums[0]; int maxGlobal = nums[0];   for (int i = 1; i < numsSize; i++) {maxCurrent = (nums[i] > maxCurrent + nums[i]) ? nums[i] : (maxCurrent + nums[i]);if (maxCurrent > maxGlobal) {maxGlobal = maxCurrent; }}return maxGlobal; 
}