Tác giả: Lê Trung Kiên lớp java 08
Email: lekien.2803.cg@gmail.com
SĐT: 0942096947
Link bài toán: https://leetcode.com/problems/kids-with-the-greatest-number-of-candies/
1. Mở đầu
Xin chào các bạn, mình viết ra bài viết này để chia sẻ phương pháp giải cũng như tư duy của mình về bài toán này của leetcode. Phương pháp của mình có thể không phải là tối ưu nhất, tuy nhiên mình sẽ phân tích, chia nhỏ bài toán ra thành các module nhỏ hơn để dễ giải quyết cũng như giúp các bạn hiểu được các yêu cầu mà bài toán đưa ra.
2. Đề bài
Có một đám nhóc đang chơi với nhau, mỗi đứa đều có số kẹo riêng của mình. Cho một mảng số nguyên candies, trong đó mỗi phần tử candies[i] biểu thị cho số kẹo của mỗi đứa trẻ. Cùng với đó là số nguyên extraCandies là số kẹo bạn đang có để cho đám nhóc kia.
Trả về kết quả là một danh sách dạng boolean result có kích thước n, với cách làm là: Bạn dùng số kẹo extraCandies cho mỗi đứa trẻ, cho xong rồi mà đứa trẻ nào có số kẹo mới đó lớn hơn số kẹo ban đầu của những đứa khác thì trả về true, còn không thì trả về false.
Lưu ý rằng có khả năng có nhiều đứa trẻ có số lượng kẹo lớn hơn những đứa khác.
Điều kiện:
n == candies.length.2 <= n <= 100.1 <= candies[i] <= 100.1 <= extraCandies <= 50.
Bài toán minh họa 1:
Input: candies = [2,3,5,1,3], extraCandies = 3
Output: [true,true,true,false,true]
Explanation: If you give all extraCandies to:
- Kid 1, they will have 2 + 3 = 5 candies, which is the greatest among the kids.
- Kid 2, they will have 3 + 3 = 6 candies, which is the greatest among the kids.
- Kid 3, they will have 5 + 3 = 8 candies, which is the greatest among the kids.
- Kid 4, they will have 1 + 3 = 4 candies, which is not the greatest among the kids.
- Kid 5, they will have 3 + 3 = 6 candies, which is the greatest among the kids.
Bài toán minh họa 2:
Input: candies = [4,2,1,1,2], extraCandies = 1
Output: [true,false,false,false,false]
Explanation: There is only 1 extra candy.
Kid 1 will always have the greatest number of candies, even if a different kid is given the extra candy.
Bài toán minh họa 3:
Input: candies = [12,1,12], extraCandies = 10
Output: [true,false,true]
3. Phân tích
Ố kề! Bài này cũng không quá khó đâu mọi người. Chúng ta sẽ có hai công việc chính cần làm để giải quyết bài toán này:
- Đầu tiên là tìm được đứa có nhiều kẹo nhất trong đám thôi. Tại sao á? Tại vì đề bài nói rằng, đứa nào mà được bạn cho thêm kẹo
extraCandies, số kẹo lúc ấy mà lớn hơn số kẹo ban đầu của những đứa khác thì mới tính làtrue. Vậy thì suy ra chỉ cần kiếm đứa có nhiều kẹo nhất trong đám, lấy số ấy làm mốc, sau khi cho kẹo, đứa nào có số lượng kẹo lớn hơn hoặc bằng cái mốc đó thì ta trả vềtrue, không thìfalsethôi. - Tiếp theo, sau khi kiểm tra ở trên rồi thì ta nhét cái
truehoặcfalseấy vào danh sáchresulttheo thứ tự giống với mảngcandies, thế là xong!
Triển bước tiếp theo thôi!
4. Code chạy bằng cơm
Công việc đầu tiên chúng ta cần làm là tìm ra được đứa có số kẹo lớn nhất đúng không ạ? Vậy thì ta sẽ cần một biến số nguyên max chứa kết quả là số kẹo lớn nhất đó. Một cái danh sách dạng Boolean tên res để chứa kết quả trả về:
Tiếp theo, để tìm được đứa có số lượng kẹo lớn nhất, ta cần một vòng lặp foreach để gán số kẹo lớn nhất vào biến max ở trên. Ở đây chúng ta sẽ dùng method Math.max() để tìm ra số lớn hơn giữa hai số:
Sau khi có được số kẹo lớn nhất rồi, ta sẽ đem nó so sánh với số kẹo mỗi đứa đã được cho thêm extraCandies, đứa nào lớn hơn hoặc bằng thì trả về true, còn không thì là false, rồi sử dụng method add() để đưa kết quả vào danh sách res ở trên. Tuy nhiên, danh sách của chúng ta cũng phải có thứ tự tương ứng với số kẹo trong mảng candies, vậy nên ta sẽ làm một vòng lặp qua mảng candies, kiểm tra đến đứa nào thì thêm luôn kết quả vào res, như vậy thì thứ tự sẽ giống nhau:
Done!
5. Code chạy bằng máy
Cơ bạn code của chúng ta sẽ như sau:
public List<Boolean> kidsWithCandies(int[] candies, int extraCandies) {
List<Boolean> res = new ArrayList<>();
int max = 0;
for (int i : candies) {
max = Math.max(max, i);
}
for (int i : candies) {
if (i + extraCandies >= max) {
res.add(true);
}
else{
res.add(false);
}
}
return res;
}
Tuy nhiên, vì đoạn (i + extraCandies >= max) trả về kết quả dạng true/false cho nên ta có thể gán luôn vào method add() để nó vừa kiểm tra vừa thêm vào luôn cho chúng ta, khi ấy code của chúng ta sẽ gọn hơn nhiều:
public List<Boolean> kidsWithCandies(int[] candies, int extraCandies) {
List<Boolean> res = new ArrayList<>();
int max = 0;
for (int i : candies) {
max = Math.max(max, i);
}
for (int i : candies) {
res.add(i+extraCandies >= max);
}
return res;
}
6. Kết thúc
Qua bài viết này, mình đã chia sẻ cho các bạn cách mình tư duy khi giải bài tập trên leetcode. Hi vọng bài viết giúp ích cho các bạn trong cách tư duy để giải các bài tập khác. Xin cám ơn các bạn đã dành thời gian đọc và theo dõi. Peace!!!
Bình luận