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/richest-customer-wealth/
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
Cho bạn một mảng số nguyên kích thước m x n tên account, trong đó acount[i][j] là số tiền mà khách hàng thứ i đang cất trong ngân hàng tên j.
Hãy kiểm tra và trả về số tiền của khách hàng giàu có nhất.
Khách hàng giàu có nhất là khách hàng có nhiều tiền nhất, tính số tiền họ có trong tất cả các tài khoản ngân hàng của họ.
Điều kiện:
m == accounts.length.n == accounts[i].length.1 <= m, n <= 50.1 <= accounts[i][j] <= 100.
Ví dụ 1:
Input: accounts = [[1,2,3],[3,2,1]]
Output: 6
Explanation:
1st customer has wealth = 1 + 2 + 3 = 6
2nd customer has wealth = 3 + 2 + 1 = 6
Both customers are considered the richest with a wealth of 6 each, so return 6.
Ví dụ 2:
Input: accounts = [[1,2,3],[3,2,1]]
Output: 6
Explanation:
1st customer has wealth = 1 + 2 + 3 = 6
2nd customer has wealth = 3 + 2 + 1 = 6
Both customers are considered the richest with a wealth of 6 each, so return 6.
Ví dụ 3:
Input: accounts = [[2,8,7],[7,1,3],[1,9,5]]
Output: 17
3. Phân tích
Âu kê bài này không khó đâu các bạn. Giờ chúng ta chỉ cần tìm ra được khách giàu nhất thôi, mà muốn tìm được khách hàng giàu nhất thì tính tổng số tiền của họ. Bằng cách cộng tổng số tiền của họ trong các ngân hàng lại, bỏ vào một mảng. Sau đó chúng ta so chỉ cần so sánh toàn bộ số tiền trong cái mảng mới vừa tạo, số tiền nào lớn nhất thì đó là kết quả cần trả về thôi. Rất là dễ đúng không ạ?
4. Code chạy bằng cơm
Hãy dùng ví dụ account = [[1,2,3], [3,2,2]] ở trên để chạy code thử nhé:
Trước tiên chúng ta cần tạo một mảng mới để chứa số tiền của mỗi khách hàng thứ i, kích thước của mảng này đúng bằng với số khách hàng có trong mảng hai chiều account:
Giờ chúng ta cần một biến sum để chứa số tiền của mỗi khách hàng thứ i, với mỗi vòng lặp tại account[i], ta sẽ cộng toàn bộ số tiền họ có trong các ngân hàng tại account[j].
Tại vị trí khách hàng i = 0 thì khách hàng có tiền tại các ngân hàng j = 0, 1, 2, ta sẽ lấy tiền tại các ngân hàng này và cộng vào với nhau. Cộng xong thì ta cho vào cái mảng sumAll vừa tạo ở trên:
Tại vị trí khách hàng i = 1 cũng tương tự, ta cộng tiền của họ tại các ngân hàng j = 0, 1, 2 lại rồi nhét vào mảng sumAll:
Bây giờ ta sẽ so sánh các số tiền có trong mảng sumAll kia và thấy 6 < 7, vậy thì ta trả về 7 là số tiền lớn nhất.
5. Code bằng máy
Code của chúng ta như sau:
public int maximumWealth(int[][] accounts) {
int row = accounts.length;
int col = accounts[0].length;
int[] sumAll= new int[row];
for (int i = 0; i < row; i++) {
int sum = 0;
for (int j = 0; j < col; j++) {
sum += accounts[i][j];
}
sumAll[i] = sum;
}
int max = 0;
for(int i : sumAll){
max = Math.max(max, i);
}
return max;
}
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