力扣第 80 场双周赛

比赛时间 2022-06-11。本场周赛国服共 929 人 AK。

T1. 强密码检验器 II（3 分）

解题思路

模拟。可用 bit mask 来简洁编码。

时间复杂度：O(n)。

参考代码

class Solution {
    public boolean strongPasswordCheckerII(String password) {
        // 它有至少 8 个字符
        if (password.length() < 8) {
            return false;
        }

        // 它 不 包含 2 个连续相同的字符
        for (int i = 1; i < password.length(); i++) {
            if (password.charAt(i) == password.charAt(i - 1)) {
                return false;
            }
        }

        // 至少包含 一个小写英文 字母。
        // 至少包含 一个大写英文 字母。
        // 至少包含 一个数字 。
        // 至少包含 一个特殊字符 。
        int mask = 0;
        for (char ch : password.toCharArray()) {
            if (Character.isLowerCase(ch)) {
                mask |= 1;
            } else if (Character.isUpperCase(ch)) {
                mask |= 2;
            } else if (Character.isDigit(ch)) {
                mask |= 4;
            } else if ("!@#$%^&*()-+".contains(String.valueOf(ch))) {
                mask |= 8;
            }
        }
        return mask == 15;
    }
}

T2. 咒语和药水的成功对数（4 分）

解题思路

将 potions 排序后二分查找 相乘 大于等于 success 的最小下标，即能求出 能成功组合的 药水 数目。

时间复杂度：O(nlogn)。

参考代码

class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        int n = spells.length;
        int m = potions.length;
        Arrays.sort(potions);

        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            int left = 0;
            int right = m;
            while (left < right) {
                int mid = left + (right - left) / 2;
                // 边界二分 F, F,..., F, [T, T,..., T]
                // ----------------------^
                if ((long) spells[i] * potions[mid] >= success) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            res[i] = m - left;
        }
        return res;
    }
}

T3. 替换字符后匹配（6 分）

解题思路

逆向模拟，枚举 s 中的每个与 sub 等长的子串，判断其能否由 sub 生成。

时间复杂度：O(n^2)。

参考代码

class Solution {
    private Map<Character, Set<Character>> mappingsMap;

    public boolean matchReplacement(String s, String sub, char[][] mappings) {
        int sLen = s.length();
        int subLen = sub.length();

        mappingsMap = new HashMap<>();
        for (char[] mapping : mappings) {
            // new -> [old]
            mappingsMap.computeIfAbsent(mapping[1], key -> new HashSet<>()).add(mapping[0]);
        }

        for (int i = 0; i + subLen <= sLen; i++) {
            String subStr = s.substring(i, i + subLen);
            if (check(subStr, sub)) {
                return true;
            }
        }
        return false;
    }

    private boolean check(String subStr, String sub) {
        for (int j = 0; j < subStr.length(); j++) {
            char newi = subStr.charAt(j);
            char oldi = sub.charAt(j);
            if (newi != oldi) {
                if (!mappingsMap.containsKey(newi) || !mappingsMap.get(newi).contains(oldi)) {
                    return false;
                }
            }
        }
        return true;
    }
}

T4. 统计得分小于 K 的子数组数目（6 分）

解题思路

枚举每个 i（左边界），二分查找求 j（右边界），使得 [i,j] 的分数严格小于 k。每个 i 的贡献为 j-i+1。时间复杂度：O(nlogn)。

也可用双指针在 时间复杂度：O(n) 内求解。

参考代码

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

        // 前缀和
        long[] preSum = new long[len + 1];
        for (int i = 0; i < len; i++) {
            preSum[i + 1] = preSum[i] + nums[i];
        }

        long cnt = 0L;
        // 枚举每个 i
        for (int i = 0; i < len; i++) {
            int left = i;
            int right = len;
            while (left < right) {
                int mid = left + (right - left) / 2;
                // 边界二分 F, F,..., F, [T, T,..., T]
                // ----------------------^
                if ((preSum[mid + 1] - preSum[i]) * (mid - i + 1L) >= k) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            // 每个 i 的贡献
            cnt += left - i + 1;
        }
        return cnt - len;
    }
}

（全文完）