LeetCode 周赛-291

第一题 ¹

问题描述

给你一个表示某个正整数的字符串 number 和一个字符 digit 。

从 number 中 恰好 移除 一个 等于 digit 的字符后，找出并返回按 十进制 表示 最大 的结果字符串。生成的测试用例满足 digit 在 number 中出现至少一次。

示例 1：

输入：number = "123", digit = "3"
输出："12"
解释："123" 中只有一个 '3' ，在移除 '3' 之后，结果为 "12" 。

示例 2：

输入：number = "1231", digit = "1"
输出："231"
解释：可以移除第一个 '1' 得到 "231" 或者移除第二个 '1' 得到 "123" 。
由于 231 > 123 ，返回 "231" 。

示例 3：

输入：number = "551", digit = "5"
输出："51"
解释：可以从 "551" 中移除第一个或者第二个 '5' 。
两种方案的结果都是 "51" 。

提示：

• 2 <= number.length <= 100
• number 由数字 '1' 到 '9' 组成
• digit 是 '1' 到 '9' 中的一个数字
• digit 在 number 中出现至少一次

思路

第一题很简单，只需要读懂题意即可。顺序扫描数组，每次遇到目标 digit 都比较一下当前去除 digit 之后剩余字符串的大小。由于字符串是由纯数字组成的，因此可以直接用字符串来比较大小，无需再转为数字。

代码

class Solution {
    public String removeDigit(String number, char digit) {
        int split = 0;
        String res = null;
        for (int i = number.length() - 1; i >= 0; i--) {
            if (number.charAt(i) == digit) {
                String cur = number.substring(0, i) + number.substring(i + 1, number.length());      
                if (res == null) {
                    res = cur;
                } else {
                    res = res.compareTo(cur) > 0 ? res : cur;
                }
            }
        }
        return res;
    }
}

第二题 ²

问题描述

给你一个整数数组 cards ，其中 cards[i] 表示第 i 张卡牌的 值 。如果两张卡牌的值相同，则认为这一对卡牌 匹配 。

返回你必须拿起的最小连续卡牌数，以使在拿起的卡牌中有一对匹配的卡牌。如果无法得到一对匹配的卡牌，返回 -1 。

示例 1：

输入：cards = [3,4,2,3,4,7]
输出：4
解释：拿起卡牌 [3,4,2,3] 将会包含一对值为 3 的匹配卡牌。注意，拿起 [4,2,3,4] 也是最优方案。

示例 2：

输入：cards = [1,0,5,3]
输出：-1
解释：无法找出含一对匹配卡牌的一组连续卡牌。

提示：

• 1 <= cards.length <= 105
• 0 <= cards[i] <= 106

思路

根据题目描述和示例，整个问题可以转化为“求数组中相同数字之间距离的最小值”的问题。使用一张哈希表保存每个数字上次出现的下标，遍历的同时计算当前数字距离其上次出现的距离，并将该距离与当前最短距离进行比较，取最小的那个作为本轮的结果，计算与比较结束后更新当前数字在哈希表中的下标，继续循环。

代码

class Solution {
    public int minimumCardPickup(int[] cards) {
        Map<Integer, Integer> map = new HashMap<>();
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < cards.length; i++) {
            if (map.containsKey(cards[i])) {
                res = Math.min(res, i - map.get(cards[i]) + 1);
            }
            map.put(cards[i], i);
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }
}

第三题 ³

问题描述

给你一个整数数组 nums 和两个整数 k 和 p ，找出并返回满足要求的不同的子数组数，要求子数组中最多 k 个可被 p 整除的元素。

如果满足下述条件之一，则认为数组 nums1 和 nums2 是 不同 数组：

• 两数组长度 不同，或者

• 存在 至少 一个下标 i 满足 nums1[i] != nums2[i] 。

子数组 定义为：数组中的连续元素组成的一个 非空 序列。

示例 1：

输入：nums = [2,3,3,2,2], k = 2, p = 2
输出：11
解释：
位于下标 0、3 和 4 的元素都可以被 p = 2 整除。
共计 11 个不同子数组都满足最多含 k = 2 个可以被 2 整除的元素：
[2]、[2,3]、[2,3,3]、[2,3,3,2]、[3]、[3,3]、[3,3,2]、[3,3,2,2]、[3,2]、[3,2,2] 和 [2,2] 。
注意，尽管子数组 [2] 和 [3] 在 nums 中出现不止一次，但统计时只计数一次。
子数组 [2,3,3,2,2] 不满足条件，因为其中有 3 个元素可以被 2 整除。

示例 2：

输入：nums = [1,2,3,4], k = 4, p = 1
输出：10
解释：
nums 中的所有元素都可以被 p = 1 整除。
此外，nums 中的每个子数组都满足最多 4 个元素可以被 1 整除。
因为所有子数组互不相同，因此满足所有限制条件的子数组总数为 10 。

提示：

• 1 <= nums.length <= 200
• 1 <= nums[i], p <= 200
• 1 <= k <= nums.length

思路

题目中的子数组描述有点复杂，其实题目中的子数组是指数组中连续的几个数字组成的序列，只要两个子序列中每个位置的元素不相同即为不同的子序列。同时应当注意，题目中的 k 是一个数值上界，而不是计数时必须满足的定值条件。

按照题目要求，对连续的子序列进行字符拼接，只要满足 k 的限制且不重复即可计数。其中去重的操作可以使用 HashSet 来做到。也有一点需要注意，子序列 [1, 2, 3] 和 子序列 [12, 3] 如果在模拟时只是进行单纯的字符拼接的话，则会得到相同的字符串，但是实际上两个子序列是不同的，应当单独计数，因此在模拟时需要对在字符之间添加分隔符。

代码

class Solution {
    public int countDistinct(int[] nums, int k, int p) {
        HashSet<String> set = new HashSet<>();
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            int count = 0;
            StringBuilder sb = new StringBuilder();
            for (int j = i; j < nums.length; j++) {
                sb.append(nums[j] + " ");
                if (nums[j] % p == 0) {
                    count++;
                }
                String cur = sb.toString();
                if (count <= k && !set.contains(cur)) {
                    res++;
                    set.add(cur);
                }
            }
        }
        return res;
    }
}

第四题 ⁴

问题描述

字符串的 引力 定义为：字符串中 不同 字符的数量。

• 例如，"abbca" 的引力为 3 ，因为其中有 3 个不同字符 'a'、'b' 和 ‘c’ 。

给你一个字符串 s ，返回 其所有子字符串的总引力。

子字符串 定义为：字符串中的一个连续字符序列。

示例 1：

输入：s = "abbca"
输出：28
解释："abbca" 的子字符串有：
- 长度为 1 的子字符串："a"、"b"、"b"、"c"、"a" 的引力分别为 1、1、1、1、1，总和为 5 。
- 长度为 2 的子字符串："ab"、"bb"、"bc"、"ca" 的引力分别为 2、1、2、2 ，总和为 7 。
- 长度为 3 的子字符串："abb"、"bbc"、"bca" 的引力分别为 2、2、3 ，总和为 7 。
- 长度为 4 的子字符串："abbc"、"bbca" 的引力分别为 3、3 ，总和为 6 。
- 长度为 5 的子字符串："abbca" 的引力为 3 ，总和为 3 。
引力总和为 5 + 7 + 7 + 6 + 3 = 28 。

示例 2：

输入：s = "code"
输出：20
解释："code" 的子字符串有：
- 长度为 1 的子字符串："c"、"o"、"d"、"e" 的引力分别为 1、1、1、1 ，总和为 4 。
- 长度为 2 的子字符串："co"、"od"、"de" 的引力分别为 2、2、2 ，总和为 6 。
- 长度为 3 的子字符串："cod"、"ode" 的引力分别为 3、3 ，总和为 6 。
- 长度为 4 的子字符串："code" 的引力为 4 ，总和为 4 。
引力总和为 4 + 6 + 6 + 4 = 20 。

提示：

• 1 <= s.length <= 105
• s 由小写英文字母组成

思路

按照题目本身描述可以采用暴力模拟的方式依次计算出不同长度的子串的引力，累加得出最终结果。暴力方法的时间复杂度和空间复杂度较高，无法通过。

这类问题暴力模拟无法解决的话，可以考虑采用动态规划的思想。首先定义 dp[i] 表示当前下标为 [0, i] 的子串的引力值大小。

想要计算 dp[i]，我们要知道 dp[i - 1]。根据我们的定义，dp[i - 1] 表示当前下标为 [0, i - 1] 的子串的引力值大小。现在需要思考递推公式，在从 dp[i - 1] 到 dp[i] 的转移过程中，我们加入了字符 s[i]，如果 s[i] 在之前的子串 s[0, i - 1] 中没有出现过的话，那么该子串的所有的子字符串的引力值都会加一，反之，如果 s[i] 出现在子串 s[0, i - 1] 的 j 位置处，那么则有 j 之前的所有子字符串中没有出现过字符 s[i]，表示 s[j, i - 1] 的所有子字符串的引力值会随着 s[i] 的加入而加一，而 s[0, j - 1] 这部分的所有子字符串的引力值不会改变。

以示例 1 为例，首先初始字符为 'a'，我们现在要添加字符 s[1]，由于 s[1] = 'b'，且它之前并没有出现过（对于这种情况，为了计算方便与算法的一致性，我们可以假设所有可能的字符上次都出现在在 -1 的位置上），因此引力值会加 1 的子串为：[a]。接下来我们添加字符 s[2]，由于 s[2] = 'b'，其上次出现的位置下标为 1，那么表示从 0 到下标 1 之间的所有子串的引力值都无法加一，因为引力值表示的是子串中不同字符的数量，加入一个已经存在的字符无法使得引力值得到增长。当前从下标 0 起，必须包含 s[2] 的子串分别为：[abb, bb, b]，由于 s[2] 是重复的，无法满足条件，因此本轮没有子字符串的引力值增长，但是需要注意的是，引入 s[2] 的同时加入了一个新的子字符串 [b]，因此本轮总体的引力值还是要加 1 的，之前加入 s[1] 的时候也同理，这里作为补充不再赘述。按照上面的规则，加入 s[3] = 'c' 后，引力值会增加的子串分别为 [abbc, bbc, bc]，以及一个新的子串 [c]，引力值增加了 3 + 1 = 4。加入 s[4] = 'a' 同理，由于 'a' 上次出现的位置下标为 0，因此下标 0 之前的子串都因为含有和本轮新字符 s[3] 相同的字符而使得其引力值无法增长，引力值会增长的子串只有 [bbca, bca, bc]，以及一个新的子字符串 [a]，本轮的引力值相比于上轮增加了 3 + 1 = 4。

根据上面的规则和分析，可以得到 dp[i] 的计算方式：dp[i] = dp [i - 1] + (i - j - 1) + 1，其中 i 为当前新加入的字符的下标，j 为 新加入字符 s[i] 在之前出现的下标，i - j - 1 表示引力值会加 1 的子字符串的数量，最后 +1 表示新加入的字符 s[i] 本身组成的子串也会使得总引力值加一。

为了计算 dp[i]，我们需要知道 dp[i - 1] 和 j。由于单个字符的引力值只有 1，因此 dp[0] 初始化为 1。所有之前未出现过的元素之前出现的下标设置为 -1 以满足边界条件。此外，我们最终的结果应当是 dp 数组中每个元素的累积值。

代码

class Solution {
    public long appealSum(String s) {
        int n = s.length();
        Map<Character, Integer> preIndex = new HashMap<>();
        int[] dp = new int[n];
        dp[0] = 1;
        preIndex.put(s.charAt(0), 0);
        long res = dp[0];
        for (int i = 1; i < n; i++) {
            int pre = preIndex.getOrDefault(s.charAt(i), -1);
            dp[i] = dp[i - 1] + i - pre - 1 + 1;
            preIndex.put(s.charAt(i), i);
            res += dp[i];
        }
        return res;
    }
}

注意到计算 dp[i] 时只用到了 dp[i - 1]，因此可以采用滚动数组的方式来降低算法的空间复杂度：

class Solution {
    public long appealSum(String s) {
        int n = s.length();
        Map<Character, Integer> preIndex = new HashMap<>();
        int dp = 1;
        preIndex.put(s.charAt(0), 0);
        long res = dp;
        for (int i = 1; i < n; i++) {
            int pre = preIndex.getOrDefault(s.charAt(i), -1);
            dp += i - pre - 1 + 1;
            res += dp;
            preIndex.put(s.charAt(i), i);
        }
        return res;
    }
}

总结

本次周赛的问题都是关于数组的，模拟类型的题比较多且很没有很多拐弯抹角的条件。前两个题很简单，第三题中规中矩，第四题如果之前没接触过类似的动态规划题目的话，递推公式很难想到。第三题如果没有读懂题目中对于子数组的描述以及 k 的含义的话就比较坑了，因为这样的话就不会去想到直接用模拟计数的方式解题。

第三题和第四题的代码编写有一些技巧，比如第三题在对模拟的子串进行去重时，应当加入分隔符以避免数字拼接后无视数位导致的字符串重复，第四题将所有未出现过的字符的“上次出现位置”记为 -1，由于我们想要计算的是 i - 1 到 j 的长度，因此可以认为数组下标是从 -1 开始的，-1 位置可以认为是一个逻辑上的开始位置，这样理解的话会简单点，就是单纯的计算数轴上两个点之间的长度而已。

References