讨论/技术交流/滑动窗口 (周分析)/
滑动窗口 (周分析)

公平的糖果棒交换

爱丽丝和鲍勃有不同大小的糖果棒:A[i] 是爱丽丝拥有的第 i 根糖果棒的大小,B[j] 是鲍勃拥有的第 j 根糖果棒的大小。

因为他们是朋友,所以他们想交换一根糖果棒,这样交换后,他们都有相同的糖果总量。(一个人拥有的糖果总量是他们拥有的糖果棒大小的总和。)

返回一个整数数组 ans,其中 ans[0] 是爱丽丝必须交换的糖果棒的大小,ans[1] 是 Bob 必须交换的糖果棒的大小。

如果有多个答案,你可以返回其中任何一个。保证答案存在。

//设定x,y 进行求第一个解
class Solution{
		public int[] fairCandySwap(int[] A,int[] B){
				int sumA = 0;
				int sumB = 0;
				for(int one:A){
						sumA+=one;
				}
				for(int one:B){
						sumB+=one;
				}
				for(int i = 0;i<A.length;i++){
						for(int j = 0;j<B.length;j++){
								if(sumA-A[i]+B[j] == sumB-B[j]+A[i]){
										return new int[]{A[i],B[j]};
								}
						}
				}
				return new int[];
		}
}

替换后的最长重复字符

给你一个仅由大写英文字母组成的字符串,你可以将任意位置上的字符替换成另外的字符,总共可最多替换 k 次。在执行上述操作后,找到包含重复字母的最长子串的长度。

注意:字符串长度 和 k 不会超过 10 的4次方。

//首先分析题目要求
// 1. 仅由大写英文字母组成,可以想到哈希表 用来存储和分析组成成分
// 2. 最多可以替换k次 
// 3. 最长字串 说明了是连续的内容,可以使用滑动窗口的方式 解决这个问题。因为控制滑动窗口的移动,
// 可以保证连续性

// 来分析解题思路,首先要确认的是 如何在使用最小的转换次数内保证重复的字母最多呢?
// 应该是 修改除了出现次数最多的 哪个字母来进行。
// 但是题目要求必须是连续的 应该如何控制呢?所以只需要保证同时满足 两个条件就可以 保证
// 当前滑动窗口内的字母出现次数最多 

// 滑动窗口的编写注意事项有
// 1. 确定滑动窗口 在哪个 字符串(可是数组也可以是其他的 链表之类的)上进行左右滑动
// 2. 确定起始位置 这里面的起始位置 包括 left(一般是0 和被动运动) 和 right(一般为最小长度
// ,主动向单一方向移动)。
// 3. 确定left 是如何移动,这点很重要。
class Solution{
		public int characterReplacement(String s,int k){
				if(s.length()<2){
						return s.length();
				}
				int length = s.length();
				int[] record = new int[26];
				char[] charsLength = s.CharArray();
				int lengthMax = 0;
				int right = 0;
				int left = 0;
				while(right <length){
					record(charsLength[right]-'A')++;
					lengthMax = Math.max(lengthMax,recrd(charsLength[right]-'A'));
					right++;
					if(right-left>lengthMax+k){
							record[charsLength[left] - 'A']--;
							left++;
					}
				}
				return right- left;
		}
}


滑动窗口中位数

中位数是有序序列最中间的那个数。如果序列的长度是偶数,则没有最中间的数;此时中位数是最中间的两个数的平均数。

例如:

[2,3,4],中位数是 3
[2,3],中位数是 (2 + 3) / 2 = 2.5
给你一个数组 nums,有一个长度为 k 的窗口从最左端滑动到最右端。窗口中有 k 个数,每次窗口向右移动 1 位。你的任务是找出每次窗口移动后得到的新窗口中元素的中位数,并输出由它们组成的数组。

// 从题目上理解就是简单的滑动窗口的方式解决 问题
// 只不过在每一次滑动窗口 中需要进行一次中位数的计算并且放入指定数组中
// 由于是指定数组 需要提前预估数组的大小 大小应该为滑动窗口长度-k+1 (长度的判断可以使用极限值的
// 方式)
// 还需要注意的是保留小数的处理
class Solution{
		public double[] medianSlidingWindow(int[] nums, int k){
				double[] result = new double[nums.length-k+1];
				int right = k-1;
				int left = 0;
				int length = nums.length;
				while(right < length){
						ArrayList<Integer> list = new ArrayList<>();
						for(int i = left;i <=right){
							list.add(nums[i]);
						}
						list.sort(Comparator.comparingInt(a->a));
						if(list.size()%2 == 0){
							result[left] = (Double.valueOf(list.get(list.size()/2-1) + Double.valueOf(list.
get(list.size()/2))))/2d;
						}else{
							result[left] = list.get(list.size()/2);
						}
						right++;
						left++;
				}
				return result;
		}
}

// 此方法会效率不高
// 建议使用第二种方式 就是使用大根堆和小根堆 以及延迟删除的方式解决这个问题
// 我们思考中位数的性质:如果一个数是中位数,那么在这个数组中,大于中位数的数目和小于中位数的
// 数目,要么相等,要么就相差一。
// 因此,我们采用对顶堆的做法,控制所有小于等于中位数的数组放到一个堆中,控制所有比中位数大的数字
// 放到另一个堆中,并且保证两个堆的数目相差小于等于1,这样就可以保证每一次查询中位数的时候,答案
// 一定出于两个堆的堆顶元素之一。
// 因此选定数据结构:优先队列。因为优先队列采用的是堆结构。正好符合我们的需求。我们将所有小于等于
// 中位数的元素放到small堆中(是一个大顶堆),将所有大于中位数的元素都放到big堆中(是一个小顶堆)。

子数组最大平均数I

给定n个整数,找出平均数最大且长度为k的连续子数组,并输出该最大平均数。

// 先说下解题思路,首先看到连续子数组 第一个反应就是滑动窗口,
// 接下来在看平均数 这里联想到滑动窗口的移动轨迹,可以初步想出 当到临界点时可以使用添加right
// 和删除left 时,直接拿avg + (A[right]-A[left] )/k 计算平均值。 减少重复循环的时间浪费。
class Solution{
		boolean flagOne = true;
		double sumOne = 0d;
		public double findMaxAverage(int[] nums,int k){
				double result = 0d;
				int right = k;
				boolean flag = true;
				int length = nums.length;
				int left = 0;
				while(right<=length){
					if(flag){
							result = getAVG(nums,right,left);
							flag = false;
					}else{
							result = Math.max(result,getAVG(nums,right,left));
					}
					right++;
					left++;
				}
				return result;
		}
		private double getAVG(int[] nums,int right,int left){
				if(flagOne){
					for(int i=left;i<right;i++){
						sumOne += nums[i];
					}
					flagOne = false;
				}else{
					sumOne +=nums[right-1];
					sumOne -= nums[left-1];
				}
				return (sumOne/(double)(right - left));
		}
}

// 但是 这个解题思路有些麻烦了,
// 第二个思路,由于规定了子数组的长度为k,因此可以通过寻找子数组的最大元素和的方式寻找子数组的最大
// 平均数,元素和最大的子数组对应的平均数也是最大的。
class Solution{
			public double findMaxAverage(int[] nums,int k){
					int sum = 0;
					int n = nums.length;
					for(int i = 0;i<k;i++){
						sum +=nums[i];
					}
					int maxSum = sum;
					for(int i = k;i<length;i++){
							sum = sum - nums[i-k] + nums[i];
							maxSum = Math.max(maxSum,sum);
					}
					return 1.0 * maxSum/k;
		}
}

尽可能使字符串相等

给你两个长度相同的字符串,s和t。

将s中的第i个字符变到t中的第i个字符需要|s[i]-t[i]|的开销(开销可能为0),也就是两个字符的ASCII码值的差的绝对值。

用于变更字符串的最大预算是maxCost,在转化字符串的时候,总开销应当小于等于预算,这也意味着字符串的转化可能是不完全的。

如果你可以将s的字符串转化为它在t中对应的字符串,则返回可以转化的最大长度。

如果s中没有字符串可以转化为t中的字符串,则返回0;

/**
	* 将差值作为一个目标对象,使用滑动窗口进行移动获取最大的值
**/

class Solution{
		public int equalSubstring(String s,String t,int maxCost){
				ArrayList<Integer> nums = new ArrayList<>();
				for(int i = 0;i<s.length();i++){
						nums.add(Math.abs(s.charAt(i) - t.charAt(i)));
				}
				int left = 0;
				int right =0;
				int length = 0;
				int code  = maxCost;
				while(right<nums.size()&& left<=right){
						code -= nums.get(right);
						if(code >= 0){
								
						}else if (right == left){
								left++;
								code = maxCost;
						}else{
								length = Math.max(length,right-left);
								code += nums.get(left);//还回来
								left++;
						}
						right++;
				}
				return Math.max(length,right-left);
		}
}

可获得的最大点数

几张卡牌 排成一行,每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。

每次行动,你可以从行的开头或者末尾拿一张卡牌,最终你必须正好拿 k 张卡牌。

你的点数就是你拿到手中的所有卡牌的点数之和。

给你一个整数数组 cardPoints 和整数 k,请你返回可以获得的最大点数。

// 将目标对象进行重新构建为 k-0 0-k 的一个数组,滑动窗口从左面移动到右面进行计算。
class Solution{
			private int sum = 0;
			private boolean start = true;
			public int maxSore(int[] cardPoints,int k){
					int[] card = new int[k];
					for(int i =0;i<k;i++){
							card[i] = cardPonits(cardPoints.length -i-1);
					}
					int cardStart = k;
					int pointStart = 0;
					int max = 0;
					while(pointStart<=k){
							max = Math.max(max,whereToGo(cardStart,pointStart,card,cardPoints));
							cardStart--;
							pointStart++;
					}
					return max;
			}

			private int whereToGo(int card,int point,int[] cardArray,int[] cardPonint){
					if(start){
							for(int i =0 ;i<card;i++){
								sum+=cardArray[i];
							}
							start = false;
					}else{
							sum -=cardArray[card];
							sum += cardPoint[point-1];
					}
					return sum;
			}
}
1
共 0 个回复
暂无回复