本文主要是介绍【代码随想录】【算法训练营】【第31天】 [455]分发饼干 [376]摆动序列 [53]最大子序和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
前言
思路及算法思维，指路 代码随想录。
题目来自 LeetCode。
day 31，放假前的周五，总是令人激动的~
题目详情
[455] 分发饼干
题目描述
455 分发饼干
解题思路
前提：
思路：贪心算法，小饼干优先满足较小胃口。
重点：局部最优解，叠加整体最优解。
代码实现
C语言
排序后，小饼干优先小胃口
int cmp(void *p1, void *p2)
{return (*(int *)p1 > *(int *)p2);
}int findContentChildren(int* g, int gSize, int* s, int sSize) {if ((gSize == 0) || (sSize == 0)) {return 0;}// 排序qsort(g, gSize, sizeof(int), cmp);qsort(s, sSize, sizeof(int), cmp);// 小饼干满足小胃口孩子int sLoc = 0;int gLoc = 0;int count = 0;while ((gLoc < gSize) && (sLoc < sSize)) {if (g[gLoc] <= s[sLoc]) {// 满足胃口，分配gLoc++;count++;}sLoc++;}return count;
}
[376] 摆动序列
题目描述
376 摆动序列
解题思路
前提：差值正负交替出现，即出现山峰或低谷
思路：判断峰值的个数
重点：注意平坡，尤其是首尾位置，影响序列长度。
代码实现
C语言
寻找峰值个数，注意平坡
int wiggleMaxLength(int* nums, int numsSize){// 初始化为1，默认首位前为平坡int length = 1;int prediff = 0;int curdiff = 0;for (int i = 0; i < numsSize - 1; i++) {int curdiff = nums[i + 1] - nums[i]; // 判断是否为符合要求的山峰或低谷if (((prediff >= 0) && (curdiff < 0)) || ((prediff <= 0) && (curdiff > 0))) {length++;// 出现峰值时更新prediffprediff = curdiff;}}return length;
}
[53] 最大子序和
题目描述
53 最大子序和
解题思路
前提：连续子数组的和的最大值
思路：负数与任何数值相加，只会使值变的更小，所以当当前和为负数时，抛弃该和，重新计算。
重点：贪心算法思维。
代码实现
C语言
连续和为负数时，抛弃当前连续子数组和
int maxSubArray(int* nums, int numsSize) {int sum = 0;int slow = 0;int fast = 0;int maxSum = -10001;while (fast < numsSize) {// 连续和为负数时，抛弃当前连续子数组和if (sum < 0) {sum = 0;}sum += nums[fast];// 取最大和if (sum > maxSum) {maxSum = sum;}fast++;}return maxSum;
}
今日收获
- 贪心算法思维方式。
这篇关于【代码随想录】【算法训练营】【第31天】 [455]分发饼干 [376]摆动序列 [53]最大子序和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
