网上营销型网站,个人网站架设,杭州兼职网站建设,iis7部署asp网站文章目录 前言一、题目1、原题链接2、题目描述 二、解题报告1、思路分析2、时间复杂度3、代码详解 前言 本专栏文章为《代码随想录》书籍的刷题题解以及读书笔记#xff0c;如有侵权#xff0c;立即删除。 一、题目
1、原题链接 455. 分发饼干 2、题目描述 二、解题报告
1、… 文章目录 前言一、题目1、原题链接2、题目描述 二、解题报告1、思路分析2、时间复杂度3、代码详解 前言 本专栏文章为《代码随想录》书籍的刷题题解以及读书笔记如有侵权立即删除。 一、题目
1、原题链接 455. 分发饼干 2、题目描述 二、解题报告
1、思路分析
1根据贪心的思路由于大饼干可以满足胃口大的孩子也能满足胃口小的孩子我们为了能够让更多的孩子得到满足我们可以优先将大的饼干先满足胃口大的孩子然后以此类推将次小的饼干满足胃口次小的孩子… 2所以我们可以先将每个孩子的胃口值和每个饼干的尺寸进行排序。然后从胃口大的孩子开始枚举同样用尺寸大的饼干开始枚举判断该饼干能否满足该孩子若能则记录的答案数加一同时枚举下一个孩子和下一个饼干若不能满足枚举下一个孩子还是上次枚举的饼干看是否能满足以此类推。注在枚举过程中由于胃口数组和饼干数组可能长度不一致以及每次枚举时元素是否需要变化等问题同时注意数组的边界问题
2、时间复杂度
时间复杂度O(nlogn)
3、代码详解
class Solution {
public:int findContentChildren(vectorint g, vectorint s) {int ans 0; //记录答案sort(g.begin(), g.end());sort(s.begin(), s.end());int j s.size() - 1; //饼干数组指针初始指向最大尺寸饼干下标也就是最后一个元素下标//从后往前枚举孩子for (int i g.size() - 1; i 0; i--) {//注意条件j0要首先判断否则会出现数组下标越界出现错误if (j 0 g[i] s[j] ) { //若s[j]饼干可以满足g[i]孩子则答案1、饼干数组指针前移ans;j--;}}return ans;}
};
