【代码随想录】【算法训练营】【第31天】 [455]分发饼干 [376]摆动序列 [53]最大子序和

本文主要是介绍【代码随想录】【算法训练营】【第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;
}