建站平台与建站系统,深圳网站制作首荐祥奔科技,网页如何建设,客户营销目录
题目需求
贪心算法思想
什么是贪心
贪心算法的使用
贪心算法的优缺点
代码实现
后言 题目需求 假设你是一位很棒的家长#xff0c;想要给你的孩子们一些小饼干。但是#xff0c;每个孩子最多只能给一块饼干。 对每个孩子 i#xff0c;都有一个胃口值 g[i]…目录
题目需求
贪心算法思想
什么是贪心
贪心算法的使用
贪心算法的优缺点
代码实现
后言 题目需求 假设你是一位很棒的家长想要给你的孩子们一些小饼干。但是每个孩子最多只能给一块饼干。 对每个孩子 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 g.length 3 * 104 0 s.length 3 * 104 1 g[i], s[j] 231 - 1 贪心算法思想
什么是贪心
贪心算法是一种解决问题的方法其核心思想是每一步都选择当前状态下的最优解而不考虑之后的选择会如何影响问题的解决。贪心算法通常适用于那些具有最优子结构性质的问题即问题的最优解可以通过子问题的最优解来推导。
贪心算法的使用 建立数学模型 首先要明确问题的数学模型即问题的目标函数以及约束条件。 确定贪心选择策略 确定每一步的最优选择策略即在当前状态下如何做出最优决策。 迭代求解 从问题的初始状态开始根据贪心选择策略逐步地向前推进直至达到问题的终止状态。 检验解的有效性 需要验证贪心算法得到的解是否满足问题的所有约束条件以及是否达到了问题的最优解。
贪心算法的优缺点
贪心算法的优点是简单、高效通常时间复杂度较低适用于求解一些具有贪心选择性质的优化问题比如最小生成树、最短路径等。然而贪心算法也存在一些局限性即可能得不到全局最优解只能得到局部最优解因此在应用时需要注意问题的特性以及选择合适的贪心策略。
代码实现
class Solution {
public:int findContentChildren(vectorint g, vectorint s) {// 先将孩子的胃口和饼干的尺寸排序sort(g.begin(), g.end());sort(s.begin(), s.end());int i 0, j 0;int count 0;// 尝试将饼干分配给孩子while (i g.size() j s.size()) {if (s[j] g[i]) { // 如果当前饼干满足当前孩子的胃口count;i; // 继续尝试下一个孩子}j; // 否则继续尝试下一块饼干}return count;}
};
可自行编写main函数进行测试。
后言
贪心说到底并不是某钟具体的算法而是一种思想即”局部最优即全局最优“这样的思想在许多情境下都能运用例如最优合并等是一种基础的算法思想。
最后给两个力扣题目吧都是简单题咱们也是从基础练
561. 数组拆分 - 力扣LeetCode
605. 种花问题 - 力扣LeetCode
本篇博文到此就结束了新手上路水平有限如有错误还望海涵并指出
