1838. 最高频元素的频数
2021.7.19 又是新的一周
题目描述
元素的 频数 是该元素在一个数组中出现的次数。
给你一个整数数组 nums 和一个整数 k 。在一步操作中，你可以选择 nums 的一个下标，并将该下标对应元素的值增加 1 。
执行最多 k 次操作后，返回数组中最高频元素的 最大可能频数 。
示例 1：
输入：nums = [1,2,4], k = 5
输出：3
解释：对第一个元素执行 3 次递增操作，对第二个元素执 2 次递增操作，此时 nums = [4,4,4] 。
4 是数组中最高频元素，频数是 3 。
示例 2：
输入：nums = [1,4,8,13], k = 5
输出：2
解释：存在多种最优解决方案：
- 对第一个元素执行 3 次递增操作，此时 nums = [4,4,8,13] 。4 是数组中最高频元素，频数是 2 。
- 对第二个元素执行 4 次递增操作，此时 nums = [1,8,8,13] 。8 是数组中最高频元素，频数是 2 。
- 对第三个元素执行 5 次递增操作，此时 nums = [1,4,13,13] 。13 是数组中最高频元素，频数是 2 。
示例 3：
输入：nums = [3,9,6], k = 2
输出：1
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/frequency-of-the-most-frequent-element
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
我的第一个想法，就是计算将位置 i 前面的所有数变成位置 i 的数共需要多大
然后二分查找
class Solution {
public int maxFrequency(int[] nums, int k) {
int l = nums.length;
Arrays.sort(nums);
long[] pre = new long[l];
for(int i = 1; i < l; i++){
pre[i] = pre[i - 1] + (nums[i] - nums[i - 1]) * i;
}
int max = 1;
for(int i = 1; i < l; i++){
int left = 0;
int right = i;
while(left < right){
int mid = (right - left) / 2 + left;
if(pre[i] - pre[mid] - mid * (nums[i] - nums[mid]) > k){
left = mid + 1;
}else{
right = mid;
}
}
max = Math.max(max, i - left + 1);
}
return max;
}
}
或者说滑动窗口，添加变成当前位置所需要加的数，如果不满足小于k的话，减去左边的值
这里内层能用if，是因为是求最大值
class Solution {
public int maxFrequency(int[] nums, int k) {
Arrays.sort(nums);
int n = nums.length;
long total = 0;
int l = 0, res = 1;
for (int r = 1; r < n; ++r) {
total += (long) (nums[r] - nums[r - 1]) * (r - l);
if (total > k) {
total -= nums[r] - nums[l];
++l;
}
res = Math.max(res, r - l + 1);
}
return res;
}
}
76. 最小覆盖子串
2021.7.19 虾皮今天笔试出了个最小覆盖子序列，会员题，看不了就先做个这个
题目描述
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。
注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = “ADOBECODEBANC”, t = “ABC”
输出：“BANC”
示例 2：
输入：s = “a”, t = “a”
输出：“a”
示例 3:
输入: s = “a”, t = “aa”
输出: “”
解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-window-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
滑动窗口+哈希表，哈希表用来判断是否包含某个字母
然后要用一个变量来存储当前有多少个字母是达到了要求的个数，避免了直接比较两个map
另外需要特别注意一个点，写在代码后面
class Solution {
public String minWindow(String s, String t) {
int ls = s.length();
int lt = t.length();
char[] tt = t.toCharArray();
char[] ss = s.toCharArray();
Map<Character, Integer> mapt = new HashMap<>();
for(int i = 0; i < lt; i++){
mapt.put(tt[i], mapt.getOrDefault(tt[i], 0) + 1);
}
Map<Character, Integer> maps = new HashMap<>();
int l = 0;
int r = 0;
int match = 0;
int min = ls + 1;
int left = -1;
while(r < ls){
char c = ss[r];
if(mapt.containsKey(c)){
maps.put(c, maps.getOrDefault(c, 0) + 1);
if(maps.get(c).equals(mapt.get(c)))
match++;
}
while(match == mapt.size()){
if(r - l + 1 < min){
min = r - l + 1;
left = l;
}
if(mapt.containsKey(ss[l])){
maps.put(ss[l], maps.get(ss[l]) - 1);
if(maps.get(ss[l]).equals(mapt.get(ss[l]) - 1)){
match--;
}
}
l++;
}
r++;
}
return left < 0 ? "" : s.substring(left, left + min);
}
}
另外特别注意：我第一次写的代码中，比较逻辑我都是直接用的“==”，但是提交以后就会发现，最后一个示例报错，然后还怎么查都找不到问题
然后就想看看题解怎么写的， 发现真有一个人说了这个问题，原因是这样：
Integer是对象
Integer会缓存频繁使用的数值，
数值范围为-128到127，在此范围内直接返回缓存值。
超过该范围就会new 一个对象。这个范围是可以修改的，在vm中修改即可调整缓存大小。
然后最后一个示例中，应该是一个字母的个数超过了127，然后比较的时候，就导致创建了一个对象，然后对象用==相比较就是比较的地址，而不是数值了，所以会出错，以后要特别注意这一点
public static Integer valueOf(int i) {
if (i >= IntegerCache.low && i <= IntegerCache.high)
return IntegerCache.cache[i + (-IntegerCache.low)];
return new Integer(i);
}
private static class IntegerCache {
static final int low = -128;
static final int high;
static final Integer cache[];
static {
int h = 127;
String integerCacheHighPropValue =
sun.misc.VM.getSavedProperty("java.lang.Integer.IntegerCache.high");
if (integerCacheHighPropValue != null) {
try {
int i = parseInt(integerCacheHighPropValue);
i = Math.max(i, 127);
h = Math.min(i, Integer.MAX_VALUE - (-low) -1);
} catch( NumberFormatException nfe) {
}
}
high = h;
cache = new Integer[(high - low) + 1];
int j = low;
for(int k = 0; k < cache.length; k++)
cache[k] = new Integer(j++);
assert IntegerCache.high >= 127;
}
那么换成子序列的话，怎么做呢
727. 最小窗口子序列
题目描述
给定字符串 S and T，找出 S 中最短的（连续）子串 W ，使得 T 是 W 的 子序列 。
如果 S 中没有窗口可以包含 T 中的所有字符，返回空字符串 “”。
如果有不止一个最短长度的窗口，返回开始位置最靠左的那个。
示例 1：
输入：
S = “abcdebdde”, T = “bde”
输出：“bcde”
解释：
“bcde” 是答案，因为它在相同长度的字符串 “bdde” 出现之前。
“deb” 不是一个更短的答案，因为在窗口中必须按顺序出现 T 中的元素。
注：
所有输入的字符串都只包含小写字母。
S 长度的范围为 [1, 20000]。
T 长度的范围为 [1, 100]。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-window-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
斥巨资开了个力扣年费会员，然后来看这道题
之前网上查的时候很多方法都是滑动窗口，先向右滑找到右边界，然后向左，找到第一个不符合条件的位置；然后从这个位置再开始滑动，说实话，这种方法，我觉得感觉就是在暴力匹配，没啥技术含量，所以我就不写了。
还是看动态规划，第一个方法给的就是在S中不断找T的前缀，然后依次扩展
用两个数组来分别统计，以上一个T中的字母为结尾的前缀出现的位置（第一个字母出现的位置），例如pre[i] = j，就是s中从 j 位置开始到 i 位置结束，使得T前缀是其中的子序列（有点绕，看代码明白点）
另一个数组统计以当前T中的字母结尾的前缀出现位置。
其实两个数组统计的是一个东西，只不过因为要用上一个数组，所以不能直接覆盖
class Solution {
public String minWindow(String s1, String s2) {
int l1 = s1.length();
int l2 = s2.length();
char[] c2 = s2.toCharArray();
int[] pre = new int[l1];
Arrays.fill(pre, -1);
for(int i = 0; i < l1; i++){
if(s1.charAt(i) == c2[0]){
pre[i] = i;
}
}
for(int i = 1; i < l2; i++){
char c = c2[i];
int last = -1;
int[] cur = new int[l1];
Arrays.fill(cur, -1);
for(int j = 0; j < l1; j++){
if(last != -1 && s1.charAt(j) == c){
cur[j] = last;
}
if(pre[j] != -1)
last = pre[j];
}
for(int j = 0; j < l1; j++){
pre[j] = cur[j];
}
}
int min = l1 + 1;
int left = -1;
for(int i = 0; i < l1; i++){
if(pre[i] != -1){
int len = i - pre[i] + 1;
if(len < min){
left = pre[i];
min = len;
}
}
}
return left == -1 ? "" : s1.substring(left, left + min);
}
}
|