Assign Cookies-K6K4.com

原题： https://leetcode.com/problems/assign-cookies/description/

题意： 假设你是一位很赞的家长想要给孩子一些饼干。但是，你只能至多给每个孩子一个饼干。孩子i的贪婪因子为gi，意思是他所满意的饼干的最小尺寸；每一个饼干j的尺寸为sj。如果sj >= gi，我们就可以把饼干j分给孩子i，然后孩子i会很满意。你的目标是最大化分到饼干的孩子的个数。

约定： （1）可以假设贪婪因子都是正数（2）不可以为一个孩子分配多个饼干。

例子：

例一：
输入: [1,2,3], [1,1] 
输出: 1
说明: 你有3个孩子和2个饼干。 3个孩子的贪婪因子分别是1，2，3。即使你有2个饼干，因为它们的大小都是1，所以你只能满足贪婪因子为1的孩子。
你需要输出 1。

例二:
输入: [1,2], [1,2,3]
输出: 2
说明: 你有2个孩子和3个饼干。 2个孩子的贪婪因子分别是1，2。你有3个饼干，它们的大小足以满足所有的孩子。
你需要输出2。

标签：饼干、孩子、贪婪、因子、gi、面试

猜你感兴趣的圈子：

LeetCode交流圈

星空

2017-08-18 18:20:52 1楼#1层

class Solution(object):
    def findContentChildren(self, g, s):
        """
        :type g: List[int]
        :type s: List[int]
        :rtype: int
        """
        cnt = 0
        i, j = len(g) - 1, len(s) - 1
        g, s = sorted(g), sorted(s)
        while min(i, j) >= 0:
            if g[i] <= s[j]:
                cnt += 1
                j -= 1
            i -= 1
        return cnt

星空

2017-08-18 18:23:21 2楼#1层

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

星空

2017-08-18 18:24:00 3楼#1层

public class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        
        int pointG = 0;
        int pointS = 0;
        
        while (pointG<g.length && pointS<s.length) {
            if (g[pointG]<=s[pointS]) {
                pointG++;
                pointS++;
            } else {
                pointS++;
            }
        }
        
        return pointG;
    }
}

取消

回复

推荐圈子

LeetCode交流圈