LeetCode: Bărci pentru salvarea oamenilor

  • 1 minute de citit
  • 2 exemple de cod în Rust și Python

Disponibil și în English

Pe această pagină

Introducere

Salut tuturor! 👋

Am exersat în ultima vreme câteva dintre provocările zilnice de pe Leetcode și, deoarece m-am mutat recent pe Substack, am vrut să scriu prima mea postare aici 😁

Boats to Save People

Problema Boats to Save People se rezolvă folosind o abordare Greedy.

Se dă un număr de persoane și greutățile lor, împreună cu o limită de încărcare a bărcii.

Trebuie să aflați numărul de bărci necesare pentru a transporta oamenii. O barcă poate transporta cel mult două persoane odată.

Pentru a respecta această restricție, mai întâi sortăm vectorul cu greutățile, apoi încercăm să asociem cea mai grea persoană cu cea mai ușoară. Dacă greutatea lor totală este mai mică sau egală cu limita de încărcare, eliminăm cele două persoane din listă și adăugăm o unitate la numărul de bărci necesare.

Dacă nu putem forma perechea, o punem pe cea mai grea persoană în barcă și căutăm o altă pereche. Adăugăm și în acest caz o unitate la numărul de bărci necesare.

Soluția în Rust

impl Solution {    pub fn num_rescue_boats(people: Vec<i32>, limit: i32) -> i32 {        let mut i = 0;        let mut j = people.len() - 1;        let mut boats = 0;        let mut sorted_people = people;        sorted_people.sort_unstable();        while i <= j {            boats += 1;            if sorted_people[i] + sorted_people[j] <= limit {                i += 1            }            if j == 0 {                break            }            j -= 1;        }        return boats;    }}

Soluția în Python

class Solution:    def numRescueBoats(self, people: List[int], limit: int) -> int:        people_size = len(people)        if people_size == 1:            return 1        people.sort()        boats_needed = 0        i = 0        j = people_size - 1        while i <= j:            # Am găsit o pereche de persoane            if people[i] + people[j] <= limit:                boats_needed += 1                i += 1                j -= 1                continue            j -= 1            boats_needed += 1        return boats_needed

Vă mulțumesc că ați citit!