小浩算法改版了,大家看一下风格怎么样,还喜欢吗?所有的排版,绘图,文案,题解都是由小浩一人完成哦~ 今天为大家分享一道关于“救生艇”的题目。 话不多说,直接看题。 01 第881题:救生艇 第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,贪心。 思路很简单:
03 JAVA示例 根据分析,得到代码: 1//JAVA2class Solution {3 public int numRescueBoats(int[] people, int limit) {4 Arrays.sort(people);5 int i = 0, j = people.length - 1;6 int ans = 0;78 while (i <= j) {9 ans++;10 if (people[i] + people[j] <= limit)11 i++;12 j--;13 }14 return ans;15 }16} 04 GO示例 GO代码其实也一样: 1func numRescueans(people []int, limit int) int {2 sort.Ints(people)3 ans := 04 i, j := 0, len(people)-15 for i <= j {6 if people[i]+people[j] <= limit {7 i++8 }9 j--10 ans++11 }12 return ans13} 小浩申明 注:本系列所有教程中都不会用到复杂的语言特性,大家不需要担心没有学过相关语法。算法思想最重要,使用各语言纯属本人爱好。同时,所有代码均在leetcode上进行过测试运行,保证其严谨性! 05 题目扩展 这里肯定马上就有细心的读者会问!为什么你每次是让最瘦的和最胖的来凑一对。而不是放弃掉这个最瘦的,去找一个逼近limit体重的人来乘船呢?这里要注意题目,因为题中已经告诉了, 一艘船仅能坐两人。所以去找一个逼近limit体重的人是没有意义的。 但是,这里并不妨碍我们将此题扩展进行思考。这里留下疑问,如果我们不对船上的人数进行限制,那么应该如何来完成本题呢?大家可以尝试代码练习一下。 评论区留下你的思路~ |
|