美文网首页
贪心算法-Leetcode-455 Assign Cookies

贪心算法-Leetcode-455 Assign Cookies

作者: 墨平语凡 | 来源:发表于2017-10-01 17:13 被阅读0次
    """
    LeetCode-455 Assign Cookies(Greedy)
    https://leetcode.com/problems/assign-cookies/description/
    my:findContentChildren1
        跳出循环的条件较复杂, 没有2中简化
    findContentChildren2: http://blog.csdn.net/sscssz/article/details/53184465
    """
    
    
    def findContentChildren1(g, s):
        """
        :type g: List[int]
        :type s: List[int]
        :rtype: int
        """
        gsize = len(g)
        ssize = len(s)
        if gsize == 0 or ssize == 0:
            return 0
        g.sort()
        s.sort()
        sindex = 0
        count = 0
    
        for element in g:
            if sindex > ssize-1:
                break
            while element > s[sindex] and sindex <= ssize-1:
                sindex += 1
                if sindex > ssize-1:
                    break
            if sindex > ssize - 1:
                break
            if element <= s[sindex]:
                count += 1
                sindex += 1
        return count
    
    def findContentChildren2(g, s):
            g.sort(reverse=True)
            s.sort(reverse=True)
    
            i, j = 0, 0
            res = 0
    
            while j < len(s) and i < len(g):
                if s[j] >= g[i]:
                    res += 1
                    j += 1
                    i += 1
                else:
                    i += 1
            return res
    
    print(findContentChildren2([1, 2, 3], [1, 1]))
    
    

    相关文章

      网友评论

          本文标题:贪心算法-Leetcode-455 Assign Cookies

          本文链接:https://www.haomeiwen.com/subject/zxjaextx.html