thảo luận Leetcode mỗi ngày

Java: 
class Solution {
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int boats = 0;

        int left = 0, right = people.length - 1;

        while (left <= right) {
            if (people[left] + people[right] <= limit) {
                left++;
                right--;
            } else {
                right--;
            }
            boats++;
        }

        return boats;
    }
}
 
Python: 
class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        count = 0
        people.sort()
        
        l, r = 0, len(people) - 1
        while (l <= r):
            if people[r] + people[l] <= limit:
                l += 1
            r -= 1
            count += 1
        return count
 
Greedy, nhẹ nhất cho đi với nặng nhất miễn sao đáp ứng được limit
JavaScript: 
function numRescueBoats(people: number[], limit: number): number {
    let res = 0;
    people.sort((a,b) => a-b);
    let l = 0, r = people.length - 1;
    while (l <= r) {
        res++;
        if (people[l] + people[r] <= limit) l++;
        r--;
    }
    return res;
};
 
Kazaizaika said:
Muốn luyệt leetcode thì nên dùng ngôn ngữ nào vậy các bác ? E hiện tại mới biết python, c++ với java thôi :byebye::byebye:

via theNEXTvoz for iPhone
Click to expand...
Bác dùng cái nào cũng được ấy mà. Nó là 3 ngôn ngữ dùng phổ biến nhất trên LC rồi :big_smile:
Nếu có lời khuyên thì dùng Python, code ngắn, ko lo exceed dữ liệu, nhiều tool ngon.
Người dùng @freedom.9 cũng đã từ C# nhảy sang Python và ko hề quay đầu lại :hungry::shame:
 
Code: 
public class Solution {
    public int NumRescueBoats(int[] people, int limit) {
       Array.Sort(people);
       int counter = 0;
       int leftMost = 0;
       for(int i = people.Length - 1; (leftMost <= i && i >= 0);i--){
            if(people[i] >= limit){
                counter += 1;
            }
            else if(people[i] + people[leftMost] <= limit){
                counter += 1;
                leftMost += 1;
            }else {
                counter += 1;
            }
       }
       return counter;
    }
}
 
Last edited:
Kazaizaika said:
Muốn luyệt leetcode thì nên dùng ngôn ngữ nào vậy các bác ? E hiện tại mới biết python, c++ với java thôi :byebye::byebye:

via theNEXTvoz for iPhone
Click to expand...
Cả ba lang trên đều phổ biến, dùng cái nào quen thuộc nhất ấy.
Quan trọng là ý tưởng và trình bày được cho người ta hiểu
:byebye:

Bài hôm nay medium nhưng khá dễ.
Xem solution thấy mấy thánh optimize dùng Bucket sort
Code: 
class Solution {
       public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int left = 0;
        int right = people.length - 1;
        int ans = 0;
        while (left <= right) {
            if (people[left] + people[right] <= limit) {
                left++;
            }

            right--;
            ans++;
        }

        return ans;
    }
}
 
Last edited:
billy_don said:
Java: 
class Solution {
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int boats = 0;

        int left = 0, right = people.length - 1;

        while (left <= right) {
            if (people[left] + people[right] <= limit) {
                left++;
                right--;
            } else {
                right--;
            }
            boats++;
        }

        return boats;
    }
}
Click to expand...
để chử 2 pointer bên ngoài cái code nó hiện ra trong đầu luôn, ko cho thời gian suy nghỉ nữa
yp40V27.png
jdzp8kF.gif
lần sau bỏ hint vào bên trong spoiler lun đi bác
 
Java: 
  public static int numRescueBoats(int[] people, int limit) {
    Arrays.sort(people);
    int pointerMin = 0, pointerMax = people.length - 1;
    int ans = 0;
    while (pointerMin <= pointerMax) {
      if (people[pointerMin] + people[pointerMax] <= limit) {
        ans++;
        pointerMin++;
        pointerMax--;
      } else {
        pointerMax--;
        ans++;
      }
    }
    return ans;
  }
 
Code: 
impl Solution {
    pub fn num_rescue_boats(mut people: Vec<i32>, limit: i32) -> i32 {
        let mut freq = vec![0i32; 3 * 10usize.pow(4) + 1];
        let npeople = people.len();

        for i in 0..npeople {
            freq[people[i] as usize] += 1;
        }

        let mut k = 0;
        for i in 0..(freq.len()) {
            for j in k..(k + freq[i]) {
                people[j as usize] = i as i32;
            }

            k += freq[i];
        }

        let mut l = 0;
        let mut r = npeople - 1;
        let mut count = 0;

        while (l < r) {
            count += 1;

            if (people[l] + people[r] <= limit) {
                l += 1;
                r -= 1;
            } else {
                r -= 1;
            }
        }

        if (l == r) {
            count += 1;
        }

        count
    }
}
 
Hỏi ngu tí, giờ còn ai dùng Python 2 không nhỉ, thấy Leetcode vẫn hỗ trợ Python 2 nhưng t toàn dùng Python 3 :D
Python: 
class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        # count people by weight
        count_weight = [0] * (limit + 1)
        for person in people:
            count_weight[person] += 1
            
        result = 0
        
        # carry people with a minimum weight of limit / 2
        lighter = limit // 2
        for heavier in range (limit - lighter, limit+1):
            while (count_weight[heavier] > 0):
                result += 1
                count_weight[heavier] -= 1
                
                # add a person in this boat if possible
                lighter = min(lighter, limit - heavier)
                while (lighter >= 0):
                    if count_weight[lighter] > 0:
                        count_weight[lighter] -= 1
                        break
                    lighter -= 1
                    
        # carry other people
        result += (sum(count_weight) + 1) // 2
        
        return result
 
C#: 
public class Solution
{
    public int NumRescueBoats(int[] people, int limit)
    {
        Array.Sort(people);
        int left = 0;
        int right = people.Length - 1;

        int result = 0;
        while (left <= right)
        {
            int remain =  limit - people[right];
            if (people[left] <= remain)
            {
                left++;
            }
            right--;
            result++;
        }

        return result;
    }
}

freedom.9 said:
C# trash language mà :shame:

via theNEXTvoz for iPhone
Click to expand...
á à :what:
 
Aluminum21 said:
C#: 
public class Solution
{
    public int NumRescueBoats(int[] people, int limit)
    {
        Array.Sort(people);
        int left = 0;
        int right = people.Length - 1;

        int result = 0;
        while (left <= right)
        {
            int remain =  limit - people[right];
            if (people[left] <= remain)
            {
                left++;
            }
            right--;
            result++;
        }

        return result;
    }
}


á à :what:
Click to expand...
Muốn lên level thì đổi qua Python ngay :shame: toy đổi từ python rating tăng từ 1k5 lên 1k8 rồi :shame:

via theNEXTvoz for iPhone
 
một solution khác ngu muội hơn:

Code: 
use std::cmp;

impl Solution {
    pub fn num_rescue_boats(mut people: Vec<i32>, limit: i32) -> i32 {
        let mut freq = vec![0i32; 3 * 10usize.pow(4) + 1];
        let npeople = people.len();

        for i in 0..npeople {
            freq[people[i] as usize] += 1;
        }

        let mut l = 0;
        let mut r =  3 * 10usize.pow(4);
        let mut count = 0;
        let ulimit = limit as usize;

        while (l < r) {
            if (l + r <= ulimit) {
                let min = cmp::min(freq[l], freq[r]);
                count += min;

                freq[l] -= min;
                freq[r] -= min;
            } else {
                count += freq[r];
                freq[r] = 0;
            }

            if (freq[l] == 0) {
                l += 1;
            }

            if (freq[r] == 0) {
                r -= 1;
            }
        }

        if (l == r) {
            if (l * 2 <= ulimit) {
                count += freq[l] / 2 + (freq[l] % 2);
            } else {
                count += freq[l];
            }
        }

        count
    }
}
 
Python: 
class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        i, j, b = 0, len(people) - 1, 0
        while i <= j:
            if people[i] + people[j] <= limit:
                i += 1
                
            j -= 1
            b += 1
        
        return b
 
JavaScript: 
var numRescueBoats = function(people, limit) {
    people.sort((u, v) => u - v);
    let ans = 0;
    for (let i = 0, j = people.length - 1; i <= j;) {
        if (i === j || people[i] + people[j] <= limit) {
            i++; j--;
        } else {
            j--;
        }
        ans++;
    }
    return ans;
};
 
small-lambda said:
một solution khác ngu muội hơn:

Code: 
use std::cmp;

impl Solution {
    pub fn num_rescue_boats(mut people: Vec<i32>, limit: i32) -> i32 {
        let mut freq = vec![0i32; 3 * 10usize.pow(4) + 1];
        let npeople = people.len();

        for i in 0..npeople {
            freq[people[i] as usize] += 1;
        }

        let mut l = 0;
        let mut r =  3 * 10usize.pow(4);
        let mut count = 0;
        let ulimit = limit as usize;

        while (l < r) {
            if (l + r <= ulimit) {
                let min = cmp::min(freq[l], freq[r]);
                count += min;

                freq[l] -= min;
                freq[r] -= min;
            } else {
                count += freq[r];
                freq[r] = 0;
            }

            if (freq[l] == 0) {
                l += 1;
            }

            if (freq[r] == 0) {
                r -= 1;
            }
        }

        if (l == r) {
            if (l * 2 <= ulimit) {
                count += freq[l] / 2 + (freq[l] % 2);
            } else {
                count += freq[l];
            }
        }

        count
    }
}
Click to expand...
Cách này tối ưu hay hơn đấy chứ
NlogN thì nhìn ra greedy xong là cứ thế code chả cần nghĩ gì
Cách này tốn time tốn sức tốn chất xám để cài đặt hơn
 
Python: 
class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        sortPeople, size = sorted(people), len(people)
        start, result, end = 0, 0, size - 1
        while start <= end:
            if sortPeople[start] + sortPeople[end] <= limit:
                start += 1
            end -= 1
            result += 1
        return result
 
GD-Cuong said:
Cách này tối ưu hay hơn đấy chứ
NlogN thì nhìn ra greedy xong là cứ thế code chả cần nghĩ gì
Cách này tốn time tốn sức tốn chất xám để cài đặt hơn
Click to expand...
bài này giải đơn giản là được rồi, tốn sức optimize làm gì, nên mới gọi là ngu muội :D
 

Similar threads

hatayquelua
thắc mắc Cần kiến thức gì để được nhận thực tập Dev
2 3
Replies
40
Views
1K
thapnhat111
thapnhat111
L
kiến thức 100 ngày tự học CNTT (AI&Data)
Replies
4
Views
239
shazam
shazam
Build Back Better
  • Locked
Bỡn cợt cô giáo lớn tuổi trên TikTok, giới trẻ đang làm gì vậy?
6 7 8
Replies
154
Views
9K
Wind.G
Wind.G
trustnetvn
thảo luận Ríp tồ: Cho các Fan cuồng BTC, ETH
Replies
0
Views
73
trustnetvn
trustnetvn
T
thắc mắc Làm thế nào để tự động hóa việc thiết lập môi trường dev khi khởi động Windows?
Replies
15
Views
774
shazam
shazam

Share this page

Back
Top