力扣第 291 场周赛

2022 五一劳动节，打个比赛放松一下。本场周赛国服共 877 人 AK。据说 T4 是蓝桥杯原题。。

T1. 移除指定数字得到的最大结果（3 分）

解题思路

模拟。移除一个字符后，长度是固定的，用库函数 String#compareTo(String anotherString) 比较字典序即可。

时间复杂度：大于 O(n)，库函数不讨论时间复杂度。

参考代码

class Solution {
    public String removeDigit(String number, char digit) {
        int len = number.length();

        String max = "";
        for (int i = 0; i < len; i++) {
            if (number.charAt(i) == digit) {
                String num = number.substring(0, i) + number.substring(i + 1, len);
                // num > res
                if (num.compareTo(max) > 0) {
                    max = num;
                }
            }
        }
        return max;
    }
}

T2. 必须拿起的最小连续卡牌数（4 分）

解题思路

枚举 & 贪心。拿起的最小连续卡牌第一张和最后一张必定相同，先预处理得出每张牌对应的下标数组，最小的下标间距即为答案。

时间复杂度：O(n)。

参考代码

class Solution {
    public int minimumCardPickup(int[] cards) {
        int len = cards.length;

        // 预处理下标数组
        Map<Integer, List<Integer>> idxMap = new HashMap<>();
        for (int i = 0; i < len; i++) {
            idxMap.computeIfAbsent(cards[i], key -> new ArrayList<>()).add(i);
        }

        // 枚举求最小值
        int min = Integer.MAX_VALUE;
        for (List<Integer> idxList : idxMap.values()) {
            if (idxList.size() > 1) {
                for (int i = 1; i < idxList.size(); i++) {
                    min = Math.min(min, idxList.get(i) - idxList.get(i - 1) + 1);
                }
            }
        }
        return min == Integer.MAX_VALUE ? -1 : min;
    }
}

T3. 含最多 K 个可整除元素的子数组（5 分）

解题思路

模拟。数据范围 nums.length <= 200，可以两层 for 循环直接模拟，再利用 Set 集合进行去重。

时间复杂度：O(n^3)，每个 O(n^2) 内额外需要 O(n) 拼接字符串。

参考代码

class Solution {
    public int countDistinct(int[] nums, int k, int p) {
        int len = nums.length;

        Set<String> hashSet = new HashSet<>();
        for (int i = 0; i < len; i++) {
            // 子数组中有 cnt 个可被 p 整除的元素
            int cnt = 0;
            StringBuilder stringBuilder = new StringBuilder();
            for (int j = i; j < len; j++) {
                if (nums[j] % p == 0) {
                    cnt++;
                }
                if (cnt <= k) {
                    stringBuilder.append(nums[j]).append(",");
                    hashSet.add(stringBuilder.toString());
                } else {
                    break;
                }
            }
        }
        return hashSet.size();
    }
}

T4. 字符串的总引力（6 分）

解题思路

数据范围 s.length <= 10^5，两层 for 循环显然会 TLE。

对于这种题型和数据范围，可以 AC 的时间复杂度一般为 O(nlogn) 或 O(n)，尝试先按字典序来个排序，发现总引力会变化，说明总引力跟顺序有关，排除排序的方向。考虑是否存在 O(n) 的解法。单独观察每个字符对总引力的贡献。发现跟前一个相同字符的位置有关。

时间复杂度：O(n)。

参考代码

class Solution {
    public long appealSum(String s) {
        int len = s.length();
        char[] chars = s.toCharArray();

        // 字符最后一次出现的下标
        int[] lastIdx = new int[26];
        Arrays.fill(lastIdx, -1);

        long cnt = 0;
        long lastSum = 0;
        // 滑动窗口
        for (int i = 0; i < len; i++) {
            // 与跟前一个相同字符的间隔
            long diff = i - lastIdx[chars[i] - 'a'];
            lastIdx[chars[i] - 'a'] = i;
            lastSum += diff;
            cnt += lastSum;
        }
        return cnt;
    }
}

（全文完）