救生艇 -- LeetCode -- 8.26

救生艇

  第 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)

思路就是贪心:

  就是先让一个人上船,看看省的位置还够不够另一个人来,尽可能把位置坐满;比如体重为 a 的 上船就看看有没有 limit - a 体重的人跟他一起,没有找 limit - a - 1的,等等等。

自己做的,刚开始想的数据不大,可以用空间换时间,能AC!

class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        int book[30005];
        int ans = people.size();
        memset(book,0,sizeof(book));
        for(int i = 0; i < people.size(); i++){
            book[people[i]]++;
        }
        for(int i = 0; i < people.size(); i++){
            if(book[people[i]] <= 0)continue;
            int x = limit - people[i];
            book[people[i]]--;
            while(x > 0){
                if(book[x] > 0){
                    book[x]--;
                    ans--;
                    break;
                }
                x--;
            }
        }
        return ans;
    }
};

救生艇 -- LeetCode -- 8.26

还有更简便的,现将原数组排序,然后两头搜索,由于是要排序,所以时间复杂度要 nlogn;

class Solution {
public:
    int numRescueBoats(vector<int>& people, int limit) {
        int ans = 0;
        int l = 0, r = people.size() - 1;
        sort(people.begin(),people.end());
        while(l <= r){
            if(people[l] + people[r] <= limit)l++;
            r--;
            ans++;
        }        
        return ans;
    }
};

救生艇 -- LeetCode -- 8.26

救生艇 -- LeetCode -- 8.26

这看着是真迷糊,可能大家写的时空复杂度都一样;

 

上一篇:设计模式(八)装饰模式


下一篇:JSP详解