LeetCode Contest 441

欢迎大家加QQ群：623375442，可以方便群里面交流。终于手速场了一次。

100598. Maximum Unique Subarray Sum After Deletion

给你一个整数数组 nums 。

你可以从数组 nums 中删除任意数量的元素，但不能将其变为空数组。执行删除操作后，选出 nums 中满足下述条件的一个子数组：

子数组中的所有元素互不相同。

最大化子数组的元素和。

返回子数组的最大元素和。

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

测试样例：

输入：nums = [1,2,3,4,5]

输出：15

解释：不删除任何元素，选中整个数组得到最大元素和。

解答：如果全是负数，那么返回负数中的最大值。否则就是删除数字，直到剩下所有正数，且每个数只出现一次。

class Solution {
    public int maxSum(int[] nums) {
        int max = Integer.MIN_VALUE;
        boolean[] isAppear = new boolean[101];
        int res = 0;
        for (int n : nums) {
            max = Math.max(max, n);
            if (n >= 0) {
                if (!isAppear[n]) {
                    res += n;
                    isAppear[n] = true;
                }
            }
        }
        if (max < 0) {
            return max;
        }
        return res;
    }
}

100563. Closest Equal Element Queries

给你一个循环数组 nums 和一个数组 queries 。

对于每个查询 i ，你需要找到以下内容：

数组 nums 中下标 queries[i] 处的元素与任意其他下标 j（满足 nums[j] == nums[queries[i]]）之间的最小距离。如果不存在这样的下标 j，则该查询的结果为 -1 。

返回一个数组 answer，其大小与 queries 相同，其中 answer[i] 表示查询i的结果。

测试样例：

输入：nums = [1,3,1,4,1,3,2], queries = [0,3,5]

输出：[2,-1,3]

解释:

查询 0：下标 queries[0] = 0 处的元素为 nums[0] = 1 。最近的相同值下标为 2，距离为 2。

查询 1：下标 queries[1] = 3 处的元素为 nums[3] = 4 。不存在其他包含值 4 的下标，因此结果为 -1。

查询 2：下标 queries[2] = 5 处的元素为 nums[5] = 3 。最近的相同值下标为 1，距离为 3（沿着循环路径：5 -> 6 -> 0 -> 1）。

解答：利用一个TreeSet去搜索比当前位置小/大的第一个位置。因为是循环数组，所以还需要考虑第一次和最后一次出现位置，利用循环达到最小。

class Solution {
    public List<Integer> solveQueries(int[] nums, int[] queries) {
        HashMap<Integer, TreeSet<Integer>> posMem = new HashMap<>();
        for (int i = 0; i < nums.length; ++i) {
            if (!posMem.containsKey(nums[i])) {
                posMem.put(nums[i], new TreeSet<>());
            }
            posMem.get(nums[i]).add(i);
        }
        List<Integer> res = new ArrayList<>();
        for (int p : queries) {
            int n = nums[p];
            if (posMem.get(n).size() == 1) {
                res.add(-1);
            } else {
                TreeSet<Integer> set = posMem.get(n);
                Integer higher = set.higher(p);
                int cur = Integer.MAX_VALUE;
                if (higher == null) {
                    cur = Math.min(cur, nums.length - p + set.first());
                } else {
                    cur = Math.min(cur, higher - p);
                }
                Integer lower = set.lower(p);
                if (lower == null) {
                    cur = Math.min(cur, p + nums.length - set.last());
                } else {
                    cur = Math.min(cur, p - lower);
                }
                res.add(cur);
            }
        }
        return res;
    }
}

100604. Zero Array Transformation IV

给你一个长度为 n 的整数数组 nums 和一个二维数组 queries ，其中 queries[i] = [li, ri, vali]。

每个 queries[i] 表示以下操作在 nums 上执行：

从数组 nums 中选择范围 [li, ri] 内的一个下标子集。

将每个选中下标处的值减去正好 vali。

零数组是指所有元素都等于 0 的数组。

返回使得经过前 k 个查询（按顺序执行）后，nums 转变为零数组的最小可能非负值 k。如果不存在这样的 k，返回 -1。

数组的子集是指从数组中选择的一些元素（可能为空）。

测试样例：

输入：nums = [2,0,2], queries = [[0,2,1],[0,2,1],[1,1,3]]

输出：2

解释:

对于查询 0 （l = 0, r = 2, val = 1）：

将下标 [0, 2] 的值减 1。

数组变为 [1, 0, 1]。

对于查询 1 （l = 0, r = 2, val = 1）：

将下标 [0, 2] 的值减 1。

数组变为 [0, 0, 0]，这就是一个零数组。因此，最小的 k 值为 2。

解答：

操作描述：
- 题目中的每个查询 [li, ri, vali] 给定了一个区间 [li, ri]，我们可以在这个区间内的任意位置减去 vali，因此问题的关键在于确定在每个查询中如何选择下标来使得数组的元素最终为零。
动态规划（DP）思想：
- 对于每个 nums[i]，我们可以用动态规划来判断是否能够在前 k 次查询之后使 nums[i] 变为 0。具体来说，对于每个 nums[i]，我们定义一个数组 dp，其中 dp[j] 表示我们能否通过前若干次查询在 nums[i] 上减去 j 的值。
- 初始时，dp[nums[i]] = true，表示我们从 nums[i] 开始，减去 nums[i] 后可以得到 0。
- 然后我们逐步查看每个查询 [li, ri, vali]，如果当前查询的范围包含 i，则我们可以尝试用这个查询将 nums[i] 进行减值。我们更新 dp 数组中的值，表示从当前位置 nums[i] 出发，能否减去某个值。
解题流程：
- 对于每个 nums[i]，使用一个 dp 数组记录是否能通过一些操作将其减为 0。
- 遍历所有的查询，如果查询能作用到当前元素 nums[i]，就更新 dp 数组。
- 如果 dp[0] 为 true，表示我们能够通过前 k 次查询将 nums[i] 变为 0。如果 dp[0] 为 false，则返回 -1，表示无法变为零。
- 最终返回操作的最大次数 k，这是使得 nums 完全变成零数组的最小次数。

class Solution {
    public int minZeroArray(int[] nums, int[][] queries) {
        int res = 0; // 记录最小的查询次数
        for (int i = 0; i < nums.length; ++i) {  // 遍历 nums 数组中的每个元素
            if (nums[i] == 0) continue; // 如果 nums[i] 本来就是 0，跳过

            boolean[] dp = new boolean[nums[i] + 1];  // dp 数组表示当前值是否可以通过查询变为 0
            dp[nums[i]] = true;  // 初始时 nums[i] 的值是可以通过操作变为 0 的
            int p = 0;  // p 记录操作的次数

            for (int[] q : queries) {  // 遍历每个查询
                ++p;  // 操作次数加 1
                if (q[0] <= i && i <= q[1]) {  // 如果当前查询的范围包含索引 i
                    // 更新 dp 数组，尝试减去 q[2] 的值
                    for (int j = 0; j + q[2] <= nums[i]; ++j) {
                        dp[j] |= dp[j + q[2]];  // 如果 dp[j+q[2]] 为 true，说明可以通过该查询将 nums[i] 减去 q[2]
                    }
                }
                if (dp[0]) break;  // 如果 dp[0] 为 true，说明已经可以将 nums[i] 变为 0，退出循环
            }

            if (!dp[0]) return -1;  // 如果 dp[0] 仍然为 false，说明无法将 nums[i] 变为 0，返回 -1
            res = Math.max(res, p);  // 更新操作次数 res
        }
        return res;  // 返回最小的操作次数
    }
}

100609. Count Beautiful Numbers

给你两个正整数 l 和 r 。如果正整数每一位上的数字的乘积可以被这些数字之和整除，则认为该整数是一个美丽整数。

统计并返回 l 和 r 之间（包括 l 和 r ）的美丽整数的数目。

测试样例：

输入：l = 10, r = 20

输出：2

解释: 范围内的美丽整数为 10 和 20 。

解答：

动态规划与记忆化搜索：
- 我们使用了一个四维的 dp 数组来存储每个递归状态的结果。该状态包含：当前处理的位置 pos、是否受限制 restrict、剩余和 remain 和当前的乘积 mul。通过这种方式，我们避免了对重复子问题的计算。
递归过程：
- 在递归的过程中，我们逐位遍历数字，并尝试选取每个位置的数字。对于每个可能的数字，我们递归计算下一个位置的结果。
- mul 记录当前已选数字的乘积，remain 记录当前已选数字的和。如果遍历完所有位置后，乘积能够被和整除，则该数字为美丽数字。
优化技巧：
- 通过 mem 数组缓存了每一位数可能的美丽数字数量，减少了重复计算。
- 使用记忆化（缓存）技术来存储中间计算结果，避免重复计算，提高了效率。

class Solution {
    // mem 数组保存了每一位数的最大乘积和（对于不同的数字长度）
    private static final int[] mem = {0,9,15,309,3675,43462,486887,5311174,57110375,607393752,2092560258};

    // 美丽数字的主函数，返回范围 [l, r] 内美丽数字的数量
    public int beautifulNumbers(int l, int r) {
        return count(r) - count(l - 1);  // 通过计算 count(r) 和 count(l-1)，得到范围 [l, r] 内美丽数字的数量
    }

    // 计算范围 [1, n] 内美丽数字的数量
    private int count(int n) {
        if (n == 0) return 0;  // 基本情况：0不是美丽数字
        String num = String.valueOf(n);  // 将数字 n 转换为字符串形式
        int max = num.length() * 9;  // 每位数字最大为 9，因此最大乘积和为位数 * 9
        int res = 0;  // 用于记录结果

        // 在 mem 数组中累计长度为 i 的所有美丽数字的数量
        for (int i = 0; i < num.length(); ++i) {
            res += mem[i];
        }

        // 针对每一个可能的剩余和 i，从数字的最高位开始逐位遍历
        for (int i = 1; i <= max; ++i) {
            Integer[][][][] dp = new Integer[num.length()][2][max + 1][max + 1];  // dp 数组，记忆化搜索
            res += helper(dp, 0, 0, 1, i, i, num);  // 使用 helper 递归函数进行处理
        }
        return res;  // 返回美丽数字的总数
    }

    // helper 函数执行记忆化递归，递归状态包括 pos（当前处理的位置），mul（当前乘积），remain（剩余和）
    private int helper(Integer[][][][] dp, int pos, int restrict, int mul, int remain, int target, String num) {
        // 递归结束条件，处理完所有位后判断是否是美丽数字
        if (pos == dp.length) {
            if (remain != 0) {
                return 0;  // 如果剩余和不为 0，返回 0
            } else {
                return mul % target == 0 ? 1 : 0;  // 判断当前乘积是否能被和整除
            }
        } 
        // 如果当前状态已经计算过，直接返回缓存结果
        else if (dp[pos][restrict][remain][mul] == null) {
            int st = 0, ed = Math.min(9, remain), res = 0;
            if (pos == 0) st = 1;  // 如果是最高位，最小值为 1
            if (restrict == 0) {
                ed = Math.min(ed, num.charAt(pos) - '0');  // 如果限制了最大数字，更新范围
            }
            // 遍历当前位置的所有可能的数字
            for (int i = st; i <= ed; ++i) {
                if (restrict == 0 && i == num.charAt(pos) - '0') {
                    res += helper(dp, pos + 1, 0, mul * i % target, remain - i, target, num);  // 如果限制了最大值，继续递归
                } else {
                    res += helper(dp, pos + 1, 1, mul * i % target, remain - i, target, num);  // 其他情况，松开限制，继续递归
                }
            }
            dp[pos][restrict][remain][mul] = res;  // 存储结果到 dp 数组
        }
        return dp[pos][restrict][remain][mul];  // 返回当前计算结果
    }
}

100598. Maximum Unique Subarray Sum After Deletion

100563. Closest Equal Element Queries

100604. Zero Array Transformation IV

100609. Count Beautiful Numbers

By hughqiao