首页 > 编程语言 >算法题笔记-滑动窗口

算法题笔记-滑动窗口

时间:2024-09-09 09:35:21浏览次数:7  
标签:right int while 笔记 算法 set 滑动 模板

refer doc
leetcode对应题目:

解题模板:

//外层循环扩展右边界,内层循环扩展左边界
for (int l = 0, r = 0 ; r < n ; r++) {
	//当前考虑的元素
	while (l <= r && check()) {
        //扩展左边界
		//触发条件,改变滑动窗口左侧边界
    }
    //区间[left,right]符合题意,统计相关信息
	// 统计单个窗口信息,并进行相关操作
}

模板理解与扩展

  • 左右指针 l r
  • for遍历循环内嵌套while循环
  • 满足while判断条件则变更左边界
  • 每次循环统计滑动窗口

无重复最长子串模板扩展示例

    public int lengthOfLongestSubstring(String s) {
        //滑动窗口
        char[] ss = s.toCharArray();
        Set<Character> set = new HashSet<>();//去重
        int res = 0;//结果
        for(int left = 0, right = 0; right < s.length(); right++) {//每一轮右端点都扩一个。
            char ch = ss[right];//right指向的元素,也是当前要考虑的元素
            while(set.contains(ch)) {//set中有ch,则缩短左边界,同时从set集合出元素.去掉模板的l<=r,不符合题意
                set.remove(ss[left]);
                left++;
            }
            set.add(ss[right]);//别忘。将当前元素加入。
            res = Math.max(res, right - left + 1);//计算当前不重复子串的长度。
        }
        return res;
    }

标签:right,int,while,笔记,算法,set,滑动,模板
From: https://www.cnblogs.com/alidata/p/18403951

相关文章

  • 编译原理(第3版)上课笔记
    1、编译器是一个程序、具有非常模块化的高层结构离线方式offline2、解释器是一类处理程序的程序在线方式online3、静态计算所生成的目标程序要和源代码语义相同(不能有任何改变)4、动态计算5、编译的各个阶段(1)词法分析器:检查单词是否合法。(2)语法分析器:生成语法树,检......
  • 【C++学习笔记】数组与指针(三)
    目录一、数组1.1数组声明与赋值1.2数组的特点特点1:任意类型均可创建数组特点2:固定大小特点3:内存连续且有序特点4:C++无数组下标越界错误特点5:数组变量不记录数据1.3遍历数组普通for循环foreach增强循环1.4字符数组1.5多维数组二维数组三维数组遍历二维数......
  • 【C++学习笔记】逻辑判断语句与循环语句(二)
    目录一、逻辑判断语句1.1ifelse语句1.2 switch语句1.3枚举类型二、循环语句2.1while循环2.2dowhile循环2.3for循环2.4break与continue关键字2.5goto语句一、逻辑判断语句1.1ifelse语句#include"iostream"usingnamespacestd;intmain(){......
  • 【408DS算法题】038进阶-图深度优先遍历DFS
    Index题目分析实现总结题目设计函数实现对图的深度优先遍历。分析实现类似于图的BFS的分析思路,图的DFS和二叉树的DFS思路相同,但需要额外考虑结点是否已经被访问过。此处同样用布尔数组visited来记录每个结点的访问情况,对于邻接矩阵存储方式的图的DFS,依照先序遍......
  • 【算法笔记】多源最短路问题——Floyd算法
    0.前言在图中,如果要求任意两点间的距离,则可以使用Floyd(\(\mathcalO(N^3)\)......
  • 【算法笔记】单源最短路问题——Dijkstra算法(无优化/优先队列/set优化)
    0.前言Dijkstra算法可在\(\mathcalO(m\logm)\)或\(\mathcalO(m\logn)\)的时间内求解无负权单源最短路问题。本文中,我们将详细介绍算法的原理、实现,以及常用的两种优化。另外,Dijkstra算法也不要乱用,比如说多源的最短路,用Dijkstra求解的复杂度只有\(\mathcalO(nm\logm)\),但......
  • 【算法笔记】三种背包问题——背包 DP
    前言背包(Knapsack)问题是经典的动态规划问题,也很有实际价值。01背包洛谷P2871[USACO07DEC]CharmBraceletSAtCoderEducationalDPContestD-Knapsack1有\(n\)个物品和一个总容量为\(W\)的背包。第\(i\)件物品的重量是\(w_i\),价值是\(v_i\)。求解将哪些物品装入背包......
  • 【算法笔记】Kruskal/Prim算法——求解最小生成树问题
    前言生活中经常遇到类似这种的问题:公路修建有一些城市,城市之间要修建高速公路,每两个城市之间都可以修双向的路。其中每两个城市之间修路都需要花费对应的金额。请问如何修路,使得总花费的金额最少,且任意两个城市之间都可以直接或间接通过修建的路来通行?实际上,我们可以把这种......
  • 【算法笔记】树状数组/Binary Indexed Tree/Fenwick Tree
    前言树状数组,即树形存储的数组,又称BinaryIndexedTree或FenwickTree。抛开它树形的存储结构,这种神奇的数据结构的应用看起来与「树」没什么关系:有一个序列\(A=(A_1,A_2,\dots,A_N)\),在不超过\(\mathcalO(\logN)\)的时间复杂度内完成下列操作:\(\to~\)求\([L,R]\)区间内所......
  • Cooley-Tukey FFT算法的非递归实现
    一维情况#include<iostream>#include<complex>#include<cmath>constdoublePI=3.14159265358979323846;//交换位置voidswap(std::complex<double>&a,std::complex<double>&b){std::complex<double>temp=a......