X

LEETCODE 1196. How Many Apples Can You Put into the Basket 解题思路分析

题目大意:

最多可以买到的苹果数量

有一些苹果,arr[i]代表第i个苹果的重量,你还有一个篮子,最多可以装5000单位重量的苹果。

请返回最多可以装进篮子多少个苹果。

示例1:

Input: arr = [100,200,150,1000]
Output: 4
Explanation: All 4 apples can be carried by the basket since their sum of weights is 1450.

示例2:

Input: arr = [900,950,800,1000,700,800]
Output: 5
Explanation: The sum of weights of the 6 apples exceeds 5000 so we choose any 5 of them.

提示:

  • 1 <= arr.length <= 10^3
  • 1 <= arr[i] <= 10^3

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1196

解题思路分析:

本题可以利用贪心算法,先将数组排序,然后由轻到重向篮子里放,直到总重量超过5000为止,所装下的苹果个数即是答案。

证明该贪心算法很容易,因为数组已经排序,没装进篮子的苹果重量一定大于等于当前篮子中任意一个,因此用剩下的去替换篮子中的苹果会得不偿失。

实现代码:

public int maxNumberOfApples(int[] arr) {
    Arrays.sort(arr);
    int basket=5000;
    for(int i=0;i<arr.length;i++){
        basket-=arr[i];
        if(basket<0) return i;
    }
    return arr.length;
}

本题解法执行时间为1ms。

Runtime: 1 ms, faster than 99.51% of Java online submissions for How Many Apples Can You Put into the Basket.

Memory Usage: 38.7 MB, less than 100.00% of Java online submissions for How Many Apples Can You Put into the Basket.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1196-how-many-apples-can-you-put-into-the-basket-解题思路分析/
Categories: leetcode
kwantong: