This is the 26th day of my participation in the August More Text Challenge

Leetcode – 881 – lifeboat

[Blog link]

The path to learning at 🐔

The nuggets home page

[B].

The ith person’s weight is people[I], and the maximum weight each ship can carry is limit.

Each boat can carry up to two people at a time, provided that the combined weight of these people is maximum limit.

Return the number of boats needed to carry each person. (Make sure everyone gets on the boat).

Example 1:

Input: people = [1,2], limit = 3Copy the code

Example 2:

Input: people = [3,2,2,1], limit = 3Copy the code

Example 3:

Input: people = [3,5,3,4], limit = 5Copy the code

Tip:

• 1 <= people.length <= 50000
• 1 <= people[i] <= limit <= 30000

Related Topics

• greedy
• An array of
• Double pointer
• The sorting
• 👍 👎 0 125

[答 案]

Leetcode topic link

[making address]

Code link

[introduction]

Idea 1: greed + big root pile

• Scan from maximum by large root heap sort
• Put in the boat if the limit is exceeded directly RES +=1
• No more than the second largest (if not, go all the way down to the elements that are less than or equal to limit)
• And then you store a stack or queue where the elements that don’t meet the criteria are put back into the big root heap
• TLE (70/78) greedy algorithm is complicated

public int numRescueBoats(int[] people, int limit) {
            PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    returno2 - o1; }});for (int person : people
            ) {
                priorityQueue.add(person);
            }
            Stack<Integer> stack = new Stack<>();
            int res = 0;
            while(! priorityQueue.isEmpty()) {int temp = priorityQueue.poll();
                if (temp >= limit) {
                    res += 1;
                    continue;
                }
                while(! priorityQueue.isEmpty() && temp + priorityQueue.peek() > limit) {int value = priorityQueue.poll();
                    stack.add(value);
                }
                if(! priorityQueue.isEmpty()) { priorityQueue.poll(); } res +=1;
                while (!stack.isEmpty()) {
                    priorityQueue.add(stack.pop());
                }
            }
            return res;
        }
Copy the code

• Time complexity
  $O(n*lgn+n^2)$
• Spatial complexity
  $O(n)$

Idea 2: Greed + linked lists

• Sort without a big root heap
• Same idea
• Also TLE (75/78)

public int numRescueBoats(int[] people, int limit) {
            Arrays.sort(people);
            int res = 0;
            boolean[] vis = new boolean[people.length];
            for (int i = people.length - 1; i >= 0; i--) {
                if (vis[i]) {
                    continue;
                }
                vis[i] = true;
                if (people[i] >= limit) {
                    res++;
                    continue;
                }
                int des = limit - people[i];
                int j = i - 1;
                while (j >= 0) {
                    if(people[j] <= des && ! vis[j]) { vis[j] =true;
                        break;
                    }
                    j--;
                }
                res++;
            }
            return res;
        }
Copy the code

• Time complexity
  $O(n*lgn +n^{2})$
• Spatial complexity
  $O(n)$

Idea 3: Greed + dichotomy

• The main is greedy logic to complex, binary search elements too

List<Integer> unVis = new ArrayList<>();

        public int numRescueBoats(int[] people, int limit) {
            Arrays.sort(people);
            int res = 0;
            for (int i : people
            ) {
                unVis.add(i);
            }

            while(! unVis.isEmpty()) {int i = unVis.size() - 1;
                if (unVis.get(i) >= limit) {
                    res++;
                    unVis.remove(i);

                    continue;
                }
                findAndRmJ(i, limit - unVis.get(i));
                unVis.remove(unVis.size() - 1);
                res++;
            }
            return res;
        }

        public void findAndRmJ(int i, int des) {

            if (i <= 0) {
                return;
            }
            int l = 0, r = i - 1;
            while (l < r) {
                int mid = (l - r + 1) / 2 + r;
                if (unVis.get(mid) <= des) {
                    l = mid;
                } else {
                    r = mid - 1; }}if (unVis.get(r) <= des) unVis.remove(r);
        }
Copy the code

• Time complexity
  $O(n*lgn)$
• Spatial complexity
  $O(n)$

Idea four: greedy algorithm optimization

• I think it is complicated, take the lightest and heaviest each time, there is no need to binary search for the maximum complement element that meets the condition

public int numRescueBoats(int[] people, int limit) {
    Arrays.sort(people);
    int l = 0, r = people.length - 1, res = 0;
    while (l < r) {
        if (people[r] >= limit || people[l] + people[r] > limit) {
            r--;
            res++;
        } else{ r--; l++; res++; }}if (l ==r){
        res++;
    }
    return res;
}
Copy the code

• Time complexity
  $O(n*lgn+n)$
• Spatial complexity
  $O(n)$