C/C++教程

leetcode-455. 分发饼干

本文主要是介绍leetcode-455. 分发饼干,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目

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

解法

直觉思路
先排序,然后根据胃口最小的孩子找能满足的最小的饼干

class Solution {

    /**
     * @param Integer[] $g
     * @param Integer[] $s
     * @return Integer
     */
    function findContentChildren($g, $s) {
        sort($g);
        sort($s);
    
        $ret = 0;
		$sKey = 0;
        foreach ($g as $gItem) {
            while(($sItem = reset($s)) !== false) {
                if ($sItem >= $gItem) {
                    $ret ++;
                    array_shift($s);
                    break;
                } else {
                    array_shift($s);
                }
            }
        }
        
        return $ret;
    }
}

因为 array_shift 会对数组做调整的原因,性能会比较差一点,可以做一点小优化

class Solution {
    
    /**
     * @param Integer[] $g
     * @param Integer[] $s
     * @return Integer
     */
    function findContentChildren($g, $s) {
        sort($g);
        sort($s);
        
        $ret  = 0;
        $sKey = 0;
        foreach ($g as $gItem) {
            for ($j = $sKey; $j < count($s); $j++) {
                $sKey++;
                if ($s[$j] >= $gItem) {
                    $ret++;
                    break;
                }
            }
        }
        
        return $ret;
    }
}
这篇关于leetcode-455. 分发饼干的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!