第八章贪心算法——理论基础，分发饼干题目

目录

概念

什么时候使用

题目举例

分发饼干

力扣题号；455. 分发饼干 - 力扣（LeetCode）

题目描述

示例 1:

示例 2:

解法一：排序+暴力

解法二：贪心

思路

代码实现

总结

---

概念

        贪心算法是一种在每一步选择中都采取当前看起来最好的选择的算法，也就是说，它做出选择后就再也不改变，也不考虑未来可能的影响。简单来说，贪心算法在选择的过程中，每一步都选择局部最优，从而希望得到整体的最优。也就是：通过局部最优，得到全局最优

        贪心算法并不能保证总是得到最优解，但对于许多问题来说，贪心算法能产生最优解。如最小生成树，霍夫曼编码等，可以证明贪心选择性质对于问题的解是最优的。

        贪心算法主要适用于需要对问题求最优解的情况，而贪心算法一般由构造子问题的最优解能逐步得到整个问题的最优解。

        如：最小生成树，单元最短路径，某些类型的装载问题和区间问题等。

        要注意的是，贪心算法并不适用于所有问题，很多问题可能看起来使用贪心很合理，但却无法得到最优解。在具体应用时，需要对问题进行深入的分析和理解。

        因此，我们可以说贪心算法是一种有效但应用有局限性的策略。

什么时候使用

        这个真的找不到一个完美的分界线作为答案，一个比较勉强的说法是当你对一个策略举反例，当你举不出来的时候就可以试试贪心算法了。

题目举例

分发饼干

力扣题号；455. 分发饼干 - 力扣（LeetCode）

注：下述题目描述和示例均来自力扣

题目描述

        假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

        对每个孩子 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.

---

解法一：排序+暴力

我就喜欢暴力，能暴力暴出来的题目我绝对不搞其他的兄弟们

package src;

import java.util.Arrays;
import java.util.Scanner;

public class text {
    public int findContentChildren(int[] g, int[] s) {
        // 若s >= g 那么就可以满足这个孩子
    	int child = 0;
    	// g 1 2 3
    	// s -1 1
    	
    	// 给这两个数组排排序
    	Arrays.sort(g);
    	Arrays.sort(s);
    	
        // 遍历搜索满足一个小朋友最小的那个饼干
    	for (int i = 0; i < g.length; i++) {
    		for (int j = 0; j < s.length; j++) {
				if (s[j] >= g[i]) {
					s[j] = -1;
                    // 找到了，小朋友+1，并且结束循环提升性能
					child++;
					break;
				}
			}
    		
		}
    	return child;
    }
}

虽然慢，但是你就说省内存不！！！你就说过了不！！！

解法二：贪心

思路

        如果我们的目的是尽可能多的让更多的孩子得到满足，那么就不要效仿“田忌赛马”，既然大尺寸的无论是胃口大的还是胃口小的都可以满足他们，那么我们就不要浪费，尽可能给胃口大的。

        那么我们就可以使用贪心算法了，先将饼干大小和孩子胃口进行排序，然后先将饼干小的给胃口小的。

代码实现

        代码里也有一些难点的注解

class Solution {
    public int findContentChildren(int[] g, int[] s) {
    	
    	// 给这两个数组排排序
    	Arrays.sort(g);
    	Arrays.sort(s);
    	int glen = g.length;
    	// 定义一个索引用于指向孩子的胃口数组
    	int index = 0;
    	for (int i = 0; i < s.length; i++) {
    		// 若果index没有到尽头并且满足孩子的胃口那么index++
    		// 如果这里不满足就会下一次循环切换一个更大的饼干来满足
			if ( index < glen && g[index] <= s[i] ) {
				index++;
			}
		}
    	return index;
    }
}

easy

古有“忠孝不能两全”，今有速度内存不可兼得

总结

与此同时，我仍然不理解

这群非人类是如何做到更优化的算法的，我认为这已经是最快的了。shift！！！！