LC 周赛 358 解题记录

暑假已过半，然鹅我的数一还没复习完一半...

T1

T1 想怎么做就怎么做，暴力枚举每一个数对也可以，反正数据量小

class Solution {
    public int maxSum(int[] nums) {
        int[] memo = new int[10];
        Arrays.fill(memo, -1);
        int ans = -1;
        for (int i = 0; i < nums.length; i++) {
            int cur = nums[i];
            String s = cur + " ";
            char c = '0';
            for (char ch: s.toCharArray()) {
                if (ch > c) {
                    c = ch;
                }
            }
            int idx = c - '0';
            if (memo[idx] == -1) {
                memo[idx] = cur;
                continue;
            }
            ans = mathjax.max(ans, memo[idx] + cur);
            memo[idx] = mathjax.max(memo[idx], cur);
        }
        return ans;
    }
}

T2

先把所有节点保存下来，按题意构造即可，终于 T2 不是思维题了！

class Solution {
    public ListNode doubleIt(ListNode head) {
        ArrayList<ListNode> arr = new ArrayList<>();
        ListNode itr = head;
        while (itr = null) {
            arr.add(itr);
            itr = itr.next;
        }
        int carry = 0;
        for (int i = arr.size() - 1; i >= 0; i--) {
            int cur = arr.get(i).val;
            cur = cur * 2 + carry;
            carry = cur / 10;
            cur = 10;
            arr.get(i).val = cur;
        }
        if (carry > 0) {
            ListNode node = new ListNode(carry);
            node.next = head;
            return node;
        }
        return head;
    }
}

T3

上点黑科技

枚举每一个位置，用近似滑动窗口的技巧保存与当前枚举元素下标距离大于等于 x 的元素。然后在窗口中用二分查找找到大于等于当前枚举元素的最小元素，和小于等于当前枚举元素的最大元素，则当前元素的最小绝对值差必然在这两个数中产生。然后再更新最终的 ans。如果 ans 中间变为 0 了则直接返回（起到一点聊胜于无的作用）

综合以上的朴素思路，使用 C++ 中的 multiset 和 lower_bound、upper_bound 解决

class Solution {
public:
    int minAbsoluteDifference(vector<int>& nums, int x) {
        int n = nums.size();
        int ans = abs(nums[0] - nums[n - 1]);
        if (ans == 0) {
            return 0;
        }
        multiset<int> set;
        int l = -x - 1;
        int r = x;
        for (int i = r; i < n; i++) {
            set.insert(nums[i]);
        }
        for (int i = 0; i < n; i++) {
            int cur = nums[i];
            l++;
            if (l >= 0 && l <= n - 1) {
                set.insert(nums[l]);
            }
            auto it = set.lower_bound(cur); // 返回第一个大于或等于cur的元素
            auto it1 = set.upper_bound(cur); // 返回第一个大于cur的元素
            if (it != set.end()) {
                ans = min(ans, *it - cur);
            }
            if (it1 != set.begin()) {
                --it1;
                ans = min(ans, cur - *it1);
            }
            if (ans == 0) {
                return 0;
            }
            if (i + x <= n - 1) {
                auto itr = set.find(nums[i + x]);
                set.erase(itr);
            }
        }
        return ans;
    }
};