azl397985856 commented 2 years ago

455. 分发饼干

入选理由

暂无

题目地址

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

前置知识

暂无

题目描述

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 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.

for123s commented 2 years ago

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int numOfChildren = g.size(), numOfCookies = s.size();
        int count = 0;
        for (int i = 0, j = 0; i < numOfChildren && j < numOfCookies; i++, j++) {
            while (j < numOfCookies && g[i] > s[j]) {
                j++;
            }
            if (j < numOfCookies) {
                count++;
            }
        }
        return count;
    }
};

falsity commented 2 years ago

class Solution {
        public int findContentChildren(int[] g, int[] s) {
            int m = g.length, n = s.length;

            Arrays.sort(g);
            Arrays.sort(s);

            int count = 0;
            int cur = 0; // 饼干搜索标志位

            for (int i = 0; i < m; i++) {
                for (int j = cur; j < n; j++) {
                    if (g[i] <= s[j]) {
                        count++;
                        cur = ++j;
                        break; // 满足条件,下一位
                    } else {
                        continue; // 继续寻找符合条件饼干
                    }
                }
            }
            return count;

        }
    }

joriscai commented 2 years ago

思路

先排序，用尽量小的饼干并且能满足孩子
使用双指针，一个个尝试饼干是否符合孩子

代码

javascript

/*
 * @lc app=leetcode.cn id=455 lang=javascript
 *
 * [455] 分发饼干
 */

// @lc code=start
/**
 * @param {number[]} g
 * @param {number[]} s
 * @return {number}
 */
var findContentChildren = function(g, s) {
  // 先排序,尽量小并且能满足孩子
  g.sort((a, b) => a - b)
  s.sort((a, b) => a - b)

  let gi = 0
  let si = 0
  let res = 0
  while (gi < g.length && si < s.length) {
    // 能够满足时
    if (s[si] >= g[gi]) {
      gi++
      res++
    }

    // 不符合时要找饼干，符合则此饼干已经被使用了
    si++
  }
  return res
};
// @lc code=end

复杂度分析

时间复杂度：O(nlogn), 先是两次排序，2nlogn，最后再遍历一次，n。总花费是2nlogn+n，即O(nlogn)
空间复杂度：O(1)，常数空间

niuyibo0619 commented 2 years ago

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()
        n, m = len(g), len(s)
        i = j = count = 0

        while i < n and j < m:
            while j < m and g[i] > s[j]:
                j += 1
            if j < m:
                count += 1
            i += 1
            j += 1

        return count

时间复杂度：O（mlogm+nlogn）空间复杂度：O（logm+logn）

ysy0707 commented 2 years ago

思路：贪心算法

class Solution {
    //从胃口最小的孩子开始，拿最小的饼干试一下能不能满足他，如果不能满足，再找稍微大一点的，如果还不能满足就再找更大一点的
    public int findContentChildren(int[] g, int[] s) {
        //先对胃口值和饼干尺寸进行排序
        Arrays.sort(g);
        Arrays.sort(s);
        int count = 0;
        for(int j = 0; count < g.length && j < s.length; j++){
            //如果当前饼干能满足当前孩子的胃口值，count就加1，否则就继续查找更大的饼干
            if(g[count] <= s[j]){
                count++;
            }
        }
        return count;
    }
}

时间复杂度：O（NlogN）空间复杂度：O（1）

ZETAVI commented 2 years ago

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        if(g == null || s == null){
            return 0;
        }

        int res = 0;
        Arrays.sort(g);
        Arrays.sort(s);

        int i = 0;
        int j = 0;
        while(i < g.length && j < s.length){
            while(j < s.length && s[j] < g[i]){
                j++;
            }
            if(j < s.length && s[j] >= g[i]){
                res++;
                i++;
                j++;
            }
        }

        return res;
    }
}

复杂度分析

时间复杂度:$ O(n*logn) $ 空间复杂度:$ O(1) $

ZETAVI commented 2 years ago

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        if(g == null || s == null){
            return 0;
        }

        int res = 0;
        Arrays.sort(g);
        Arrays.sort(s);

        int i = 0;
        int j = 0;
        while(i < g.length && j < s.length){
            while(j < s.length && s[j] < g[i]){
                j++;
            }
            if(j < s.length && s[j] >= g[i]){
                res++;
                i++;
                j++;
            }
        }

        return res;
    }
}

复杂度分析

时间复杂度:$ O(n*logn) $ 空间复杂度:$ O(1) $

flagyk5 commented 2 years ago

'''
时间 nlogn
空间 n
'''

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()
        i = j = ans = 0
        while i < len(g) and j < len(s):
            if s[j] >= g[i]: 
                i += 1
                j += 1
                ans += 1
            else: j += 1  
        return ans

biscuit279 commented 2 years ago

为啥是降序排序？

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        s.sort(reverse = True)
        g.sort(reverse = True)
        count = 0
        gi = 0 
        si = 0
        while gi < len(g) and si< len(s):
            if s[si] >= g[gi]:
                count += 1
                si += 1
            gi += 1
        return count

时间复杂度：O（nlogn）空间复杂度：O（1）

ru8dgj0001 commented 2 years ago

class Solution: def findContentChildren(self, g: List[int], s: List[int]) -> int: g.sort() s.sort() i = j = ans = 0 while i < len(g) and j < len(s): if s[j] >= g[i]: i += 1 j += 1 ans += 1 else: j += 1
return ans

taojin1992 commented 2 years ago

Understand:

1 <= g.length <= 3 * 10^4
0 <= s.length <= 3 * 10^4
1 <= g[i], s[j] <= 2^31 - 1

Are both arrays sorted?
smaller cookies for more satiable kids

maximize the number of your content children 

g:[1,2,3,8]
s:[1,5]
return 2

g:[1,2,3,8]
s:[2,5]
return 2

Plan & Match:

no cookie? return 0

preprocessing by sorting g, s

traverse the cookie and check on kids
if current cookie larger, satisfy the current kid, proceed to next kid and cookie
if kid larger, proceed to next cookie

the lengths can be different

Review:

g:[1,2]
s:[1,5]
return 2

g:[8,9]
s:[1,5]
return 0

g:[1,2,3,8]
s:[1,5]
return 2

g:[1,2,3,8]
s:[2,5]
return 2

Evaluate:

m = g.length, n = s.length

## Time: 
O(mlogm) + O(nlogn) + O(min(m,n))
= O(mlogm) + O(nlogn)

## Space:
O(1)

Code:

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        if (s.length == 0) return 0;
        Arrays.sort(g);
        Arrays.sort(s);
        int childIndex = 0; // start from the 1st kid
        int cookieIndex = 0;
        int count = 0;
        // note the && below
        while (childIndex < g.length && cookieIndex < s.length) {
            if (g[childIndex] <= s[cookieIndex]) {
                count++;
                childIndex++;
                cookieIndex++;
            } else {
                cookieIndex++;
            }
        }

        return count;
    }
}

shixinlovey1314 commented 2 years ago

Title:455. Assign Cookies

Question Reference LeetCode

Solution

Code

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(s.begin(), s.end());
        sort(g.begin(), g.end());
        int i = 0;
        int j = 0;

        while (i < g.size() && j < s.size()) {  
            if (g[i] <= s[j]) {
                i++;
                j++;
            }
            else
                j++;
        }

        return i;
    }
};

Complexity

Time Complexity and Explanation

o(nlogn)

Space Complexity and Explanation

O(1)

lihuiwen commented 2 years ago

代码

class Solution {
  public int findContentChildren(int[] g, int[] s) {
      if (s.length == 0) return 0;
      Arrays.sort(g);
      Arrays.sort(s);
      int childIndex = 0; // start from the 1st kid
      int cookieIndex = 0;
      int count = 0;
      // note the && below
      while (childIndex < g.length && cookieIndex < s.length) {
          if (g[childIndex] <= s[cookieIndex]) {
              count++;
              childIndex++;
              cookieIndex++;
          } else {
              cookieIndex++;
          }
      }

      return count;
  }
}

Lydia61 commented 2 years ago

分发饼干

思路

贪心算法

代码

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()
        n, m = len(g), len(s)
        i = j = count = 0

        while i < n and j < m:
            while j < m and g[i] > s[j]:
                j += 1
            if j < m:
                count += 1
            i += 1
            j += 1

        return count

复杂度分析

时间复杂度：O（mlogm+nlogn）
空间复杂度：O（logm+logn）

st2yang commented 2 years ago

思路

贪心
双指针

代码

python

class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
    ng, ns = len(g), len(s)
    if s == 0:
        return 0

    g.sort()
    s.sort()

    pg = ps = 0
    res = 0
    while pg < ng and ps < ns:
        if g[pg] <= s[ps]:
            res += 1
            pg += 1
            ps += 1
        else:
            ps += 1

    return res

复杂度

时间: O(nlogn+mlogm)
空间: O(1)

chun1hao commented 2 years ago

var findContentChildren = function(g, s) {
    s.sort((a,b)=> b-a)
    g.sort((a,b)=> b-a)
    let i=0
    let j=0
    let ans = 0
    while(i<g.length && j<s.length){
        if(s[j] >= g[i]){
            ans++
            i++
            j++
        }else{
            i++
        }
    }
    return ans
};

freesan44 commented 2 years ago

思路

贪心算法，两个数组设置各自指针，只要饼干大于最低小孩的要求，就双进1

关键点

代码

语言支持：Python3

Python3 Code:

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()
        gIndex,sIndex = 0, 0
        res = 0
        while gIndex != len(g) and sIndex != len(s):
            gElement = g[gIndex]
            sElement = s[sIndex]
            # 如果饼干满足小孩的胃口，就两个指针跳转
            if sElement >= gElement:
                res += 1
                gIndex += 1
                sIndex += 1
            else:#不满足就推移到下个饼干
                sIndex += 1
        return res

if __name__ == '__main__':
    # g = [1,2]
    # s = [1,2,3]
    g = [1, 2, 3]
    s = [1, 1]
    res = Solution().findContentChildren(g, s)
    print(res)

复杂度分析

令 n 为数组长度。

时间复杂度：$O(n)$
空间复杂度：$O(1)$

zhangyalei1026 commented 2 years ago

思路

排序 + 双指针，小朋友吃小饼干

代码

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g_sort = sorted(g)
        s_sort = sorted(s)
        i, j = 0, 0
        result = 0
        while i < len(g) and j < len(s):
            if g_sort[i] <= s_sort[j]:
                result += 1
                i += 1
                j += 1
            else:
                j += 1
        return result

复杂度分析

时间复杂度：O(nlogn) 空间复杂度: O(1)

mannnn6 commented 2 years ago

代码

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int start = 0;
        int count = 0;
        for (int i = 0; i < s.length && start < g.length; i++) {
            if (s[i] >= g[start]) {
                start++;
                count++;
            }
        }
        return count;
    }
}

复杂度

时间复杂度：O(NlogN) 空间复杂度: O(1)

hellowxwworld commented 2 years ago

int findContentChildren(vector<int>& gi, vector<int>& sj) {
    int res = 0;
    int i, j;
    sort(gi.begin(), gi.end());
    sort(sj.begin(), sj.end());
    for (i = 0, j = 0; i < gi.size() && j < sj.size(); ++j) {
        if (gi[i] <= sj[j])
            ++i;
    }
    return i;
}

AgathaWang commented 2 years ago

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        #贪心 双指针
        # tc: 因为用sort, O(nlogn)
        g.sort()
        s.sort()
        g_index = 0
        s_index = 0
        count = 0
        while g_index<len(g) and s_index<len(s):
            if g[g_index] <= s[s_index]:
                g_index += 1
                count+=1
            s_index+=1
        return count

shawncvv commented 2 years ago

思路

贪心算法

代码

JavaScript Code

/**
 * @param {number[]} g
 * @param {number[]} s
 * @return {number}
 */
const findContentChildren = function (g, s) {
  g = g.sort((a, b) => a - b);
  s = s.sort((a, b) => a - b);
  let gi = 0; // 胃口值
  let sj = 0; // 饼干尺寸
  let res = 0;
  while (gi < g.length && sj < s.length) {
    // 当饼干 sj >= 胃口 gi 时，饼干满足胃口，更新满足的孩子数并移动指针
    if (s[sj] >= g[gi]) {
      gi++;
      sj++;
      res++;
    } else {
      // 当饼干 sj < 胃口 gi 时，饼干不能满足胃口，需要换大的
      sj++;
    }
  }
  return res;
};

复杂度

时间复杂度：O(nlogn)
空间复杂度：O(1)

q815101630 commented 2 years ago

We need to ensure that the smallest cookie gives to the person with the smallest desire. This will ensure the maximal number of people get content with. This follows with the Greedy property.

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()
        cnt = 0
        i = 0
        for size in s:
            if i == len(g):
                return cnt
            if size >= g[i]:
                cnt += 1
                i+=1
        return cnt

Time: O(nlogn) Space: O(1)

leetcode-pp / 91alg-5-daily-check

【Day 65 】2021-11-13 - 455. 分发饼干 #84

455. 分发饼干

入选理由

题目地址

前置知识

题目描述

思路

代码

复杂度分析

复杂度分析

复杂度分析

为啥是降序排序？

Understand:

Plan & Match:

Review:

Evaluate:

Code:

Title:455. Assign Cookies

Question Reference LeetCode

Solution

Code

Complexity

Time Complexity and Explanation

Space Complexity and Explanation

代码

分发饼干

思路

代码

复杂度分析

思路

代码

复杂度

思路

关键点

代码

思路

代码

复杂度分析

代码

复杂度

思路

代码