2019年政府网站建设重点深圳公关公司

前言

救生艇属于贪心算法，解题之前条件一定要归纳好。题目中存在3个要求：

1.一艘船最多坐2人

2.船数要求最小

3.每艘船重量小于limit

意味着体重较轻的两人可以同乘一艘救生艇。

. - 力扣（LeetCode）

实现原理

1.重量大的有轻的可以配对，则可以配对同乘。

2.重量大的没有轻的可以配对，则单独乘。

3.涉及到轻重配对，最佳还是优先给予排序好的数据进行配对。

具体代码实现

class Solution {public int numRescueBoats(int[] people, int limit) {int res=0;Arrays.sort(people);int left=0;int right=people.length-1;while(left<=right){if(people[left]+people[right]<=limit){++left;}--right;++res;}return res;}
}

QA1: