网站流量外流,wordpress主页模板,wordpress 音乐格式,机械加工网名一、题目 假设你是一位很棒的家长#xff0c;想要给你的孩子们一些小饼干。但是#xff0c; 每个孩子最多只能给一块饼干 。 对每个孩子i#xff0c;都有一个 胃口值 g[i] #xff0c;这是能让孩子们满足胃口的饼干的最小尺寸#xff1b;并且每块饼干j#xff0c;都有一个…一、题目 假设你是一位很棒的家长想要给你的孩子们一些小饼干。但是 每个孩子最多只能给一块饼干 。 对每个孩子i都有一个 胃口值 g[i] 这是能让孩子们满足胃口的饼干的最小尺寸并且每块饼干j都有一个 尺寸s[j]。如 果 s[j] g[i] 我们 可 以 将 这 个 饼 干 j 分 配 给 孩 子 i 这个孩子会得到满足 。你的目标是尽可能满足越多数量的孩子并输出这个最大数值。 示例 1: 输入 : g [ 1 , 2 , 3 ] , s [ 1 , 1 ] 输出 : 1 解释 : 你有三个孩子和两块小饼干 3 个孩子的胃口值分别是 1 , 2 , 3 。 虽然你有两块小饼干由于他们的尺寸都是 1 你只能让胃口值是 1 的孩子满足。 所以你应该输出 1 。 示例 2: 输入 : g [ 1 , 2 ] , s [ 1 , 2 , 3 ] 输出 : 2 解释 : 你有两个孩子和三块小饼干 2 个孩子的胃口值分别是 1 , 2 。 你拥有的饼干数量和尺寸都足以让所有孩子满足。 所以你应该输出 2 。 提示 1) 1 g.length 3*10^4 2) 0 s.length 3*10^4 3) 1 g[i], s[j] 2^31-1 二、解题思路 贪心算法亦称贪婪算法是一种在解决问题时始终选择当前状态下最优解的策略。换言之该算法并不追求全局最优而是基于局部最优解的累积效果。 在《算法导论》一书中对贪心算法有如下阐述贪心算法在每一步都做出当时认为最佳的选择即始终采取局部最优的决策期望这些局部最优选择能够导向全局最优解。 针对本题贪心算法尤为适用。题目要求尽可能多地满足孩子们的需求由于饼干不可分割因此我们可以采取一种策略即让胃口较大的孩子食用较大的饼干而胃口较小的孩子则食用较小的饼干。具体操作时可以从胃口最小的孩子开始尝试用最小的饼干来满足其需求若无法满足则逐步尝试更大的饼干直至找到合适的饼干或遍历完所有饼干。
#include iostream
#include vector
#include algorithmint findContentChildren(std::vectorint g, std::vectorint s) {// 先对胃口值和饼干尺寸进行排序std::sort(g.begin(), g.end());std::sort(s.begin(), s.end());int count 0;for (int j 0; count g.size() j s.size(); j) {// 如果当前饼干能满足当前孩子的胃口值count就加1否则就继续查找更大的饼干if (g[count] s[j])count;}return count;
}int main() {std::vectorint g {1, 2, 3}; // 孩子的胃口值std::vectorint s {1, 1}; // 饼干的尺寸int result findContentChildren(g, s);std::cout 满足的孩子数量: result std::endl;return 0;
} 三、代码实现 还一种方式就是先从最大的饼干开始看一下能不能满足胃口最大的如果不能满足就 找胃口稍微小一点是再试一下如果还不能满足就一直找。代码实现如下 #include iostream
#include vector
#include algorithmint findContentChildren(std::vectorint g, std::vectorint s) {// 先对胃口值和饼干尺寸进行排序std::sort(g.begin(), g.end());std::sort(s.begin(), s.end());int count 0;int i s.size() - 1;for (int j g.size() - 1; i 0 j 0; j--) {// 如果当前饼干能满足当前孩子的胃口值count就加1否则就继续查找胃口更小的孩子if (g[j] s[i]) {count;i--;}}return count;
}int main() {std::vectorint g {1, 2, 3}; // 孩子的胃口值std::vectorint s {1, 1}; // 饼干的尺寸int result findContentChildren(g, s);std::cout 满足的孩子数量: result std::endl;return 0;
} 贪心算法仅追求局部最优解它能够界定某些问题的可行域但无法确保解的最优性。由于贪心算法始终立足于局部视角并未全面考量整体情况因此在某些问题上应用贪心算法是适宜的而在其他问题上则可能不适用。这些都需要针对具体问题进行具体分析。
