2023‐08‐13 第 358 场周赛

数组中的最大数对和

• 没注意到数对这个条件

/*
[84,91,18,59,27,9,81,33,17,58] 165
*/


class Solution {
public:
    int maxSum(vector<int>& nums) {
        // 最大的一对数
        
        unordered_map<int, int> cnt; // 最大数位相同的个数
        unordered_map<int, int> sum; // 最大数位相同的和
        
        unordered_map<int, vector<int>> vec; // 相同数位 对
        
        for (int i = 0; i < nums.size(); i ++) {
            int idx = INT_MIN;
            int n = nums[i];
            
            while (n) {
                idx = max(idx, n % 10);
                
                n /= 10;
            }
            
            vec[idx].emplace_back(nums[i]);
        }
        
        int res = -1;
        
        for (auto [k, v] : vec) {
            
            if (v.size() > 1) {
                sort(v.begin(), v.end());
                
                int f = v.size() - 1;
                
                res = max(res, v[f] + v[f - 1]);
            }
        }
        
        return res;
    }
};

翻倍以链表形式表示的数字

• 数字溢出导致罚时

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

/*
[0]
[9,1,9,5,0,5,1,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9]
*/
class Solution {
public:
    ListNode* doubleIt(ListNode* head) {
        // 数据溢出 long long 溢出
        // 还是得用 数组乘法
        
        long long num = 0;
        
        ListNode* res = new ListNode(0);
        
        vector<int> idx; // 原链表数字
        
        while (head != nullptr) {
            idx.emplace_back(head -> val);
            
            head = head -> next;
        }
        
        reverse(idx.begin(), idx.end());
        
        
        vector<int> idx_2; // 原链表翻倍后的数字
        
        int cnt = 0; // 进位
        for (int i = 0; i < idx.size(); i ++) {
            int n = idx[i] * 2 + cnt; // 数字
            
            cnt = n / 10;
            
            idx_2.emplace_back(n % 10);
            
        }
        
        if (cnt != 0) idx_2.emplace_back(cnt);
        
//         num *= 2;
        
//         if (num == 0) return res;
        
//         while (num) {
//             idx.emplace_back(num % 10);
            
//             num /= 10;
//         }
        
        reverse(idx_2.begin(), idx_2.end());
        
        ListNode* c = res;
        
        for (int i = 0; i < idx_2.size(); i ++) {
            ListNode* tem = new ListNode(0);
            
            tem -> val = idx_2[i];
            
            c -> next = tem;
            
            c = tem;
        }
        
        return res -> next;
    }
};

限制条件下元素之间的最小绝对差

• 这个题看着挺简单的
• 暴力肯定会超时 但是想不到其他的方法
• 想用滑动窗口 或者 双指针 但是卡住了
• lower_bound

class Solution {
public:
    int minAbsoluteDifference(vector<int> &nums, int x) {
        int ans = INT_MAX, n = nums.size();
        set<int> s = {INT_MIN / 2, INT_MAX}; // 哨兵
        for (int i = x; i < n; i++) {
            s.insert(nums[i - x]);
            int y = nums[i];
            auto it = s.lower_bound(y);
            ans = min(ans, min(*it - y, y - *--it));
        }
        return ans;
    }
};