文章目录
周赛380[3005. 最大频率元素计数](https://leetcode.cn/problems/count-elements-with-maximum-frequency/)哈希 + 计数
[3006. 找出数组中的美丽下标 I](https://leetcode.cn/problems/find-beautiful-indices-in-the-given-array-i/)二分 + 枚举
[3007. 价值和小于等于 K 的最大数字](https://leetcode.cn/problems/maximum-number-that-sum-of-the-prices-is-less-than-or-equal-to-k/)二分 + 数位DP
[3008. 找出数组中的美丽下标 II](https://leetcode.cn/problems/find-beautiful-indices-in-the-given-array-ii/)KMP优化 + 二分 + 枚举
周赛380
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 <= 1001 <= nums[i] <= 100
哈希 + 计数
class Solution {
public int maxFrequencyElements(int[] nums) {
int mx = 0;
Map
for(int x : nums){
map.merge(x, 1, Integer::sum);
mx = Math.max(mx, map.get(x));
}
int res = 0;
for(Map.Entry
if(entry.getValue() == mx)
res += mx;
}
return res;
}
}
3006. 找出数组中的美丽下标 I
中等
给你一个下标从 0 开始的字符串 s 、字符串 a 、字符串 b 和一个整数 k 。
如果下标 i 满足以下条件，则认为它是一个 美丽下标：
0 <= i <= s.length - a.lengths[i..(i + a.length - 1)] == a存在下标j，使得：
0 <= j <= s.length - b.lengths[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 <= 1051 <= a.length, b.length <= 10s、a、和 b 只包含小写英文字母。
二分 + 枚举
class Solution {
public List
// 找到所有的i和j
List
List
for(int i = 0; i <= s.length() - a.length(); i++){
if(s.substring(i, i + a.length()).equals(a))
li.add(i);
}
lj.add(-1);
for(int j = 0; j <= s.length() - b.length(); j++){
if(s.substring(j, j + b.length()).equals(b))
lj.add(j);
}
lj.add(Integer.MAX_VALUE);
// 枚举所有i，找符合条件的j
// |j - i| <= k ==> j<=i+k (i < j), j>=i-k (i > j)
List
for(int i = 0; i < li.size(); i++){
int ipos = li.get(i);
int jpos = lj.get(lowerbound(lj, Math.max(0, ipos-k))); // j>=i-k (i > j)
if(jpos != -1 && jpos != Integer.MAX_VALUE &&
jpos <= ipos && jpos>=ipos-k){
res.add(ipos);
continue;
}
jpos = lj.get(f(lj, Math.min(ipos+k, s.length()))); // j<=i+k (i < j) = (>=(x+1)) - 1
if(jpos != -1 && jpos != Integer.MAX_VALUE &&
jpos >= ipos && jpos <= ipos + k)
res.add(ipos);
}
return res;
}
// 二分找到第一个>=
private int lowerbound(List
int left = 0, right = nums.size();
while(left < right){
int mid = (left + right) >> 1;
if(nums.get(mid) < target)
left = mid + 1;
else right = mid;
}
return right;
}
// 二分找到第一个<=
private int f(List
int left = 0, right = nums.size()-1;
while(left <= right){
int mid = (left + right + 1) >> 1;
if(nums.get(mid) > target)
right = mid - 1;
else left = mid + 1;
}
return right;
}
}
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 <= 10151 <= x <= 8
二分 + 数位DP
https://leetcode.cn/problems/maximum-number-that-sum-of-the-prices-is-less-than-or-equal-to-k/solutions/2603673/er-fen-da-an-shu-wei-dpwei-yun-suan-pyth-tkir/
class Solution {
int x;
public long findMaximumNumber(long k, int x) {
this.x = x;
long left = 0;
long right = (k + 1) << x;
while (left <= right) {
long mid = (left + right) >>> 1;
if (countDigitOne(mid) > k) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return right;
}
// 233 数字1的个数
long num;
int m;
long[][] cache;
public long countDigitOne(long num) {
this.num = num;
this.m = 64 - Long.numberOfLeadingZeros(num);
cache = new long[m][m+1];
for(int i = 0; i < m; i++)
Arrays.fill(cache[i], -1);
return f(m-1, 0, true);
}
public long f(int i, int cnt1, boolean isLimit){
if(i < 0)return cnt1;
if(!isLimit && cache[i][cnt1] >= 0)
return cache[i][cnt1];
long res = 0;
int up = isLimit ? (int) (num >> i & 1) : 1;
for(int d = 0; d <= up; d++){
res += f(i-1, cnt1 + (d == 1 && (i+1) % x == 0 ? 1 : 0), isLimit && d == up);
}
if(!isLimit)
cache[i][cnt1] = res;
return res;
}
}
3008. 找出数组中的美丽下标 II
困难
给你一个下标从 0 开始的字符串 s 、字符串 a 、字符串 b 和一个整数 k 。
如果下标 i 满足以下条件，则认为它是一个 美丽下标 ：
0 <= i <= s.length - a.lengths[i..(i + a.length - 1)] == a存在下标 j 使得：
0 <= j <= s.length - b.lengths[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 * 1051 <= a.length, b.length <= 5 * 105s、a、和 b 只包含小写英文字母。
KMP优化 + 二分 + 枚举
https://leetcode.cn/problems/find-beautiful-indices-in-the-given-array-ii/solutions/2603695/kmper-fen-cha-zhao-by-endlesscheng-7bjm/
更优雅的方法
先二分找 >= x 的第一个元素下标，然后该元素下标-1就是， class Solution { public List char[] text = s.toCharArray(); List List lj.add(0, -1); lj.add(Integer.MAX_VALUE); // 枚举所有i，找符合条件的j // |j - i| <= k ==> j<=i+k (i < j), j>=i-k (i > j) List for(int i = 0; i < li.size(); i++){ int ipos = li.get(i); int jpos = lj.get(lowerbound(lj, Math.max(0, ipos-k))); // j>=i-k (i > j) if(jpos != -1 && jpos != Integer.MAX_VALUE && jpos <= ipos && jpos>=ipos-k){ res.add(ipos); continue; } jpos = lj.get(f(lj, Math.min(ipos+k, s.length()))); // j<=i+k (i < j) = (>=(x+1)) - 1 if(jpos != -1 && jpos != Integer.MAX_VALUE && jpos >= ipos && jpos <= ipos + k) res.add(ipos); } return res; } private List int m = pattern.length; int[] pi = new int[m]; int c = 0; for (int i = 1; i < m; i++) { char v = pattern[i]; while (c > 0 && pattern[c] != v) { c = pi[c - 1]; } if (pattern[c] == v) { c++; } pi[i] = c; } List c = 0; for (int i = 0; i < text.length; i++) { char v = text[i]; while (c > 0 && pattern[c] != v) { c = pi[c - 1]; } if (pattern[c] == v) { c++; } if (c == m) { res.add(i - m + 1); c = pi[c - 1]; } } return res; } // 二分找到第一个>= private int lowerbound(List int left = 0, right = nums.size(); while(left < right){ int mid = (left + right) >> 1; if(nums.get(mid) < target) left = mid + 1; else right = mid; } return right; } // 二分找到第一个<= private int f(List int left = 0, right = nums.size()-1; while(left <= right){ int mid = (left + right + 1) >> 1; if(nums.get(mid) > target) right = mid - 1; else left = mid + 1; } return right; } } 相关链接
发表评论