Biweekly Contest 147

欢迎大家加QQ群：623375442，可以方便群里面交流。最后一题只有6分是完全没想到的。这题真的好难。

100509. Substring Matching Pattern

给你一个字符串 s 和一个模式字符串 p ，其中 p 恰好 包含 一个 '*' 符号。

p 中的 '*' 符号可以被替换为零个或多个字符组成的任意字符序列。

如果 p 可以变成 s 的子字符串，那么返回 true ，否则返回 false 。

子字符串 指的是字符串中一段连续 非空 的字符序列。

测试样例：

输入：s = "leetcode", p = "ee*e"

输出：true

解释：将 '*' 替换为 "tcod" ，子字符串 "eetcode" 匹配模式串。

解答：这题类似正则匹配那道题目。注意p的后缀都是'*'的情况。

class Solution {
    public boolean hasMatch(String s, String p) {
        boolean[][] isVisit = new boolean[s.length() + 1][p.length() + 1];
        for (int i = 0; i < s.length(); ++i) {
            if (helper(s, p, i, 0, isVisit)) {
                return true;
            }
        }
        return false;
    }

    private boolean helper(String s, String p, int sp, int pp, boolean[][] isVisit) {
        if (pp == p.length()) {
            return true;
        } else if (sp == s.length()) {
            if (isVisit[sp][pp]) return false;
            isVisit[sp][pp] = true;
            if (p.charAt(pp) == '*') {
                return helper(s, p, sp, pp + 1, isVisit);
            }
            return false;
        } else if (!isVisit[sp][pp]) {
            isVisit[sp][pp] = true;
            if (s.charAt(sp) == p.charAt(pp)) {
                return helper(s, p, sp + 1, pp + 1, isVisit);
            } else if (p.charAt(pp) == '*') {
                return helper(s, p, sp + 1, pp + 1, isVisit) || helper(s, p, sp + 1, pp, isVisit) || helper(s, p, sp, pp + 1, isVisit);
            }
        }
        return false;
    }
}

100503. Design Task Manager

一个任务管理器系统可以让用户管理他们的任务，每个任务有一个优先级。这个系统需要高效地处理添加、修改、执行和删除任务的操作。

请你设计一个 TaskManager 类：

• TaskManager(vector<vector>& tasks) 初始化任务管理器，初始化的数组格式为 [userId, taskId, priority] ，表示给 userId 添加一个优先级为 priority 的任务 taskId 。
• void add(int userId, int taskId, int priority) 表示给用户 userId 添加一个优先级为 priority 的任务 taskId ，输入 保证 taskId 不在系统中。
• void edit(int taskId, int newPriority) 更新已经存在的任务 taskId 的优先级为 newPriority 。输入 保证 taskId 存在于系统中。
• void rmv(int taskId) 从系统中删除任务 taskId 。输入 保证 taskId 存在于系统中。
• int execTop() 执行所有用户的任务中优先级 最高 的任务，如果有多个任务优先级相同且都为 最高 ，执行 taskId 最大的一个任务。执行完任务后，taskId 从系统中 删除 。同时请你返回这个任务所属的用户 userId 。如果不存在任何任务，返回 -1 。

注意 ，一个用户可能被安排多个任务。

测试样例：

输入：["TaskManager", "add", "edit", "execTop", "rmv", "add", "execTop"]
[[[[1, 101, 10], [2, 102, 20], [3, 103, 15]]], [4, 104, 5], [102, 8], [], [101], [5, 105, 15], []]

输出：[null, null, null, 3, null, null, 5]

解释：

• TaskManager taskManager = new TaskManager([[1, 101, 10], [2, 102, 20], [3, 103, 15]]); // 分别给用户 1 ，2 和 3 初始化一个任务。
• taskManager.add(4, 104, 5); // 给用户 4 添加优先级为 5 的任务 104 。
• taskManager.edit(102, 8); // 更新任务 102 的优先级为 8 。
• taskManager.execTop(); // 返回 3 。执行用户 3 的任务 103 。
• taskManager.rmv(101); // 将系统中的任务 101 删除。
• taskManager.add(5, 105, 15); // 给用户 5 添加优先级为 15 的任务 105 。
• taskManager.execTop(); // 返回 5 。执行用户 5 的任务 105 。

解答：这题难度不大，主要多复用函数可以减少犯错的概率。

class TaskManager {
    private HashMap<Integer, int[]> taskInfo;
    private TreeSet<int[]> sort;

    public TaskManager(List<List<Integer>> tasks) {
        taskInfo = new HashMap<>();
        sort = new TreeSet<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                for (int i = 0; i < 2; ++i) {
                    if (o1[i] != o2[i]) return Integer.compare(o2[i], o1[i]);
                }
                return 0;
            }
        });
        for (List<Integer> task : tasks) {
            add(task.get(0), task.get(1), task.get(2));
        }
    }

    public void add(int userId, int taskId, int priority) {
        taskInfo.put(taskId, new int[]{userId, taskId, priority});
        sort.add(new int[]{priority, taskId});
    }

    public void edit(int taskId, int newPriority) {
        int[] info = taskInfo.get(taskId);
        rmv(taskId);
        add(info[0], taskId, newPriority);
    }

    public void rmv(int taskId) {
        int[] info = taskInfo.get(taskId);
        taskInfo.remove(taskId);
        sort.remove(new int[]{info[2], info[1]});
    }

    public int execTop() {
        if (sort.isEmpty()) return -1;
        int[] first = sort.pollFirst();
        int[] info = taskInfo.get(first[1]);
        System.out.println(Arrays.toString(info));
        rmv(first[1]);
        return info[0];
    }
}

100536. Longest Subsequence With Decreasing Adjacent Difference

给你一个整数数组 nums 。

你的任务是找到 nums 中的 最长子序列 seq ，这个子序列中相邻元素的 绝对差 构成一个 非递增 整数序列。换句话说，nums 中的序列 seq0, seq1, seq2, ..., seqm 满足 |seq1 - seq0| >= |seq2 - seq1| >= ... >= |seqm - seqm - 1| 。

请你返回这个子序列的长度。

一个 子序列 指的是从一个数组中删除零个或多个元素后，剩下元素不改变顺序得到的 非空 数组。

测试样例：

输入：nums = [16,6,3]

输出：3

解释：最长子序列是 [16, 6, 3] ，相邻绝对差值为 [10, 3] 。

解答：典型动态规划题目。1 <= nums[i] <= 300，这个范围可以知道最大diff小于299。可以遍历每个位置，所有diff情况。

class Solution {
    public int longestSubsequence(int[] nums) {
        int[] lastAppear = new int[301];
        Arrays.fill(lastAppear, -1);
        int[][] mem = new int[nums.length][300];
        int res = 0;
        for (int i = 0; i < nums.length; ++i) {
            for (int j = 1; j <= 300; ++j) {
                // 遍历diff情况
                if (lastAppear[j] != -1) {
                    int diff = Math.abs(nums[i] - j);
                    int max = mem[lastAppear[j]][diff];
                    // 后缀最大会被使用到，注意
                    mem[i][diff] = Math.max(mem[i][diff], max == 0 ? 2 : (max + 1));
                    res = Math.max(res, mem[i][diff]);
                }
            }
            // 记录后缀最大
            for (int j = 298; j >= 0; --j) {
                mem[i][j] = Math.max(mem[i][j], mem[i][j + 1]);
            }
            lastAppear[nums[i]] = i;
        }
        return res;
    }
}

100513. Maximize Subarray Sum After Removing All Occurrences of One Element

给你一个整数数组 nums 。

你可以对数组执行以下操作 至多 一次：

• 选择 nums 中存在的 任意 整数 X ，确保删除所有值为 X 的元素后剩下数组 非空 。
• 将数组中 所有 值为 X 的元素都删除。

请你返回 所有 可能得到的数组中 最大 子数组和为多少。

子数组 指的是一个数组中一段连续 非空 的元素序列。

测试样例：

输入：nums = [-3,2,-2,-1,3,-2,3]

输出：7

解释：我们执行至多一次操作后可以得到以下数组：

• 原数组是 nums = [-3, 2, -2, -1, 3, -2, 3] 。最大子数组和为 3 + (-2) + 3 = 4 。
• 删除所有 X = -3 后得到 nums = [2, -2, -1, 3, -2, 3] 。最大子数组和为 3 + (-2) + 3 = 4 。
• 删除所有 X = -2 后得到 nums = [-3, 2, -1, 3, 3] 。最大子数组和为 2 + (-1) + 3 + 3 = 7 。
• 删除所有 X = -1 后得到 nums = [-3, 2, -2, 3, -2, 3] 。最大子数组和为 3 + (-2) + 3 = 4 。
• 删除所有 X = 3 后得到 nums = [-3, 2, -2, -1, -2] 。最大子数组和为 2 。

输出为 max(4, 4, 7, 4, 2) = 7 。

解答：这题没想到啥好办法。直接分类讨论。如果一个负数出现次数超过330次，那么就假设删除这个数字，遍历一次数组，然后计算最大子序列。如果小于330次，那么计算一下，利用这个负数出现的位置，计算最大子序列。

class Solution {
    public long maxSubarraySum(int[] nums) {
        long[] prefixSum = new long[nums.length + 1];
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        long res = nums[0];
        for (int i = 0; i < nums.length; ++i) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
            if (nums[i] < 0) {
                if (!map.containsKey(nums[i])) {
                    map.put(nums[i], new ArrayList<>());
                }
                map.get(nums[i]).add(i);
            }
            res = Math.max(res, nums[i]);
        }
        res = Math.max(res, prefixSum[nums.length]);
        if (res <= 0) return res;
        SegmentTree tree = new SegmentTree(prefixSum);
        for (Map.Entry<Integer, List<Integer>> kv : map.entrySet()) {
            if (kv.getValue().size() == nums.length) {
                break;
            // 次数超过330次，直接假设删除这个数字，得出最大子序列。
            } else if (kv.getValue().size() >= 330) {
                res = Math.max(res, scanWithSkip(nums, kv.getKey()));
            } else {
                long[] max = new long[kv.getValue().size()];
                res = Math.max(res, tree.maxRange(0, kv.getValue().get(0)));
                int size = kv.getValue().size();
                for (int i = 1; i < size; ++i) {
                    max[i - 1] = tree.maxRange(kv.getValue().get(i - 1) + 2, kv.getValue().get(i));
                }
                max[kv.getValue().size() - 1] = tree.maxRange(kv.getValue().get(size - 1) + 1, nums.length);
                int last = 0;
                for (int i = 0; i < size; ++i) {
                    long min = tree.minRange(last, kv.getValue().get(i));
                    last = kv.getValue().get(i);
                    // 双循环，枚举两端情况下，最佳结果。
                    // 利用线段树快速计算min和max
                    for (int j = i; j < size; ++j) {
                        res = Math.max(res, max[j] - min - kv.getKey() * (j - i + 1L));
                    }
                }
            }
        }
        return res;
    }

    private long scanWithSkip(int[] nums, int skip) {
        long sum = 0, res = Long.MIN_VALUE;
        for (int n : nums) {
            if (n == skip) continue;
            sum += n;
            res = Math.max(res, sum);
            if (sum < 0) sum = 0;
        }
        return res;
    }
}

class SegmentTree {
    private long[] minTree, maxTree;
    private int n;

    public SegmentTree(long[] nums) {
        if (nums.length > 0) {
            n = nums.length;
            minTree = new long[n * 2];
            maxTree = new long[n * 2];
            buildTree(nums);
        }
    }
    private void buildTree(long[] nums) {
        for (int i = n, j = 0;  i < 2 * n; i++,  j++) {
            minTree[i] = nums[j];
            maxTree[i] = nums[j];
        }
        for (int i = n - 1; i > 0; --i) {
            minTree[i] = Math.min(minTree[i * 2], minTree[i * 2 + 1]);
            maxTree[i] = Math.max(maxTree[i * 2], maxTree[i * 2 + 1]);
        }
    }

    public long minRange(int l, int r) {
        l += n;
        r += n;
        long sum = Long.MAX_VALUE / 2;
        while (l <= r) {
            if ((l % 2) == 1) {
                sum = Math.min(sum, minTree[l]);
                l++;
            }
            if ((r % 2) == 0) {
                sum = Math.min(sum, minTree[r]);
                r--;
            }
            l /= 2;
            r /= 2;
        }
        return sum;
    }

    public long maxRange(int l, int r) {
        l += n;
        r += n;
        long sum = Long.MIN_VALUE / 2;
        while (l <= r) {
            if ((l % 2) == 1) {
                sum = Math.max(sum, maxTree[l]);
                l++;
            }
            if ((r % 2) == 0) {
                sum = Math.max(sum, maxTree[r]);
                r--;
            }
            l /= 2;
            r /= 2;
        }
        return sum;
    }
}