网上看到这题
Return the maximum sum formed by any 2 numbers that form the same digit sum in a given list of numbers. Return -1 if no 2 numbers have the same digit sum.
Example 1:
Input A: [51, 71, 17, 42, 33, 44, 24, 62]
Output: 133
Explanation: Max sum can be formed by 71 + 62 which has same digit sum of 8
Example 2:
Input A: [51, 71, 17, 42]
Output: 93
Explanation: Max sum can be formed by 51 + 42 which has same digit sum of 6
Example 3:
Input A: [42, 33, 60]
Output: 102
Explanation: Max sum can be formed by 42 + 60 which has same digit sum of 6
Example 4:
Input A: [51, 32, 43]
Output: -1
Explanation: There are no 2 numbers with same digit sum
贴下别人的解法
class Solution {
public:
int findMaxSum(vector<int> nums) {
unordered_map<int, vector<int>> sumToNums; //maps digit sum to numbers with that digit sum
for (int i = 0; i < nums.size(); i++) {
int curNum = nums[i];
int dS = digitSum(curNum);
sumToNums[dS].push_back(curNum);
}
int maxSum = -1;
for (int i = 0; i < nums.size(); i++) {
int curNum = nums[i];
int dS = digitSum(curNum);
vector<int> matches = sumToNums[dS];
for (int num : matches) {
if (num == curNum) continue; //Can't add num to num
maxSum = max(maxSum, curNum+num);
}
}
return maxSum;
}
private:
int digitSum(int num) {
int sum = 0;
while (num > 0) {
sum += num%10;
num /= 10;
}
return sum;
}
};
int main() {
Solution s = Solution();
vector<int> nums = {51, 32, 43};
cout << s.findMaxSum(nums);
}
import functools
import heapq
def maximum_sum_of_same_digit_sum(A):
digit_sum_map = {}
for num in A:
# Computing the sum of digits of the number
sum_of_digits = functools.reduce(lambda x, y: int(x) + int(y), str(num))
# Updating the obtained sum to the hash map and also pushing the corresponding number to the min heap
if sum_of_digits not in digit_sum_map or len(digit_sum_map[sum_of_digits]) < 2:
# Push the numbers to the heap until the numbers which form a sum are exactly 2
heapq.heappush(digit_sum_map.setdefault(sum_of_digits, []), num)
else:
# Once the numbers reach 2 push and pop the numbers to maintain the count to 2
heapq.heappushpop(digit_sum_map[sum_of_digits], num)
# Return the maximum sum of all the the 2 largest numbers that forms a particular sum
return max(map(lambda nums: functools.reduce(lambda x, y: x + y, nums) if len(nums) == 2 else -1, digit_sum_map.values()))