ARST打卡第237周[237/521]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

class Solution {
public:
    int getBitSum(int num) {
        int bitSum = 0;
        while (num) {
            bitSum += num % 10;
            num /= 10;
        }
        return bitSum;
    }
    int maximumSum(vector<int>& nums) {
        // 本来想看看数位和定义，看tips，结果tips把思路全说了，尴尬
        // 那就快速实现吧
        // 枚举数据和对最大两个值的hash，然后最终获取结果
        // 优化思路: AC之后看别人的提交发现如果在第一种for里面就ans维护最大ans.
        // 数据结构可以退化为 unordered_map<int, int> 后面保存每次的max_num
        // 每次直接维护ans即可
        unordered_map<int, pair<int, int>> bitSum2max;
        for (auto& num : nums) {
            int bitSum = getBitSum(num);
            if (bitSum2max.find(bitSum) == bitSum2max.end()) {
                bitSum2max[bitSum].first = num;
                continue;
            }
            if (bitSum2max[bitSum].second == 0) {
                // 升序排列. 小的放 first, 大的放 second
                if (num < bitSum2max[bitSum].first) {
                    swap(num, bitSum2max[bitSum].first);
                }
                bitSum2max[bitSum].second = num;
                continue;
            }
            if (num <= bitSum2max[bitSum].first) {
                continue;
            } else if (num <= bitSum2max[bitSum].second) {
                swap(num, bitSum2max[bitSum].first);
            } else {
                // 先替换第二个，再把第二个替换掉第一个
                swap(num, bitSum2max[bitSum].second);
                swap(num, bitSum2max[bitSum].first);
            }
        }
        int ans = -1;
        for (const auto& it : bitSum2max) {
            if (it.second.first && it.second.second) {
                ans = max(ans, it.second.first + it.second.second);
            }
        }
        return ans;
    }
};