class049 滑动窗口技巧与相关题目【算法】

class049 滑动窗口技巧与相关题目【算法】

算法讲解049【必备】滑动窗口技巧与相关题目
在这里插入图片描述

code1 209. 长度最小的子数组

// 累加和大于等于target的最短子数组长度
// 给定一个含有 n 个正整数的数组和一个正整数 target
// 找到累加和 >= target 的长度最小的子数组并返回其长度
// 如果不存在符合条件的子数组返回0
// 测试链接 : https://leetcode.cn/problems/minimum-size-subarray-sum/

package class049;

// 累加和大于等于target的最短子数组长度
// 给定一个含有 n 个正整数的数组和一个正整数 target
// 找到累加和 >= target 的长度最小的子数组并返回其长度
// 如果不存在符合条件的子数组返回0
// 测试链接 : https://leetcode.cn/problems/minimum-size-subarray-sum/
public class Code01_MinimumSizeSubarraySum {

	public static int minSubArrayLen(int target, int[] nums) {
		int ans = Integer.MAX_VALUE;
		for (int l = 0, r = 0, sum = 0; r < nums.length; r++) {
			sum += nums[r];
			while (sum - nums[l] >= target) {
				// sum : nums[l....r]
				// 如果l位置的数从窗口出去,还能继续达标,那就出去
				sum -= nums[l++];
			}
			if (sum >= target) {
				ans = Math.min(ans, r - l + 1);
			}
		}
		return ans == Integer.MAX_VALUE ? 0 : ans;
	}

}

code2 3. 无重复字符的最长子串

// 无重复字符的最长子串
// 给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。
// 测试链接 : https://leetcode.cn/problems/longest-substring-without-repeating-characters/

package class049;

import java.util.Arrays;

// 无重复字符的最长子串
// 给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。
// 测试链接 : https://leetcode.cn/problems/longest-substring-without-repeating-characters/
public class Code02_LongestSubstringWithoutRepeatingCharacters {

	public static int lengthOfLongestSubstring(String str) {
		char[] s = str.toCharArray();
		int n = s.length;
		// char -> int -> 0 ~ 255
		// 每一种字符上次出现的位置
		int[] last = new int[256];
		// 所有字符都没有上次出现的位置
		Arrays.fill(last, -1);
		// 不含有重复字符的 最长子串 的长度
		int ans = 0;
		for (int l = 0, r = 0; r < n; r++) {
			l = Math.max(l, last[s[r]] + 1);
			ans = Math.max(ans, r - l + 1);
			// 更新当前字符上一次出现的位置
			last[s[r]] = r;
		}
		return ans;
	}

}

code3 76. 最小覆盖子串

// 最小覆盖子串
// 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串
// 如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 “” 。
// 测试链接 : https://leetcode.cn/problems/minimum-window-substring/

package class049;

// 最小覆盖子串
// 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串
// 如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 "" 。
// 测试链接 : https://leetcode.cn/problems/minimum-window-substring/
public class Code03_MinimumWindowSubstring {

	public static String minWindow(String str, String tar) {
		if (str.length() < tar.length()) {
			return "";
		}
		char[] s = str.toCharArray();
		char[] t = tar.toCharArray();
		int[] cnts = new int[256];
		for (char cha : t) {
			cnts[cha]--;
		}
		// 最小覆盖子串的长度
		int len = Integer.MAX_VALUE;
		// 从哪个位置开头,发现的这个最小覆盖子串
		int start = 0;
		for (int l = 0, r = 0, debt = t.length; r < s.length; r++) {
			// s[r] 当前字符 -> int
			// cnts[s[r]] : 当前字符欠债情况,负数就是欠债,正数就是多给的
			if (cnts[s[r]]++ < 0) {
				debt--;
			}
			if (debt == 0) {
				// r位置结尾,真的有覆盖子串!
				// 看看这个覆盖子串能不能尽量短
				while (cnts[s[l]] > 0) {
					// l位置的字符能拿回
					cnts[s[l++]]--;
				}
				// 从while里面出来,
				// l....r就是r位置结尾的最小覆盖子串
				if (r - l + 1 < len) {
					len = r - l + 1;
					start = l;
				}
			}
		}
		return len == Integer.MAX_VALUE ? "" : str.substring(start, start + len);
	}

}

code4 134. 加油站

// 加油站
// 在一条环路上有 n 个加油站,其中第 i 个加油站有汽油 gas[i] 升。
// 你有一辆油箱容量无限的的汽车,从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升
// 你从其中的一个加油站出发,开始时油箱为空。
// 给定两个整数数组 gas 和 cost ,如果你可以按顺序绕环路行驶一周
// 则返回出发时加油站的编号,否则返回 -1
// 如果存在解,则 保证 它是 唯一 的。
// 测试链接 : https://leetcode.cn/problems/gas-station/

package class049;

// 加油站
// 在一条环路上有 n 个加油站,其中第 i 个加油站有汽油 gas[i] 升。
// 你有一辆油箱容量无限的的汽车,从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升
// 你从其中的一个加油站出发,开始时油箱为空。
// 给定两个整数数组 gas 和 cost ,如果你可以按顺序绕环路行驶一周
// 则返回出发时加油站的编号,否则返回 -1
// 如果存在解,则 保证 它是 唯一 的。
// 测试链接 : https://leetcode.cn/problems/gas-station/
public class Code04_GasStation {

	public static int canCompleteCircuit(int[] gas, int[] cost) {
		int n = gas.length;
		// 车辆尝试从0~n-1出发,看能不能走一圈,l
		// r : 窗口即将进来数字的位置
		// len : 窗口大小
		// sum : 窗口累加和
		for (int l = 0, r = 0, len = 0, sum = 0; l < n; l++) {
			while (sum >= 0) {
				// 当前窗口累加和>=0,尝试扩
				if (len == n) {
					return l;
				}
				// r : 窗口即将进来数字的位置
				r = (l + (len++)) % n;
				sum += gas[r] - cost[r];
			}
			// sum < 0,此时l位置无法转一圈
			len--;
			sum -= gas[l] - cost[l];
		}
		return -1;
	}

}

code5 1234. 替换子串得到平衡字符串

// 替换子串得到平衡字符串
// 有一个只含有 ‘Q’, ‘W’, ‘E’, ‘R’ 四种字符,且长度为 n 的字符串。
// 假如在该字符串中,这四个字符都恰好出现 n/4 次,那么它就是一个「平衡字符串」。
// 给你一个这样的字符串 s,请通过「替换一个子串」的方式,使原字符串 s 变成一个「平衡字符串」。
// 你可以用和「待替换子串」长度相同的 任何 其他字符串来完成替换。
// 请返回待替换子串的最小可能长度。
// 如果原字符串自身就是一个平衡字符串,则返回 0。
// 测试链接 : https://leetcode.cn/problems/replace-the-substring-for-balanced-string/

package class049;

// 替换子串得到平衡字符串
// 有一个只含有 'Q', 'W', 'E', 'R' 四种字符,且长度为 n 的字符串。
// 假如在该字符串中,这四个字符都恰好出现 n/4 次,那么它就是一个「平衡字符串」。
// 给你一个这样的字符串 s,请通过「替换一个子串」的方式,使原字符串 s 变成一个「平衡字符串」。
// 你可以用和「待替换子串」长度相同的 任何 其他字符串来完成替换。
// 请返回待替换子串的最小可能长度。
// 如果原字符串自身就是一个平衡字符串,则返回 0。
// 测试链接 : https://leetcode.cn/problems/replace-the-substring-for-balanced-string/
public class Code05_ReplaceTheSubstringForBalancedString {

	// Q W E R
	// 0 1 2 3
	// "W Q Q R R E"
	// 1 0 0 3 3 2
	// cnts[1] = 1;
	// cnts[0] = 2;
	// cnts[2] = 1;
	// cnts[3] = 2;
	public static int balancedString(String str) {
		int n = str.length();
		int[] arr = new int[n];
		int[] cnts = new int[4];
		for (int i = 0; i < n; i++) {
			char c = str.charAt(i);
			arr[i] = c == 'W' ? 1 : (c == 'E' ? 2 : (c == 'R' ? 3 : 0));
			cnts[arr[i]]++;
		}
		// str : 长度是4的整数倍,n
		// 每种字符出现的个数 : n/4
		int require = n / 4;
		// 至少要修改多长的子串,才能做到四种字符一样多
		int ans = n;
		// 自由变化的窗口l....r
		for (int l = 0, r = 0; l < n; l++) {
			// l = 0, r= 0, 窗口0长度
			// l...r-1 : [l,r)
			while (!ok(cnts, r - l, require) && r < n) {
				// cnts : 窗口之外的统计
				cnts[arr[r++]]--;
			}
			// 1) l...r-1 [l,r) ,做到了!
			// 2) r == n,也没做到
			if (ok(cnts, r - l, require)) {
				ans = Math.min(ans, r - l);
			}
			// [l,r),不被cnts统计到的
			//   l+1
			cnts[arr[l]]++;
		}
		return ans;
	}

	// cnts : l...r范围上的字符不算!在自由变化的窗口之外,每一种字符的词频统计
	// len : 自由变化窗口的长度
	// require : 每一种字符都要达到的数量
	// 返回值 : 请问能不能做到
	public static boolean ok(int[] cnts, int len, int require) {
		for (int i = 0; i < 4; i++) {
			// 0 1 2 3
			if (cnts[i] > require) {
				return false;
			}
			// require - cnts[i] : 20 - 16 = 4
			len -= require - cnts[i];
		}
		return len == 0;
	}

}

code6 992. K 个不同整数的子数组

// K个不同整数的子数组
// 给定一个正整数数组 nums和一个整数 k,返回 nums 中 「好子数组」 的数目。
// 如果 nums 的某个子数组中不同整数的个数恰好为 k
// 则称 nums 的这个连续、不一定不同的子数组为 「好子数组 」。
// 例如,[1,2,3,1,2] 中有 3 个不同的整数:1,2,以及 3。
// 子数组 是数组的 连续 部分。
// 测试链接 : https://leetcode.cn/problems/subarrays-with-k-different-integers/

转化:
严格等于k的子数组个数:f(nums,k)-f(nums,k-1)
f函数是不超过k的子数组个数

package class049;

import java.util.Arrays;

// K个不同整数的子数组
// 给定一个正整数数组 nums和一个整数 k,返回 nums 中 「好子数组」 的数目。
// 如果 nums 的某个子数组中不同整数的个数恰好为 k
// 则称 nums 的这个连续、不一定不同的子数组为 「好子数组 」。
// 例如,[1,2,3,1,2] 中有 3 个不同的整数:1,2,以及 3。
// 子数组 是数组的 连续 部分。
// 测试链接 : https://leetcode.cn/problems/subarrays-with-k-different-integers/
public class Code06_SubarraysWithKDifferentIntegers {

	public static int subarraysWithKDistinct(int[] arr, int k) {
		return numsOfMostKinds(arr, k) - numsOfMostKinds(arr, k - 1);
	}

	public static int MAXN = 20001;

	public static int[] cnts = new int[MAXN];

	// arr中有多少子数组,数字种类不超过k
	// arr的长度是n,arr里的数值1~n之间
	public static int numsOfMostKinds(int[] arr, int k) {
		Arrays.fill(cnts, 1, arr.length + 1, 0);
		int ans = 0;
		for (int l = 0, r = 0, collect = 0; r < arr.length; r++) {
			// r(刚进)
			if (++cnts[arr[r]] == 1) {
				collect++;
			}
			// l.....r    要求不超过3种,已经4种,l往右(吐数字)
			while (collect > k) {
				if (--cnts[arr[l++]] == 0) {
					collect--;
				}
			}
			// l.....r不超过了
			// 0...3
			// 0~3
			// 1~3
			// 2~3
			// 3~3
			ans += r - l + 1;
		}
		return ans;
	}

}

code7 395. 至少有 K 个重复字符的最长子串

// 至少有K个重复字符的最长子串
// 给你一个字符串 s 和一个整数 k ,请你找出 s 中的最长子串
// 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度
// 如果不存在这样的子字符串,则返回 0。
// 测试链接 : https://leetcode.cn/problems/longest-substring-with-at-least-k-repeating-characters/

转化:
子串必须只有i中字符,>=k次,最长多少(1<=i<=26)
取最大值

package class049;

import java.util.Arrays;

// 至少有K个重复字符的最长子串
// 给你一个字符串 s 和一个整数 k ,请你找出 s 中的最长子串
// 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度
// 如果不存在这样的子字符串,则返回 0。
// 测试链接 : https://leetcode.cn/problems/longest-substring-with-at-least-k-repeating-characters/
public class Code07_LongestSubstringWithAtLeastKRepeating {

	public static int longestSubstring(String str, int k) {
		char[] s = str.toCharArray();
		int n = s.length;
		int[] cnts = new int[256];
		int ans = 0;
		// 每次要求子串必须含有require种字符,每种字符都必须>=k次,这样的最长子串是多长
		for (int require = 1; require <= 26; require++) {
			Arrays.fill(cnts, 0);
			// collect : 窗口中一共收集到的种类数
			// satisfy : 窗口中达标的种类数(次数>=k)
			for (int l = 0, r = 0, collect = 0, satisfy = 0; r < n; r++) {
				cnts[s[r]]++;
				if (cnts[s[r]] == 1) {
					collect++;
				}
				if (cnts[s[r]] == k) {
					satisfy++;
				}
				// l....r 种类超了!
				// l位置的字符,窗口中吐出来!
				while (collect > require) {
					if (cnts[s[l]] == 1) {
						collect--;
					}
					if (cnts[s[l]] == k) {
						satisfy--;
					}
					cnts[s[l++]]--;
				}
				// l.....r : 子串以r位置的字符结尾,且种类数不超的,最大长度!
				if (satisfy == require) {
					ans = Math.max(ans, r - l + 1);
				}
			}
		}
		return ans;
	}

}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/222516.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

docker配置阿里云镜像加速器

docker配置阿里云镜像加速器 1.注册一个阿里云账户 https://cr.console.aliyun.com/ 2.获取加速器地址链接 可直接复制&#xff0c;位置如下: 3.配置脚本 这个位置可以直接复制脚本&#xff0c;大家操作的时候直接复制自己的就好 sudo mkdir -p /etc/docker sudo tee /et…

应用于指纹门锁上的安全芯片ACM32FP421系列,内核性能高,安全性高,内建 AES、CRC、TRNG 等算法模块

ACM32FP421 芯片的内核基于 ARMv8-M 架构&#xff0c;支持 Cortex-M33 和 Cortex-M4F 指令集。内核支持一 整套 DSP 指令用于数字信号处理&#xff0c;支持单精度 FPU 处理浮点数据&#xff0c;同时还支持 Memory Protection Unit &#xff08;MPU&#xff09;用于提升应用的安…

数字化未来,亚马逊鲲鹏系统引领全新购物下单体验

随着科技的不断发展&#xff0c;人们的购物方式也在发生翻天覆地的变化。在这个数字化时代&#xff0c;亚马逊鲲鹏系统应运而生&#xff0c;成为一款集注册、买家号智能养号、自动下单、自动留评、QA等功能于一体的综合软件&#xff0c;为用户提供了全新的购物体验。 首先&…

RocketMQ-源码架构二

梳理一些比较完整&#xff0c;比较复杂的业务线 消息持久化设计 RocketMQ的持久化文件结构 消息持久化也就是将内存中的消息写入到本地磁盘的过程。而磁盘IO操作通常是一个很耗性能&#xff0c;很慢的操作&#xff0c;所以&#xff0c;对消息持久化机制的设计&#xff0c;是…

单片机的基本概念——什么是单片机、单片机的分类以及单片机的发展历史、发展趋势

什么是单片机 本文主要涉及了什么是单片机、单片机的分类、单片机发展史以及单片机的发展趋势的一些内容 文章目录 什么是单片机一、 什么是单片机1.1 微型计算机1.2 单板机1.3 单片机1.3.1 单片机的分类 二、 单片机的发展历史2.1 发展阶段2.2 单片机的特点2.3 单片机的发展趋…

ACM32F403/F433 12 位多通道,支持 MPU 存储保护功能,应用于工业控制,智能家居等产品中

ACM32F403/F433 芯片的内核基于 ARMv8-M 架构&#xff0c;支持 Cortex-M33 和 Cortex-M4F 指令集。芯片内核 支持一整套DSP指令用于数字信号处理&#xff0c;支持单精度FPU处理浮点数据&#xff0c;同时还支持Memory Protection Unit &#xff08;MPU&#xff09;用于提升应用的…

【Kubernetes】kubeadm安装k8s1.25.0高可用集群

k8s集群搭建&#xff08;v1.25.0&#xff09; 一、初始化实验环境二、安装containerd服务2.1、安装containerd2.2、安装docker2.3、配置镜像加速器三、安装初始化k8s需要的软件包四、kubeadm初始化k8s集群4.1、设置容器运行时4.2、生成并修改配置文件4.2、初始化安装4.3、修改c…

C语言之数组(精讲)

目录 数组 数组的声明&#xff08;使用数组前的准备&#xff09; 访问数组&#xff08;数组的使用方法&#xff09; 数组的遍历 数组初始化 1.在声明变量时&#xff0c;除了必要的情况下&#xff0c;都需要对变量进行初始化。 2.我们还可以像下面在声明数组时不指定元素…

win10与 vm虚拟机win7共享文件夹创建

1:在win10&#xff08;主机&#xff09;电脑先随意共享一个文件夹 2&#xff1a;在win10&#xff08;主机&#xff09;上创建一个网络映射 右键此电脑选择映射网络驱动器 成功后会多出这个网络位置 3&#xff1a;win7虚拟机设置 在虚拟机中点击计算机右键添加一个网络位置

云HIS:新一代云架构医院信息管理系统源码(java语言)

云HIS信息管理云平台&#xff0c;提供全方位的临床系统应用&#xff0c;是国内领先的以云计算为基础&#xff0c;以云计算赋能医疗机构&#xff0c;是颠覆传统医疗信息化业态的技术与模式创新&#xff0c;以SaaS方式&#xff0c;为医疗机构提供信息系统服务&#xff0c;满足从医…

Scrapy爬虫数据存储为JSON文件的解决方案

什么是JSON文件 JSON&#xff08;JavaScript Object Notation&#xff09;是一种轻量级的数据交换格式&#xff0c;易于人们阅读和编写&#xff0c;同时也易于机器解析和生成。它基于JavaScript Spark语言的一个子集&#xff0c;但独立于Smashing语言&#xff0c;因此在许多中…

【面试经典150 | 二叉树】翻转二叉树

文章目录 写在前面Tag题目来源题目解读解题思路方法一&#xff1a;递归方法二&#xff1a;迭代 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法&#xff0c;两到三天更新一篇文章&#xff0c;欢迎催更…… 专栏内容以分析题目为主&#xff0c;并附带一些对于本题…

Linux 编译过程分析

文章目录 一、源码foo.hhello.cfoo1.cfoo2.c GCC 指令预处理命令hello.i 编译&#xff08;Compile only&#xff09;命令foo2.s 汇编命令readelfreadelf -hreadelf -Sreadelf -rreadelf -sstrip 链接 本文基于《深度探索Linux操作系统&#xff1a;系统构建和原理解析》 一、源…

2022年南美地区医疗机器人市场及全球概况报告

今天分享的是机器人系列深度研究报告&#xff1a;《2022年南美地区医疗机器人市场及全球概况报告》。 &#xff08;报告出品方&#xff1a;Apollo Reports&#xff09; 报告共计&#xff1a;172页 研究方法论 2.1通过桌面研究和内部存储库的假设 a)最初&#xff0c;各个类别…

深度学习实战64-黑白照片着色的模型应用,快速部署实现黑白图片快速上色的功能

大家好,我是微学AI,今天给大家介绍一下深度学习实战64-黑白照片着色的模型应用,快速部署实现黑白图片快速上色的功能。图片上色是一个具有多模态不确定性和高度不适定性的挑战性问题。直接训练深度神经网络通常会导致错误的语义颜色和低色彩丰富度。虽然基于Transformer的方…

从零开始学习 JS APL(六):完整指南和实例解析

学习目标&#xff1a; 1. 能够利用正则表达式校验输入信息的合法性 2. 具备利用正则表达式验证小兔鲜注册页面表单的能力 学习内容&#xff1a; 正则表达式 综合案例 阶段案例 学习时间&#xff1a; 周一至周五晚上 7 点—晚上9点周六上午 9 点-上午 11 点周日下午 3 点-下…

力扣11.盛最多水的容器

题目描述 思路 用双指针法。 每次向内移动较短的那个板&#xff0c;能带来更大的效益。 代码 class Solution {public int maxArea(int[] height) {int res 0;int i 0,j height.length - 1;while(i < j){res height[i] < height[j] ? Math.max((j - i) * height…

BearPi Std 板从入门到放弃 - 引气入体篇(7)(DAC)

简介 基于前面的文章, 缩略STM32CubeMx创建项目的过程&#xff0c;直接添加DAC相关初始化; 开发板 &#xff1a; Bearpi Std(小熊派标准板) 主芯片: STM32L431RCT6 LED : PC13 \ 推挽输出即可 \ 高电平点亮 串口: Usart1 KEY1 : PB2 \ 上拉 \ 按下下降沿触发(一次)\ 用于增…

2024年MCM/ICM美国大学生数学建模竞赛备战指南

01 2024美赛基本要求 1.关于时间&#xff08;北京时间&#xff09; 比赛开始时间&#xff1a; 2024年2月2日6:00至 2024年2月6日9:00 提交截止时间&#xff1a;2024年2月6日10:00 结果发布时间&#xff1a;结果将于2024年5月31日或之前发布 2.关于规则 完整的解决方案现…

海上液化天然气 LNG 终端 ,数字孪生监控系统

液化天然气 (Liquefied Natural Gas&#xff0c;简称 LNG) 在能源转型过程中被广泛认可为相对较清洁的能源选择。 相对于传统的煤炭和石油燃料&#xff0c;LNG 的燃烧过程产生的二氧化碳 (CO2) 排放较低。LNG 的燃烧释放的二氧化碳排放较少&#xff0c;因此对应对气候变化和减…