力扣第 380 场周赛

比赛时间 2024-01-14。本场周赛国服共 255 人 AK。

T1. 最大频率元素计数（3 分）

解题思路

模拟。

时间复杂度：O(n)。

参考代码

class Solution {
    public int maxFrequencyElements(int[] nums) {
        int[] cnt = new int[105];
        for (int v : nums) {
            cnt[v]++;
        }
        int max = Arrays.stream(cnt).max().orElseThrow();
        int c = 0;
        for (int v : cnt) {
            if (v == max) c++;
        }
        return c * max;
    }
}

T2. 找出数组中的美丽下标 I（4 分）

解题思路

见 T4。

参考代码

略。

T3. 价值和小于等于 K 的最大数字（5 分）

解题思路

二分 + 数位 DP。注意一般数位 DP 的 i 是左到右，本题的 i 是低位到高位，需要转换成 n-i。

时间复杂度：O((x + logk)^3)。

参考代码

class Solution {
    private int x;

    public long findMaximumNumber(long k, int x) {
        this.x = x;

        long left = 2;
        long right = (long) 1e16;
        while (left < right) {
            long mid = left + (right - left) / 2;
            // 边界二分 F, F,..., F, [T, T,..., T]
            // ----------------------^
            if (count(mid) > k) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left - 1;
    }

    private char[] s;
    private int n;
    private long[][] dp;

    private long count(long num) {
        s = Long.toBinaryString(num).toCharArray();
        n = s.length;
        dp = new long[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], -1);
        }
        return f(0, 0, true, false);
    }

    private long f(int i, int sum, boolean isLimit, boolean isNum) {
        if (i == n) {
            return isNum ? sum : 0;
        }
        // 记忆化搜索
        if (!isLimit && isNum && dp[i][sum] != -1) {
            return dp[i][sum];
        }
        long res = 0;
        if (!isNum) {
            // 可以跳过当前数位
            res = f(i + 1, sum, false, false);
        }
        int up = isLimit ? s[i] - '0' : 1;
        for (int d = isNum ? 0 : 1; d <= up; d++) {
            int is1 = ((n - i) % x == 0 && d == 1) ? 1 : 0;
            res += f(i + 1, sum + is1, isLimit && d == up, true);
        }
        if (!isLimit && isNum) {
            dp[i][sum] = res;
        }
        return res;
    }
}

T4. 找出数组中的美丽下标 II（6 分）

解题思路

KMP + 二分。KMP 预处理出子串所有出现位置，再二分判定每个起点是否符合要求。

时间复杂度：O(nlogn)。

参考代码

class Solution {
    public List<Integer> beautifulIndices(String s, String a, String b, int k) {
        char[] txt = s.toCharArray();
        char[] patA = a.toCharArray();
        char[] patB = b.toCharArray();
        List<Integer> idsA = getStartIds(txt, patA, prefix_function(patA));
        List<Integer> idsB = getStartIds(txt, patB, prefix_function(patB));

        List<Integer> ans = new ArrayList<>();
        for (Integer i : idsA) {
            int l = i - k, r = i + k;

            int j0 = lowerBound(idsB, l);
            int j1 = lowerBound(idsB, r + 1);
            if (j0 < j1) {
                ans.add(i);
            }
        }
        return ans;
    }

    private int lowerBound(List<Integer> a, int key) {
        int l = 0, r = a.size();
        while (l < r) {
            int m = l + (r - l) / 2;
            if (a.get(m) >= key) r = m;
            else l = m + 1;
        }
        return l;
    }

    private List<Integer> getStartIds(char[] txt, char[] pat, int[] pi) {
        List<Integer> res = new ArrayList<>();
        int n = txt.length, m = pat.length;
        for (int i = 0, j = 0; i < n; i++) {
            while (j > 0 && txt[i] != pat[j]) j = pi[j - 1];
            if (txt[i] == pat[j]) j++;
            if (j == m) {
                res.add(i - j + 1);
                j = pi[j - 1];
            }
        }
        return res;
    }

    private int[] prefix_function(char[] s) {
        int n = s.length;
        int[] pi = new int[n];
        for (int i = 1; i < n; i++) {
            int j = pi[i - 1];
            while (j > 0 && s[i] != s[j]) j = pi[j - 1];
            if (s[i] == s[j]) j++;
            pi[i] = j;
        }
        return pi;
    }
}

（全文完）