分发饼干 -455

贪心算法问题

介绍

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i，都有一个胃口值 gi，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 sj 。如果 sj >= gi ，我们可以将这个饼干 j 分配给孩子 i，这个孩子会得到满足。

你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

注意：你可以假设胃口值为正。一个小朋友最多只能拥有一块饼干。

示例 1:

输入: [1,2,3], [1,1]

输出: 1

解释:
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。

示例 2:

输入: [1,2], [1,2,3]

输出: 2

解释:
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.

代码

function findCookieChildren (children: number[], cookies: number[]) {
  // 对孩子和饼干按从小到大顺序进行排序
  children = children.sort((a, b) => a - b)
  cookies = cookies.sort((a, b) => a - b)
  // i 代表孩子的索引
  let i = 0
  // j 代表饼干的索引
  let j = 0
  // count 代表被满足孩子的数量
  let count = 0
  // 只要还有孩子且还有饼干，就继续尝试满足孩子
  while(i < children.length && j < cookies.length) {
    // 因为从小到大排序过，所以从最小胃口的孩子开始，尝试满足孩子
    if(children[i] <= cookies[j]) {
      // 如果能满足，就消耗掉孩子、饼干，并且 count 加一
      i ++
      j ++
      count ++
    } else {
      // 否则就用更大的饼干尝试满足孩子
      j ++
    }
  }
  return count
}

// in-source test suites
if (import.meta.vitest) {
  const { it, expect } = import.meta.vitest
  
  it('test', () => {
    expect(findCookieChildren([1,2], [1,2,3])).toBe(2)
    expect(findCookieChildren([1,2,3], [1,1])).toBe(1)
  })  
}

LeetCode 链接

https://leetcode.cn/problems/assign-cookies/

分发饼干 -455 ​

介绍 ​

代码 ​

LeetCode 链接 ​

分发饼干 -455

介绍

代码

LeetCode 链接