Sliding Windows

2024-05-05 21:12
文章标签 windows sliding

本文主要是介绍Sliding Windows，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

209，3，904，76，438，560，239

套路：

初始化左指针，初始化右指针，初始化窗口，初始化结果

右指针循环遍历扩大窗口

进行窗口判断

左指循环针遍历缩小窗口

最大值在扩窗时收集结果，最小值在缩窗时收集结果

 template

import java.util.HashMap;public class SlidingWindow {public void slidingWindow(String s, String t) {HashMap<Character, Integer> need = new HashMap<>();HashMap<Character, Integer> window = new HashMap<>();for (char c : t.toCharArray()) {need.put(c, need.getOrDefault(c, 0) + 1);}int left = 0, right = 0;int valid = 0;while (right < s.length()) {// c 是将移入窗口的字符char c = s.charAt(right);// 右移窗口right++;// 进行窗口内数据的一系列更新// 例如：更新窗口内字符的计数window.put(c, window.getOrDefault(c, 0) + 1);// 当窗口内满足某些条件时进行调试输出System.out.println("window: [" + left + ", " + right + ")");// 判断左侧窗口是否要收缩while (window needs shrink) { // 这里的条件需要根据具体问题来定义// d 是将移出窗口的字符char d = s.charAt(left);// 左移窗口left++;// 进行窗口内数据的一系列更新// 例如：减少窗口内字符的计数window.put(d, window.getOrDefault(d, 1) - 1);}}}public static void main(String[] args) {SlidingWindow sw = new SlidingWindow();sw.slidingWindow("your_string_s", "your_string_t");}
}

209. 长度最小的子数组

中等

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组

[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。7

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
class Solution {// 方法：求最短的子数组，其和至少为 targetpublic int minSubArrayLen(int target, int[] nums) {int left = 0; // 左指针，用于标记子数组的开始位置int sum = 0; // 用于记录当前子数组的和int ans = nums.length + 1; // 初始化答案为一个不可能的大值（数组长度+1）// 遍历数组，右指针 right 表示子数组的结束位置for (int right = 0; right < nums.length; right++) {sum += nums[right]; // 向当前子数组的和中加入 nums[right]// 当当前子数组的和大于等于目标值时，尝试缩小子数组while (sum >= target) {sum -= nums[left]; // 从和中去掉子数组的第一个元素ans = Math.min(ans, right - left + 1); // 更新最小子数组长度left++; // 左指针向右移动，减小子数组的长度}}// 检查是否找到了符合条件的子数组if (ans == nums.length + 1) {return 0; // 如果 ans 仍然是初始化的值，说明没有找到符合条件的子数组，返回 0} else {return ans; // 否则返回找到的最短子数组长度}}
}

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

中等

给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
class Solution {public int lengthOfLongestSubstring(String s) {Set<Character> set = new HashSet<>(); // 使用一个HashSet来记录每个字符是否出现过char[] ch = s.toCharArray(); // 将输入的字符串转换为字符数组，便于索引操作int left = 0; // 左指针，用于表示当前考察的子串的开始位置int count = 0; // 当前窗口的长度int ans = 0; // 用于记录遇到的最长无重复字符子串的长度// 遍历字符串中的每个字符for (int right = 0; right < ch.length; right++) {if (!set.contains(ch[right])) { // 如果当前字符不在HashSet中，说明未重复set.add(ch[right]); // 将此字符加入HashSetcount = count + 1; // 窗口长度增加ans = Math.max(ans, count); // 更新最大长度} else { // 如果当前字符已在HashSet中，说明重复了// 移动左指针，直到移除重复的字符while (set.contains(ch[right])) {set.remove(ch[left]); // 移除左指针处的字符left++; // 左指针向右移动count--; // 窗口长度减少}set.add(ch[right]); // 将当前字符加入HashSetcount++; // 窗口长度增加}}return ans; // 返回最长无重复字符子串的长度}
}


class Solution {public int lengthOfLongestSubstring(String s) {int[] ch = new int[128];for(int i=0;i<128;i++){ch[i]=-1;}int ans=0;int st=0;for(int i=0;i<s.length();i++){int c = s.charAt(i);if(ch[c]!=-1){st=Math.max(st,ch[c]);}ans=Math.max(ans,i-st+1);ch[c]=i+1;}return ans;}
}

904. 水果成篮

中等

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。

你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

  • 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
  • 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
  • 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。

给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。

示例 1：

输入：fruits = [1,2,1]
输出：3
解释：可以采摘全部 3 棵树。

class Solution {public int totalFruit(int[] fruits) {int left = 0;  // 初始化左指针，表示当前子数组的开始位置int right = 0; // 初始化右指针，表示当前子数组的结束位置int resault = 0; // 用于存储最长子数组的长度Map<Integer,Integer> map = new HashMap<>(); // 哈希表用于存储窗口内各种水果的数量// 遍历所有水果for(right = 0; right < fruits.length; right++){// 将当前水果加入到哈希表中，计数加1map.put(fruits[right] , map.getOrDefault(fruits[right] , 0) + 1);// 当哈希表中的水果种类超过2种时，缩小窗口while(map.size() > 2){// 将左指针所在的水果计数减1map.put(fruits[left], map.get(fruits[left]) - 1);// 如果某种水果的数量减到0，从哈希表中移除if(map.get(fruits[left]) == 0){map.remove(fruits[left]);}// 左指针向右移动，缩小窗口left++;}// 更新最大子数组的长度resault = Math.max(resault, right - left + 1);}return resault; // 返回最大长度}
}

76. 最小覆盖子串
困难

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

  • 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
  • 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

class Solution {public String minWindow(String s, String t) {// 边界条件检查if (s == null || t == null || s.length() == 0 || t.length() == 0 || s.length() < t.length()) {return ""; // 如果输入不合理，则返回空字符串}int[] map = new int[128]; // ASCII字符映射表，用于记录字符串t中各字符的数量int count = t.length(); // 需要匹配的字符总数int start = 0, end = 0; // 滑动窗口的起始和结束位置int minLen = Integer.MAX_VALUE; // 最小窗口长度，初始化为最大整数值int startIndex = 0; // 最小窗口的起始索引// 遍历字符串t，初始化字符计数器for (char c : t.toCharArray()) {map[c]++; // 增加t中字符的计数}char[] chS = s.toCharArray(); // 将字符串s转换为字符数组，以便操作// 扩展窗口的右边界while (end < chS.length) {// 当前字符在t中，减少相应的计数，并扩展窗口的右边界if (map[chS[end++]]-- > 0) {count--; // 减少需要匹配的字符计数}// 当所有字符都匹配后while (count == 0) {// 如果当前窗口的长度小于已记录的最小长度，则更新最小窗口if (end - start < minLen) {startIndex = start; // 更新最小窗口起始索引minLen = end - start; // 更新最小窗口长度}// 尝试收缩窗口的左边界，同时更新字符计数器和匹配计数if (map[chS[start++]]++ == 0) {count++; // 如果移除的字符是需要的字符，则增加需要匹配的字符计数}}}// 如果没有找到有效的窗口，则返回空字符串，否则返回最小窗口子字符串return minLen == Integer.MAX_VALUE ? "" : new String(chS, startIndex, minLen);}
}

438. 找到字符串中所有字母异位词
中等

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 1:

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

class Solution {public List<Integer> findAnagrams(String s, String p) {int sLen = s.length(), pLen = p.length(); // s和p的长度if (sLen < pLen) {return new ArrayList<Integer>(); // 如果s的长度小于p的长度，直接返回空列表}List<Integer> ans = new ArrayList<Integer>(); // 存储所有异位词起始索引的列表int[] sCount = new int[26]; // s中的字符计数int[] pCount = new int[26]; // p中的字符计数// 初始化计数数组for (int i = 0; i < pLen; ++i) {++sCount[s.charAt(i) - 'a']; // 对s的前pLen个字符进行计数++pCount[p.charAt(i) - 'a']; // 对p的所有字符进行计数}// 如果初始化时s的前pLen个字符的计数与p的字符计数相同，说明找到一个异位词if (Arrays.equals(sCount, pCount)) {ans.add(0); // 将起始索引0添加到结果列表中}// 遍历s中的每个字符，使用滑动窗口更新字符计数for (int i = 0; i < sLen - pLen; ++i) {--sCount[s.charAt(i) - 'a']; // 移除窗口最左侧的字符计数++sCount[s.charAt(i + pLen) - 'a']; // 添加窗口最右侧的新字符计数// 比较更新后的s计数和p计数是否相同，相同则为异位词if (Arrays.equals(sCount, pCount)) {ans.add(i + 1); // 将当前异位词的起始索引添加到结果列表中}}return ans; // 返回包含所有异位词起始索引的列表}
}

560. 和为 K 的子数组
中等

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

示例 1：

输入：nums = [1,1,1], k = 2
输出：2

示例 2：

输入：nums = [1,2,3], k = 3
输出：2

public class Solution {public int subarraySum(int[] nums, int k) {int count = 0; // 用于计算和为k的子数组数量int pre = 0; // 用于累加前缀和HashMap<Integer, Integer> mp = new HashMap<>(); // 哈希表用来存储前缀和及其出现的次数mp.put(0, 1); // 初始化，对于前缀和为0的情况，假设已经出现一次（处理边界情况，如数组的部分元素和正好为k）for (int i = 0; i < nums.length; i++) {pre += nums[i]; // 累加当前元素到前缀和中// 如果当前前缀和减去k的结果已存在于哈希表中，说明存在一个子数组的和为kif (mp.containsKey(pre - k)) {count += mp.get(pre - k); // 将这些子数组的数量加到count上}// 更新当前前缀和的计数，如果这个前缀和第一次出现，则初始化为1，否则累加mp.put(pre, mp.getOrDefault(pre, 0) + 1);}return count; // 返回所有满足条件的子数组数量}
}

239. Sliding Window Maximum

Hard

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

Example 1:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation: 
Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       31 [3  -1  -3] 5  3  6  7       31  3 [-1  -3  5] 3  6  7       51  3  -1 [-3  5  3] 6  7       51  3  -1  -3 [5  3  6] 7       61  3  -1  -3  5 [3  6  7]      7
class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int len = nums.length;  // 数组的长度int[] res = new int[len - k + 1];  // 存储每个窗口的最大值int left = 0;  // 窗口的左边界int right = k - 1;  // 窗口的右边界int max = Integer.MIN_VALUE;  // 当前窗口中的最大值int maxIndex = -1;  // 当前最大值的索引// 遍历数组，直到右边界达到数组的末尾while (right < len) {// 如果最大值的索引仍在窗口内if (left <= maxIndex) {// 检查新加入窗口的元素是否大于当前最大值if (nums[right] >= nums[maxIndex]) {maxIndex = right;  // 更新最大值索引max = nums[right];  // 更新最大值}// 否则，重新计算当前窗口的最大值} else if (nums[right] >= max - 1 ) {maxIndex = right;max = nums[right];} else if (nums[left] >= max - 1 ) {maxIndex = left;max = nums[left];} else {max = nums[left];// 遍历当前窗口，找出最大值和对应的索引for (int j = left + 1; j <= right; j++) {if (nums[j] >= max) {maxIndex = j;max = nums[j];}}}// 将当前窗口的最大值存入结果数组res[left] = max;// 窗口向右移动left++;right++;}return res;  // 返回结果数组}
}

这篇关于Sliding Windows的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/962691。

相关文章

javafx 如何将项目打包为 Windows 的可执行文件exe

javafx 如何将项目打包为 Windows 的可执行文件exe

《javafx如何将项目打包为Windows的可执行文件exe》文章介绍了三种将JavaFX项目打包为.exe文件的方法：方法1使用jpackage（适用于JDK14及以上版本）,方法2使用La... 目录方法 1：使用 jpackage（适用于 JDK 14 及更高版本）方法 2：使用 Launch4j（
阅读更多...
windows端python版本管理工具pyenv-win安装使用

windows端python版本管理工具pyenv-win安装使用

《windows端python版本管理工具pyenv-win安装使用》：本文主要介绍如何通过git方式下载和配置pyenv-win,包括下载、克隆仓库、配置环境变量等步骤,同时还详细介绍了如何使用... 目录pyenv-win 下载配置环境变量使用 pyenv-win 管理 python 版本一、安装 和
阅读更多...
Python使用pysmb库访问Windows共享文件夹的详细教程

Python使用pysmb库访问Windows共享文件夹的详细教程

《Python使用pysmb库访问Windows共享文件夹的详细教程》本教程旨在帮助您使用pysmb库,通过SMB（ServerMessageBlock）协议,轻松连接到Windows共享文件夹,并列... 目录前置条件步骤一：导入必要的模块步骤二：配置连接参数步骤三：实例化SMB连接对象并尝试连接步骤四：
阅读更多...
在 Windows 上部署 gitblit

在 Windows 上部署 gitblit

在 Windows 上部署 gitblit 在 Windows 上部署 gitblit 缘起gitblit 是什么安装JDK部署 gitblit 下载 gitblit 并解压配置登录注册为 windows 服务 修改 installService.cmd 文件运行 installService.cmd运行 gitblitw.exe查看 services.msc 缘起
阅读更多...
Windows如何添加右键新建菜单

Windows如何添加右键新建菜单

Windows如何添加右键新建菜单 文章目录 Windows如何添加右键新建菜单实验环境缘起以新建`.md`文件为例第一步第二步第三步 总结 实验环境 Windows7 缘起 因为我习惯用 Markdown 格式写文本，每次新建一个.txt后都要手动修改为.md，真的麻烦。如何在右键新建菜单中添加.md选项呢？ 网上有很多方法，这些方法我都尝试了，要么太麻烦，要么不凑效
阅读更多...
Windows下Nginx的安装及开机启动

Windows下Nginx的安装及开机启动

1、将nginx-1.16.1.zip解压拷贝至D:\web\nginx目录下。 2、启动Nginx，两种方法： （1）直接双击nginx.exe，双击后一个黑色的弹窗一闪而过。 （2）打开cmd命令窗口，切换到nginx目录下，输入命令 nginx.exe 或者 start nginx ，回车即可。 3、检查nginx是否启动成功。 直接在浏览器地址栏输入网址 http://lo
阅读更多...
Windows环境利用VS2022编译 libvpx 源码教程

Windows环境利用VS2022编译 libvpx 源码教程

libvpx libvpx 是一个开源的视频编码库，由 WebM 项目开发和维护，专门用于 VP8 和 VP9 视频编码格式的编解码处理。它支持高质量的视频压缩，广泛应用于视频会议、在线教育、视频直播服务等多种场景中。libvpx 的特点包括跨平台兼容性、硬件加速支持以及灵活的接口设计，使其可以轻松集成到各种应用程序中。 libvpx 的安装和配置过程相对简单，用户可以从官方网站下载源代码
阅读更多...
C++实现俄罗斯方块（Windows控制台版）

C++实现俄罗斯方块（Windows控制台版）

C++实现俄罗斯方块（Windows控制台版） 在油管上看到一个使用C++控制台编写的俄罗斯方块小游戏，源代码200多行，B站上也有相关的讲解视频，非常不错，值得学习。 B站讲解视频地址为：【百万好评】国外技术大神C++游戏编程实战教程，油管580W收藏，新手10小时入门，并快速达到游戏开发能力（中英字幕） B站 CSDN博主千帐灯无此声还为此写了一篇博客：C++实现俄罗斯方块（源码+详解），讲
阅读更多...
Windows下php扩展开发c++动态库

Windows下php扩展开发c++动态库

PHP扩展开发，从零了解到初步完成一个小项目，经过三天的仔细研究，现整理如下 一、需求介绍 PHP扩展开发，调用自己之前的c++动态库，完成功能 二、项目之前 系统：windows xp  开发工具：vs 2008 web环境：apache2.4  PHP5.3.29-VC9-ts-x86 aphach和PHP 环境之前已经搭建完成 PHP源码：去官网http://www.php.n
阅读更多...
OpenStack镜像制作系列4—Windows Server2019镜像

OpenStack镜像制作系列4—Windows Server2019镜像

本系列文章主要对如何制作OpenStack镜像的过程进行描述记录  CSDN：OpenStack镜像制作教程指导（全） OpenStack镜像制作系列1—环境准备 OpenStack镜像制作系列2—Windows7镜像 OpenStack镜像制作系列3—Windows10镜像 OpenStack镜像制作系列4—Windows Server2019镜像 OpenStack镜像制作系
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2