Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
💡 By Loser1 from Learning AI with Losers
🔥 Bạn có bao giờ thấy hai người xa lạ bỗng trở thành tri kỷ chỉ vì có cùng sở thích? Hôm nay, ta sẽ tìm kiếm những con số có “tâm hồn đồng điệu” – tức là có tổng chữ số bằng nhau – và kết hợp chúng để tạo ra giá trị lớn nhất có thể!
📌 Hãy tưởng tượng bạn đang trong một bữa tiệc, nơi mỗi người có một số điểm “hòa hợp” nhất định. Nhiệm vụ của bạn là tìm ra cặp đôi ăn ý nhất có điểm tổng hợp cao nhất! 🎉
Hôm nay chúng ta cùng nhau với loser1 sẽ chinh phục bài toán [2342. Max Sum of a Pair With Equal Sum of Digits] – một thử thách thú vị với cách tiếp cận khéo léo! 🚀
Bạn được cung cấp một mảng nums
gồm các số nguyên dương (0-indexed). Bạn có thể chọn hai chỉ số i
và j
, sao cho i != j
, và tổng các chữ số của số nums[i]
bằng tổng các chữ số của nums[j]
.
Trả về giá trị lớn nhất của nums[i] + nums[j]
mà bạn có thể đạt được với tất cả các cặp chỉ số i
và j
thỏa mãn điều kiện.
Example 1:
Input: nums = [18,43,36,13,7] Output: 54 Giải thích: Các cặp (i, j) thỏa mãn điều kiện là: - (0, 2), cả hai số có tổng chữ số bằng 9, và tổng của chúng là 18 + 36 = 54. - (1, 4), cả hai số có tổng chữ số bằng 7, và tổng của chúng là 43 + 7 = 50. Vì vậy, tổng lớn nhất mà chúng ta có thể đạt được là 54.
Example 2:
Input: nums = [10,12,19,14] Output: -1 Giải thích: Không có hai số nào thỏa mãn điều kiện, vì vậy chúng ta trả về -1.
Ràng buộc:
1 <= nums.length <= 105
1 <= nums[i] <= 109
Bạn có bao giờ để ý rằng một số như 18
và 36
đều có tổng chữ số là 9
không? 🤔
💡 Ý tưởng chính:
📌 Minh họa trực quan
Giả sử ta có danh sách số như sau:
nums = [18, 43, 36, 13, 7]
Ta tính tổng chữ số của từng số:
18 → 1 + 8 = 9
43 → 4 + 3 = 7
36 → 3 + 6 = 9
13 → 1 + 3 = 4
7 → 7
Bây giờ ta nhóm lại:
Tổng chữ số 9: [18, 36]
Tổng chữ số 7: [43, 7]
Tổng chữ số 4: [13]
Tổng chữ số 7: [7]
📌 Cặp có tổng giá trị cao nhất là (18, 36) → 54
Sử dụng unordered_map<int, multiset<int>>
để lưu các số có cùng tổng chữ số.
Key
: Tổng chữ sốValue
: Một tập hợp chứa các số tương ứngVì ta dùng multiset<int>
, các số sẽ tự động được sắp xếp tăng dần.
📌 Ta chỉ cần lấy hai phần tử cuối cùng của tập hợp để tính tổng lớn nhất!
multiset
mất O(logn)O(\log n)unordered_map
class Solution {
public:
int sum_digits(int x) {
int ans = 0;
while (x > 0) {
ans += x % 10;
x /= 10;
}
return ans;
}
int maximumSum(vector<int>& nums) {
int ans = -1;
unordered_map<int, multiset<int>> myMap;
for (int x : nums) {
myMap[sum_digits(x)].insert(x);
}
for (const auto& pair : myMap) {
const multiset<int>& myMultiSet = pair.second;
if (myMultiSet.size() >= 2) {
auto it = myMultiSet.rbegin();
int max1 = *it;
++it;
int max2 = *it;
ans = max(ans, max1 + max2);
}
}
return ans;
}
};
Hãy tưởng tượng mảng [18, 43, 36, 13, 7]
như một nhóm bạn:
✔️ Nhóm số theo tổng chữ số giúp chúng ta tìm ra những “tri kỷ” số học.
✔️ Sử dụng multiset
giúp dễ dàng lấy hai số lớn nhất.
✔️ Cách tiếp cận này hiệu quả hơn brute-force, tiết kiệm thời gian đáng kể.
🚀 Loser’s Wisdom of the Day:
“Trong lập trình (và cuộc sống), đôi khi bạn không cần phải tìm kiếm toàn bộ thế giới để có câu trả lời – chỉ cần nhìn vào những gì có chung bản chất với nhau!” 💡
🔥 Ngày mai chúng ta sẽ tiếp tục khám phá thế giới thuật toán! Đừng bỏ lỡ nhé! 💪
CODE EDITOR
📌 Hashtags:
#leetcode #leetcodedaily #coding #datastructures #algorithms #learningwithlosers