分发饼干

发表于
本文字数： 1k 阅读时长 ≈ 1 分钟

LeetCode每日一题，455. Assign Cookies

先看题目描述

rRGx2R.png

大意就是给定两个数组 g 和 s，g 中存储的元素代表每个孩子的胃口，s 中存储的元素代表每个饼干的尺寸，我们现在需要给孩子分发饼干，为了满足孩子，给孩子分配的饼干的尺寸必须不小于孩子的胃口，且最多给每个孩子分配一块饼干，问可以满足的孩子的最大数量是多少

算法和思路

贪心+排序+双指针

为了尽可能满足最多数量的孩子，从贪心的角度考虑，应该按照孩子的胃口从小到大的顺序依次满足每个孩子，对于每个孩子，应该选择可以满足这个孩子的胃口且尺寸最小的饼干

算法流程

  • 将 g 数组和 s 数组按照升序排列
  • 设 g 数组和 s 数组的长度为 m 和 n，初始化两个指针 i 和 j 均等于 0，维护已满足孩子数量的变量 res 初始化为 0
  • 当 i < m 且 j < n 时执行循环：
    • 若 g[i] <= s[j]，说明该饼干能满足当前的孩子，将 res + 1，i 和 j 指针同时向右移动一位，去满足下一位孩子
    • 否则，说明该饼干不能满足当前的孩子，则将 j 指针右移，寻找可以满足当前孩子的胃口且尺寸最小的饼干
  • 最后返回 res 即可

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int m = g.length;
        int n = s.length;
        int i = 0;
        int j = 0;
        int res = 0;
        while (i < m && j < n) {
            if (g[i] <= s[j]) {
                res++;
                i++;
                j++;
            } else {
                j++;
            }
        }
        return res;
    }
}