LeetCode 455. 分发饼干Assign Cookies题解贪心 双指针【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcodeLeetCode 455「分发饼干」Assign Cookies是一道经典的贪心算法入门题也是本仓库leetcode 解题之路easy 题集中的代表题目。本文以仓库内 problems/455.AssignCookies.en.md 与 problems/455.AssignCookies.md 为主体完整还原题目描述、贪心策略推导、双指针算法流程与 JS / Python 双语言实现并结合仓库 thinkings/greedy.md 中对贪心策略的理论总结讲清为什么排序后按顺序匹配就是最优解读完即可举一反三迁移到同类资源分配 / 覆盖类问题。题目回顾假设你是一位很棒的家长想要给孩子们一些小饼干。规则如下每个孩子最多只能得到一块饼干对每个孩子 i都有一个胃口值gi即能让该孩子满足的饼干最小尺寸每块饼干 j 都有一个尺寸sj如果sj gi就可以把饼干 j 分给孩子 i该孩子会得到满足胃口值均为正数。目标尽可能满足越多数量的孩子并输出这个最大数值。两个示例输入输出解释g [1,2,3],s [1,1]1两块尺寸为 1 的饼干只能满足胃口为 1 的孩子g [1,2],s [1,2,3]2饼干数量和尺寸足以让所有孩子满足前置知识为什么这道题用贪心本题所需的两个前置知识分别是贪心算法与双指针仓库 thinkings/greedy.md 对此有系统的理论说明。贪心策略的核心定义是在对问题求解时总是做出在当前看来最好的选择即做出某种意义上的局部最优解而不从整体最优的角度去全局搜索。贪心并不是对任何问题都能得到整体最优解典型的反例是硬币找零关键取决于贪心策略的选择。一个可用的贪心策略必须具备无后效性某个状态以前的过程不会影响以后的状态后续决策只与当前状态有关——这一点与动态规划相同。贪心与动态规划一样大多数情况下都用来处理极值问题最大化、最小化而本题要求满足孩子的最大数量正是一个典型的极值问题。思路分析小的饼干优先匹配小的胃口本题可以这样贪心求解给一个孩子的饼干应当尽量小并且能满足孩子把大饼干留来满足胃口大的孩子。因为胃口小的孩子最容易得到满足所以优先满足胃口小的孩子的需求然后按照从小到大的顺序尝试用每块饼干去匹配孩子。为什么这个贪心策略是安全的局部最优即全局最优孩子的胃口g排序后胃口最小的孩子g[0]最难替代——能被大饼干满足的一定也能被至少同样大的饼干满足反过来一块小饼干如果连最小胃口的孩子都满足不了那它一定满足不了任何胃口更大的孩子可以直接放弃因此用当前最小尺寸的饼干去尝试当前最小胃口的孩子成功则双方都向前推进资源不浪费失败则该饼干对后续所有孩子都无效直接丢弃。每一步都不牺牲未来的可能性具备无后效性。算法步骤将需求因子数组g和饼干尺寸数组s分别从小到大排序使用贪心思想并配合两个指针gi指向当前待满足的孩子胃口值sj指向当前尝试的饼干饼干尺寸每块饼干只尝试一次若s[sj] g[gi]说明该饼干能满足当前孩子两个指针同时后移满足数 1接着尝试满足下一个孩子否则说明该饼干太小换下一块更大的饼干继续尝试sj任一个数组遍历完毕即终止返回累计的满足数量。关键点先排序再贪心只有两个数组都从小到大有序才能保证当前最小饼干对当前最小胃口的比较是全局最优的贪心决策双指针保证了每块饼干至多被扫描一次整体呈现线性扫描结构。代码实现JavaScript 版来自英文文档仓库英文版 problems/455.AssignCookies.en.md 给出的 JS 实现/** * param {number[]} g * param {number[]} s * return {number} */ const findContentChildren function (g, s) { g g.sort((a, b) a - b); s s.sort((a, b) a - b); let gi 0; // 胃口值 let sj 0; // 饼干尺寸 let res 0; while (gi g.length sj s.length) { // 当饼干 sj 胃口 gi 时饼干满足胃口更新满足的孩子数并移动指针 if (s[sj] g[gi]) { gi; sj; res; } else { // 当饼干 sj 胃口 gi 时饼干不能满足胃口需要换大的 sj; } } return res; };Python 版来自中文文档仓库中文版 problems/455.AssignCookies.md 额外提供了 Python 实现写法更为精简——当饼干满足胃口时同时移动孩子指针并计数无论是否满足饼干指针都前进不满足说明饼干太小同样要丢弃class Solution: def findContentChildren(self, g: List[int], s: List[int]) - int: g.sort() s.sort() count gIdx sIdx 0 while gIdx len(g) and sIdx len(s): if s[sIdx] g[gIdx]: gIdx 1 count 1 sIdx 1 return count两种语言实现遵循完全相同的贪心 双指针逻辑可相互对照理解。复杂度分析时间复杂度O(NlogN)主要开销来自对g和s两个数组的排序排序完成后的双指针扫描为 O(N)被排序项支配。空间复杂度O(1)只使用常数个指针变量与计数器未引入与输入规模相关的额外空间。在仓库中的定位与延伸阅读本题收录于本仓库的 easy 题集见 collections/easy.md英文版见 collections/easy.en.md并已列入仓库根目录 README.md 的 LeetCode 题解索引题号 0455。若想进一步加深对贪心算法的理解建议阅读仓库专题文章 thinkings/greedy.md英文版 thinkings/greedy.en.md。该文指出LeetCode 上的贪心题目大多用于处理极值问题其中覆盖类问题如 45. 跳跃游戏 II、1024. 视频拼接 等对应的中文题解见仓库 problems 目录同样可以采用贪心求解且与本题共享维护最远/最优可达边界、逐步贪心推进的底层套路同时也要注意贪心的难点在于证明局部最优解可以推出全局最优解这正是本题最小饼干匹配最小胃口策略的价值所在。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考