leetcode contest 380

t3 比较难得构造题目，反而其他题目都是简单题目。

3005. 最大频率元素计数

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

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

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

示例 1：

输入：nums = [1,2,2,3,1,4]
输出：4
解释：元素 1 和 2 的频率为 2 ，是数组中的最大频率。
因此具有最大频率的元素在数组中的数量是 4 。

示例 2：

输入：nums = [1,2,3,4,5]
输出：5
解释：数组中的所有元素的频率都为 1 ，是最大频率。
因此具有最大频率的元素在数组中的数量是 5 。

提示：

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100

地址

https://leetcode.cn/contest/weekly-contest-380/problems/count-elements-with-maximum-frequency/

题意

直接模拟即可

思路

1. 这接找到对角线最长，且面积最大的矩形返回面积即可。
2. 复杂度分析：

• 时间复杂度：$O(n)$，其中 $n$ 表示给定数组的长度。
• 空间复杂度：$O(1)$。

代码

class Solution:
    def areaOfMaxDiagonal(self, dimensions: List[List[int]]) -> int:
        x, y = 0, 0
        for w, h in dimensions:
            if w**2 + h**2 > x**2 + y**2 or w**2 + h**2 == x**2 + y**2 and w * h > x * y:
                x, y = w, h
        return x * y

3006. 找出数组中的美丽下标 I

给你一个下标从 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

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

示例 1：

输入：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] 作为结果。

示例 2：

输入：s = "abcd", a = "a", b = "a", k = 4
输出：[0]
解释：存在 1 个美丽下标：[0]。
- 下标 0 是美丽下标，因为 s[0..0] == "a" ，且存在下标 0 ，满足 s[0..0] == "a" 且 |0 - 0| <= 4 。
因此返回 [0] 作为结果。

提示：

• 1 <= k <= s.length <= 105
• 1 <= a.length, b.length <= 10
• s、a、和 b 只包含小写英文字母。

地址

https://leetcode.cn/contest/weekly-contest-380/problems/find-beautiful-indices-in-the-given-array-i/

题意

kmp匹配，二分查找，kr字符串哈希

思路

1. 本质是我们知道字符串 $a,b$ 在字符串 $s$ 中的匹配位置，并检测 $a$ 中的每个匹配位置 $i$，是否存在位置 $j$ 在字符串 $s$ 中匹配 $b$, 此时 $j$ 满足 $j \in[i - k, i+k]$, 题目的关键在于两点:
   • 匹配的字符串位置序列：此时我们可以用 kmp 或者 $KR$ 字符串匹配算法，计算所有可能的匹配位置即可。
   • 对于每个位置 $i$ 是否存在位置 $j$ 与其匹配：此时我们可以用二分查找找到 大于等于$i-k$ 的其实位置 $x$, 同时找到大于 $i + k$ 的起始位置 $y$, 此时检测 $x$ 与 $y$ 是否相等即可。
2. 复杂度分析：

• 时间复杂度：$O(n \log n + m)$, $n$ 表示给定字符串 $s$ 的长度， $m$ 表示给定字符串 $a$ 与 $b$ 的长度之和；
• 空间复杂度：$O(n)$；

代码

class Solution:
    def match(self, s, a):
        res = []
        if len(s) < len(a):
            return res
        mod, base = 10**9 + 7, 31
        key, h = 0, 1
        m = len(a)
        
        for i in range(m):
            key = (key * base + ord(a[i]) - ord('a')) % mod
        for i in range(m - 1):
            h = h * base % mod
        curr = 0
        for i in range(len(s)):
            curr = (curr * base + ord(s[i]) - ord('a')) % mod
            if i >= m - 1:
                if curr == key:
                    res.append(i - m + 1)
                curr = (curr - h * (ord(s[i - m + 1]) - ord('a')) % mod + mod) % mod
        return res
        
    def beautifulIndices(self, s: str, a: str, b: str, k: int) -> List[int]:
        arr1 = self.match(s, a)
        arr2 = self.match(s, b)
        res = []
        for v in arr1:
            x = bisect_left(arr2, v - k)
            y = bisect_right(arr2, v + k)
            if x != y:
                res.append(v)
        return res;

3007. 价值和小于等于 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 。

示例 1：

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

示例 2：

输入：k = 7, x = 2
输出：9
解释：由于 x 等于 2 ，我们检查每个数字的偶数位。
2 和 3 在二进制表示下的第二个数位为设置位，所以它们的价值和为 2 。
6 和 7 在二进制表示下的第二个数位为设置位，所以它们的价值和为 2 。
8 和 9 在二进制表示下的第四个数位为设置位但第二个数位不是设置位，所以它们的价值和为 2 。
数字 1 ，4 和 5 在二进制下偶数位都不是设置位，所以它们的价值和为 0 。
10 在二进制表示下的第二个数位和第四个数位都是设置位，所以它的价值为 2 。
前 9 个数字的价值和为 6 。
前 10 个数字的价值和为 8，超过了 k = 7 ，所以答案为 9 。

提示：

• 1 <= k <= 1015
• 1 <= x <= 8

地址

https://leetcode.cn/contest/weekly-contest-380/problems/maximum-number-that-sum-of-the-prices-is-less-than-or-equal-to-k/

题意

构造题目，数学计算题目

思路

1. 数学计算题目相关

2. 复杂度分析：

• 时间复杂度：$O(n)$，其中 $n$ 表示给定的数组的长度。
• 空间复杂度：$O(n)$，其中 $n$ 表示给定的数组的长度。

代码

3008. 找出数组中的美丽下标 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

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

示例 1：

输入：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] 作为结果。

示例 2：

输入：s = "abcd", a = "a", b = "a", k = 4
输出：[0]
解释：存在 1 个美丽下标：[0]。
- 下标 0 是美丽下标，因为 s[0..0] == "a" ，且存在下标 0 ，满足 s[0..0] == "a" 且 |0 - 0| <= 4 。
因此返回 [0] 作为结果。

提示：

• 1 <= k <= s.length <= 5 * 105
• 1 <= a.length, b.length <= 5 * 105
• s、a、和 b 只包含小写英文字母。

地址

https://leetcode.cn/contest/weekly-contest-380/problems/find-beautiful-indices-in-the-given-array-ii/

题意

kmp匹配，二分查找，kr字符串哈希

思路

1. 与 $T2$ 一样的题目，本质是我们知道字符串 $a,b$ 在字符串 $s$ 中的匹配位置，并检测 $a$ 中的每个匹配位置 $i$，是否存在位置 $j$ 在字符串 $s$ 中匹配 $b$, 此时 $j$ 满足 $j \in[i - k, i+k]$, 题目的关键在于两点:
   • 匹配的字符串位置序列：此时我们可以用 kmp 或者 $KR$ 字符串匹配算法，计算所有可能的匹配位置即可。
   • 对于每个位置 $i$ 是否存在位置 $j$ 与其匹配：此时我们可以用二分查找找到 大于等于$i-k$ 的其实位置 $x$, 同时找到大于 $i + k$ 的起始位置 $y$, 此时检测 $x$ 与 $y$ 是否相等即可。
2. 复杂度分析：

• 时间复杂度：$O(n \log n + m)$, $n$ 表示给定字符串 $s$ 的长度， $m$ 表示给定字符串 $a$ 与 $b$ 的长度之和；
• 空间复杂度：$O(n)$；

代码

class Solution:
    def match(self, s, a):
        res = []
        if len(s) < len(a):
            return res
        mod, base = 10**9 + 7, 31
        key, h = 0, 1
        m = len(a)
        
        for i in range(m):
            key = (key * base + ord(a[i]) - ord('a')) % mod
        for i in range(m - 1):
            h = h * base % mod
        curr = 0
        for i in range(len(s)):
            curr = (curr * base + ord(s[i]) - ord('a')) % mod
            if i >= m - 1:
                if curr == key:
                    res.append(i - m + 1)
                curr = (curr - h * (ord(s[i - m + 1]) - ord('a')) % mod + mod) % mod
        return res
        
    def beautifulIndices(self, s: str, a: str, b: str, k: int) -> List[int]:
        arr1 = self.match(s, a)
        arr2 = self.match(s, b)
        res = []
        for v in arr1:
            x = bisect_left(arr2, v - k)
            y = bisect_right(arr2, v + k)
            if x != y:
                res.append(v)
        return res

欢迎关注和打赏，感谢支持！

• 关注我的博客: https://mike-box.github.io/

• 关注我的知乎：https://www.zhihu.com/people/da-hua-niu