LeetCode 每日一题：分发饼干 - Keep It Simple, Stupid.

题目

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

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

分发饼干

解法1：单排序

func findContentChildren(g []int, s []int) int {
   if len(s) == 0 {
      return 0
   }
   sort.Ints(s)
   amount := 0
   for _, w := range g {
      ii := sort.SearchInts(s, w)
      if ii != len(s) {
         amount++
         s = append(s[:ii], s[ii+1:]...)
      }
   }
   return amount
}

先对 s 进行排序，然后遍历孩子的胃口值，搜索离胃口值最近的饼干；
搜到则次数 +1，并把饼干从 s 中删除。

解法2：双排序

对 s 和 g 进行排序，然后拿饼干去匹配孩子的胃口。

func findContentChildren(g []int, s []int) int {
   if len(s) == 0 {
      return 0
   }
   sort.Ints(s)
   sort.Ints(g)
   gi, si := 0, 0
   for {
      if g[gi] <= s[si] {
         gi++
         si++
      } else {
         si++
      }
      if gi == len(g) || si == len(s) {
         break
      }
   }
   return gi
}

func findContentChildren(g []int, s []int) int {
   if len(s) == 0 {
      return 0
   }
   sort.Ints(s)
   sort.Ints(g)
   count := 0
   for _, sv := range s {
      if sv >= g[count] {
         count++
         if count == len(g) {
            break
         }
      }
   }
   return count
}

以上三种解法执行结果均为：执行用时：36 ms，内存消耗：6.2 MB
（我还以为后面两个会比第一个好点 =_=）