一、将x减到0的最小操作数
给你一个整数数组 nums
和一个整数 x
。每一次操作时,你应当移除数组 nums
最左边或最右边的元素,然后从 x
中减去该元素的值。请注意,需要 修改 数组以供接下来的操作使用。
如果可以将 x
恰好 减到 0
,返回 最小操作数 ;否则,返回 -1
输入:nums = [1,1,4,2,3], x = 5 输出:2 解释:最佳解决方案是移除后两个元素,将 x 减到 0 。
题意:
给定一个数组nums和一个整数x;每次操作的时候,移除左边和右边的元素,使得移除元素之和=x
思路:
一般从两边移除元素,有两种思路;
1.逆向思维,在数组中找到一个滑动窗口,和为sum-x,结果就为num.length-滑动窗口的长度
2.正向思维,前缀和后缀;
代码:
逆向思维:
class Solution {
public int minOperations(int[] nums, int x) {
int total = 0;
for(int num:nums){
total+=num;
}
if(total<x)return -1;
int left=0;
int right=0;
int max=-1;
int sum=0;
while(right<nums.length){
sum+=nums[right];
while(sum>total-x){
sum-=nums[left];
left++;
}
if(sum==total-x){
max=Math.max(max,right-left+1);
}
right++;
}
return max==-1?-1:nums.length-max;
}
}
正向思维:
二、最高频元素的频数(排序+滑动窗口)
元素的 频数 是该元素在一个数组中出现的次数。
给你一个整数数组 nums
和一个整数 k
。在一步操作中,你可以选择 nums
的一个下标,并将该下标对应元素的值增加 1
。
执行最多 k
次操作后,返回数组中最高频元素的 最大可能频数 。
输入:nums = [1,2,4], k = 5 输出:3 解释:对第一个元素执行 3 次递增操作,对第二个元素执 2 次递增操作,此时 nums = [4,4,4] 。 4 是数组中最高频元素,频数是 3 。
思路:使用滑动窗口的思路(条件是操作数<=k)
当操作数>k之后,就要移动left;left需要移动到costK不大于k
while(costK>k){
costK-=nums[right]-nums[left];
left++;
}
如果<k,移动right;移动right的时候,需要更新costK,costK=(nums[right]-nums[right-1])*(right-left);因为所有的数字都变成了nums[right-1]了,然后一共有right-left个数字;
costK+=(long)(nums[right]-nums[right-1])*(right-left);
移动的过程中寻找最大值;
注意:costK的类型要是long,可能溢出
代码:
class Solution {
public int maxFrequency(int[] nums, int k) {
Arrays.sort(nums);
int left=0;
int right=1;
int res=1;
long costK = 0;
while(right<nums.length){
costK+=(long)(nums[right]-nums[right-1])*(right-left);
while(costK>k){
costK-=nums[right]-nums[left];
left++;
}
res=Math.max(res,right-left+1);
right++;
}
return res;
}
}
三、每种字符至少取K个
给你一个由字符 'a'
、'b'
、'c'
组成的字符串 s
和一个非负整数 k
。每分钟,你可以选择取走 s
最左侧 还是 最右侧 的那个字符。
你必须取走每种字符 至少 k
个,返回需要的 最少 分钟数;如果无法取到,则返回 -1
。
题意:
思路:逆向思维
题目中要求从左边或者右边取,将a\b\c三个字符取出最少K类,求最小的操作次数;
1.首先统计出字符串中字符的数目
2.然后减去k个,如果减去之后变为负数,返回-1
3.然后开始滑
逆向思维就是:题目中是否存在一段子串满足字符出现最多的次数为:count[0]-k,count[1]-k,count[2]-k。求出这段子串的最大长度
eg:"aabaaaacaabc" k=2 a:8 b:2 c:2
然后a\b\c最多出现的次数可以为:6,0,0; 每次遍历到一个字符,就将出现的次数-1(还可以出现多少次),如果出现<0的情况,左边界就要改变了。
代码:
class Solution {
public int takeCharacters(String s, int k) {
if(k==0)return 0;
// 1.统计次数
int[] count=new int[3];
for(int i=0;i<s.length();i++){
char ch=s.charAt(i);
count[ch-'a']++;
}
// 2.将map中的字母-k
for(int i=0;i<3;i++){
if(count[i]<k)return -1;
count[i]-=k;
}
//滑动窗口正文
int left = 0;
int right = 0;
int res = 0;
while (right < s.length()) {
char ch = s.charAt(right);
count[ch-'a']--;
while (count[0] < 0 ||count[1] < 0 || count[2] < 0) {
char ch1 = s.charAt(left);
count[ch1-'a']++;
left++;
}
res = Math.max(res, right - left + 1);
right++;
}
return s.length() - res;
}
}
四、找出最长等值子数组
给你一个下标从 0 开始的整数数组 nums
和一个整数 k
。
如果子数组中所有元素都相等,则认为子数组是一个 等值子数组 。注意,空数组是 等值子数组 。
从 nums
中删除最多 k
个元素后,返回可能的最长等值子数组的长度。
题意:
给定一个数组nums,求子数组中删除k个元素后,所有元素都相等,返回相同元素的最大个数。
思路:
滑动窗口左边界改变的的条件是:但滑动窗口中频率不是最大的数字的总和>k,就要移动左边界,直到总和<k;
while (right-left+1-maxFreq > k) {
int leftNum = nums.get(left);
map.put(leftNum, map.get(leftNum) - 1);
left++;
}
每次更新map哈希表的时候,顺便获取到哈希表中出现频率最多的数字。
int num = nums.get(right);
map.put(num, map.getOrDefault(num, 0) + 1);
maxFreq=Math.max(maxFreq,map.get(num));
代码:
class Solution {
public int longestEqualSubarray(List<Integer> nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
int left = 0;
int right = 0;
int maxFreq = 0;
int res = 1;
while (right < nums.size()) {
//遍历元素 将num统计到map中
int num = nums.get(right);
map.put(num, map.getOrDefault(num, 0) + 1);
maxFreq=Math.max(maxFreq,map.get(num));
//当滑动窗口中其他数字的次数>k时
while (right-left+1-maxFreq > k) {
int leftNum = nums.get(left);
map.put(leftNum, map.get(leftNum) - 1);
left++;
}
res=Math.max(right-left+1,res);
right++;
}
return maxFreq;
}
}
标签:map,right,窗口,nums,int,数组,滑动,不定,left
From: https://blog.csdn.net/2301_78191305/article/details/141798778