• 0

  • 490

救生艇的逃生

1 month ago

今天为大家分享一道关于 “救生艇” 的题目。

话不多说,直接看题吧。

01、题目示例

第881题:救生艇
第 i 个人的体重为 people[i],每艘船可以承载的最大重量为 limit。每艘船最多可同时载两人,但条件是这些人的重量之和最多为 limit。返回载到每一个人所需的最小船数。(保证每个人都能被船载)。

示例 1:

输入:people = [1,2], limit = 3
输出:1
解释:1 艘船载 (1, 2)
复制代码

示例 2:

输入:people = [3,2,2,1], limit = 3
输出:3
解释:3 艘船分别载 (1, 2), (2) 和 (3)
复制代码

示例 3:

输入:people = [3,5,3,4], limit = 5
输出:4
解释:4 艘船分别载 (3), (3), (4), (5)
复制代码

提示:

  • 1 <= people.length <= 50000

  • 1 <= people[i] <= limit <= 30000

02、题目分析

这不是一道算法题,这是一个脑筋急转弯。

一个船最多可以装两个人,并且不能把船压垮。同时要求把这些人可以统统装下的最小船数。用脚趾头也可以想到,我们需要尽最大努力的去维持一个床上得有两个人。。哦,不,船上。这是什么思想?Bingo,贪心。

思路很简单:

  1. 我们首先需要让这些人 根据体重进行排序。

  2. 同时 维护两个指针,每次让最重的一名上船,同时让最轻的也上船。(因为最重的要么和最轻的一起上船。要么就无法配对,只能自己占用一艘船的资源)

03、JAVA示例

根据分析,得到代码:

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int i = 0, j = people.length - 1;
        int ans = 0;
 
        while (i <= j) {
            ans++;
            if (people[i] + people[j] <= limit)
                i++;
            j--;
        }
        return ans;
    }
}
复制代码

04、GO示例

GO代码其实也一样:

func numRescueBoats(people []int, limit int) int {
    sort.Ints(people)
    ans :=0
    i, j :=00len(people) - 1
    for i <= j {
        if people[i] + people[j] <= limit {
            i++
        } else{
            j--
        }
        ans++
    }
    return ans
}
复制代码

05、题目扩展

这里肯定马上就有细心的读者会问!为什么你每次是让最瘦的和最胖的来凑一对。而不是放弃掉这个最瘦的,去找一个逼近limit体重的人来乘船呢?这里要注意题目,因为题中已经告诉了, 一艘船仅能坐两人。所以去找一个逼近limit体重的人是没有意义的。

但是,这里并不妨碍我们将此题扩展进行思考。这里留下疑问,如果我们不对船上的人数进行限制,那么应该如何来完成本题呢?大家可以尝试代码练习一下。


我把我写的所有题解都整理成了一本电子书,每道题都配有完整图解。点击即可下载

和小浩学算法

免责声明:文章版权归原作者所有,其内容与观点不代表Unitimes立场,亦不构成任何投资意见或建议。

程序员

490

Relevant articles

未登录头像

No more data