LeetCode Contest 380

100162. Count Elements With Maximum Frequency

给你一个由 正整数 组成的数组 nums 。

返回数组 nums 中所有具有 最大 频率的元素的 总频率 。

元素的 频率 是指该元素在数组中出现的次数。

测试样例：

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

输出：4

解释：元素 1 和 2 的频率为 2 ，是数组中的最大频率。因此具有最大频率的元素在数组中的数量是 4 。

解答：按照题意，用HashMap统计，然后计算最大频率，最后统计元素数。

class Solution {
    public int maxFrequencyElements(int[] nums) {
        HashMap<Integer, Integer> reqCount = new HashMap<>();
        for (int n : nums) {
            reqCount.put(n, reqCount.getOrDefault(n, 0) + 1);
        }

        int res = 0, maxFreq = 0;
        for (int n : nums) {
            int t = reqCount.get(n);
            if (t > maxFreq) {
                maxFreq = t;
                res = 1;
            } else if (t == maxFreq) {
                ++res;
            }
        }
        return res;
    }
}

100160. Maximum Number That Sum of the Prices Is Less Than or Equal to K

给你一个整数 k 和一个整数 x 。

令 s 为整数 num 的下标从 1 开始的二进制表示。我们说一个整数 num 的 价值 是满足 i % x == 0 且 s[i] 是 设置位 的 i 的数目。

请你返回 最大 整数 num ，满足从 1 到 num 的所有整数的 价值 和小于等于 k 。

注意：

• 一个整数二进制表示下 设置位 是值为 1 的数位。
• 一个整数的二进制表示下标从右到左编号，比方说如果 s == 11100 ，那么 s[4] == 1 且 s[2] == 0 。

测试样例：

输入：k = 9, x = 1

输出：6

解释：数字 1 ，2 ，3 ，4 ，5 和 6 二进制表示分别为 "1" ，"10" ，"11" ，"100" ，"101" 和 "110" 。由于 x 等于 1 ，每个数字的价值分别为所有设置位的数目。这些数字的所有设置位数目总数是 9 ，所以前 6 个数字的价值和为 9 。所以答案为 6 。

解答：其实是一道板子题，主要需要仔细。利用折半搜索来定位最优的数字。然后有一个numBitCount的函数，来确定某一位出现的次数。

class Solution {
    public long findMaximumNumber(long k, int x) {
        long st = 1, ed = Long.MAX_VALUE >> 5;
        while (st < ed) {
            long mid = (st + ed + 1) / 2, count = 0;
            for (int i = x; i <= 60; i = i + x) {
                count += numBitCount(mid, i);
            }
            if (count <= k) {
                st = mid;
            } else {
                ed = mid - 1;
            }
        }
        return st;
    }

    private long numBitCount(long num, int pos) {
        long mul = 1L << pos;
        long count = num / mul * (1L << (pos - 1));
        long remain = num % mul;
        if (((remain >> (pos - 1)) & 1) == 1L) {
            count += (remain - (1L << (pos - 1)) + 1);
        }
        return count;
    }
}

100207. Find Beautiful Indices in the Given Array II

给你一个下标从 0 开始的字符串 s 、字符串 a 、字符串 b 和一个整数 k 。

如果下标 i 满足以下条件，则认为它是一个 美丽下标 ：

• 0 <= i <= s.length - a.length
• s[i..(i + a.length - 1)] == a
• 存在下标 j 使得：
• 0 <= j <= s.length - b.length
  • s[j..(j + b.length - 1)] == b
  • |j - i| <= k

以数组形式按 从小到大排序 返回美丽下标。

测试样例：

输入：s = "isawsquirrelnearmysquirrelhouseohmy", a = "my", b = "squirrel", k = 15

输出：[16,33]

解释：存在 2 个美丽下标：[16,33]。

• 下标 16 是美丽下标，因为 s[16..17] == "my" ，且存在下标 4 ，满足 s[4..11] == "squirrel" 且 |16 - 4| <= 15 。
• 下标 33 是美丽下标，因为 s[33..34] == "my" ，且存在下标 18 ，满足 s[18..25] == "squirrel" 且 |33 - 18| <= 15 。

因此返回 [16,33] 作为结果。

解答：这题和第二题一样，我就只放这题的题解了。本质是KMP的板子题。如果会KMP算法，就能知道所有i和j可能出现的位置，最后利用双指针（我又偷懒用了Java自带的红黑树）来搜索符合条件的i。

class Solution {
    public List<Integer> beautifulIndices(String s, String a, String b, int k) {
        List<Integer> aList = kmp(s, a), bList = kmp(s, b);
        TreeSet<Integer> set = new TreeSet<>(bList);
        List<Integer> res = new ArrayList<>();
        for (int an : aList) {
            Integer l = set.floor(an), r = set.ceiling(an);
            if ((l != null && an - l <= k) || (r != null && r - an <= k)) {
                res.add(an);
            }
        }
        return res;
    }

    public List<Integer> kmp(String query, String pattern) {
        int n = query.length();
        int m = pattern.length();
        int[] fail = new int[m];
        Arrays.fill(fail, -1);
        for (int i = 1; i < m; ++i) {
            int j = fail[i - 1];
            while (j != -1 && pattern.charAt(j + 1) != pattern.charAt(i)) {
                j = fail[j];
            }
            if (pattern.charAt(j + 1) == pattern.charAt(i)) {
                fail[i] = j + 1;
            }
        }

        List<Integer> res = new ArrayList<>();
        int match = -1;
        for (int i = 0; i < n; ++i) {
            while (match != -1 && pattern.charAt(match + 1) != query.charAt(i)) {
                match = fail[match];
            }
            if (pattern.charAt(match + 1) == query.charAt(i)) {
                ++match;
                if (match == m - 1) {
                    res.add(i - pattern.length() + 1);
                    match = fail[match];
                }
            }
        }
        return res;
    }
}