分类 算法 下的文章

快速沃尔什变换(FWT)模板题 CSU 1911 Card Game


题目描述: 给你两个二进制数的集合,给出q次询问,输出两个集合之间元素或的值等于查询值的种数。
题目链接: Card Game

快速沃尔什变换详解请看快速沃尔什变换详解

代码

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define LL long long
const int maxn = 1 << 18;
LL a[maxn], b[maxn];
int n, m;
char s[20];

void FWT(LL a[], int n)
{
    for (int d = 1; d < n; d <<= 1) {
        for (int m = d << 1, i = 0; i < n; i += m) {
            for (int j = 0; j < d; j++) {
                int x = a[i + j];
                int y = a[i + j + d];
                a[i + j + d] = x + y;
            }
        }
    }
}

void UFWT(LL a[], int n)
{
    for (int d = 1; d < n; d <<= 1) {
        for (int m = d << 1, i = 0; i < n; i += m) {
            for (int j = 0; j < d; j++) {
                int x = a[i + j];
                int y = a[i + j + d];
                a[i + j + d] = y - x;
            }
        }
    }
}
void solve(LL a[], LL b[], int n)
{
    FWT(a, n);
    FWT(b, n);
    for (int i = 0; i < n; i++) {
        a[i] = a[i] * b[i];
    }
    UFWT(a, n);
}

int main()
{
    int t, q;
    scanf("%d", &t);
    for (int cas = 1; cas <= t; cas++) {
        memset(a, 0, sizeof a);
        memset(b, 0, sizeof b);
        scanf("%d%d", &n, &m);
        int l, x;
        for (int i = 0; i < n; i++) {
            x = 0;
            scanf("%s", s);
            l = strlen(s);
            for (int j = 0; j < l; j++)
                x = (x << 1) + s[j] - '0';
            a[x]++;
        }
        for (int i = 0; i < n; i++) {
            x = 0;
            scanf("%s", s);
            l = strlen(s);
            for (int j = 0; j < l; j++)
                x = (x << 1) + s[j] - '0';
            b[x]++;
        }
        solve(a, b, (1 << m));
        scanf("%d", &q);
        printf("Case #%d:\n", cas);
        while (q--) {
            scanf("%s", s);
            x = 0;
            l = strlen(s);
            for (int i = 0; i < l; i++)
                x = (x << 1) + s[i] - '0';
            printf("%lld\n", a[x]);
        }
    }
    return 0;
}

快速沃尔什变换(FWT)讲解 解决集合卷积的方法


能看到这篇博客的人,一定知道FWT是干什么的。(什么?你不知道?)
没事,这里有pick讲FWT的博客。先点进去看一看。
如果你看懂了,那么恭喜你。如果你跟我一样看不懂,那么请继续往下看。

这里的A和B都是什么呢?其实它们是一个多维的向量(如果你不知道向量是什么,就把它当成数组),下标从0开始。
其中,$ A = <a_{0},a_{1},...,a_{2^{k}-1}> $,$ B = <b_{0},b_{1},...,b_{2^{k}-1}> $,$ C = A\otimes B $
这里我们定义$$ A\pm B = < a_{0}\pm b_{0}, a_{1}\pm b_{1},..., (a_{2^{k}-1})\pm (b_{2^{k}-1}) > $$ 即对应位相加(减)$$ A * B = < a_{0} * b_{0}, a_{1} * b_{1},..., (a_{2^{k}-1}) * (b_{2^{k}-1}) > $$即对应位相乘$ A\otimes B $ 为A和B做卷积之后得到的结果,也是一个和原来大小一样的向量。

注意到FWT做的是二进制上的位运算,所以一定要把A和B补到2的整次幂次(即不足的地方填上0)。

我们要构造一个变换tf,使得$tf(A)*tf(B)=tf(C)$。这个变换的对象是一个大小为$2^{k}$的向量,变换出来的结果也是一个大小为$2^{k}$的向量。

就以异或举例。picks告诉我们$$tf(A)=(tf(A_{0})+tf(A_{1}),tf(A_{0})-tf(A_{1}))$$$$A_{0}=<a_{0},a_{1},...,a_{2^{k-1}-1}>$$$$A_{1}=<a_{2^{k-1}},a_{2^{k-1}+1},...,a_{2^{k}-1}>$$即把A中的下标按照二进制最高位为0或1分成前后两部分(前面的为$A_{0}$,后面的为$A_{1}$),分治下去做。

分治之后得到$tf(A_{0})$和$tf(A_{1})$。然后tf(A)的前半部分(即$[0,2^{k-1}-1]$)为$tf(A_{0})+tf(A_{1})$,后半部分(即$[2^{k-1},2^{k}-1]$)为$tf(A_{0})-tf(A_{1})$。(其实就是已知两个向量,把两个向量做加减运算,加的那个结果填到前一半中,减的那个结果填到后一半中)。

然而,这为什么是对的?
接下来我们来证明它是对的。

我要事先说明(注意不是证明)一个引理:$tf(A+B)=tf(A)+tf(B)$。这个东西看上去挺直观的(一点都不直观好吗。。)。这个东西可以用数学归纳法证。这里略过。。。(有时间的时候再补上)

我们看k=1的时候。根据定义,有$$tf(A)=<a_{0}+a_{1},a_{0}-a_{1}>$$$$tf(B)=<b_{0}+b_{1},b_{0}-b_{1}>$$$$tf(C)=<c_{0}+c_{1},c_{0}-c_{1}>$$$$c_{0}=a_{0}*b_{0}+a_{1}*b_{1},c_{1}=a_{0}*b_{1}+a_{1}*b_{0}$$自己代代看,反正代出来很神奇的的发现$tf(A)*tf(B)=tf(C)$

接下来使用数学归纳法。假设对于大小都为$2^{k}(k\epsilon N)$的向量A和B,满足$C = A\otimes B$,并且$tf(A)*tf(B)=tf(C)$。
考虑当大小为$2^{k+1}$的情况。我们要证明在这种情况下,$tf(A)*tf(B)=tf(C)$。根据定义,有
$$tf(A)=(tf(A_{0})+tf(A_{1}),tf(A_{0})-tf(A_{1}))$$$$tf(B)=(tf(B_{0})+tf(B_{1}),tf(B_{0})-tf(B_{1}))$$$$tf(A)*tf(B)=([tf(A_{0})+tf(A_{1})]*[tf(B_{0})+tf(B_{1})],[tf(A_{0})-tf(A_{1})]*[tf(B_{0})-tf(B_{1})])$$
暴力把式子拆开,有
$tf(A)*tf(B)=$
$$(tf(A_{0})*tf(B_{0})+tf(A_{0})*tf(B_{1})+tf(A_{1})*tf(B_{0})+tf(A_{1})*tf(B_{1}),$$$$tf(A_{0})*tf(B_{0})+tf(A_{1})*tf(B_{1})-tf(A_{0})*tf(B_{1})-tf(A_{1})*tf(B_{0}))$$
注意到这里的$A_{0}$,$A_{1}$,$B_{0}$,$B_{1}$都是大小为$2^{k}$的向量,符合归纳的基础。于是,
$tf(A)*tf(B)=$
$$(tf(A_{0}\otimes B_{0})+tf(A_{0}\otimes B_{1})+tf(A_{1}\otimes B_{0})+tf(A_{1}\otimes B_{1}),$$$$tf(A_{0}\otimes B_{0})+tf(A_{1}\otimes B_{1})-tf(A_{0}\otimes B_{1})-tf(A_{1}\otimes B_{0}))$$
由于异或每一位是独立,而这里如果我们把C按照最高位为0或1分成两部分,最高位的异或和其它位不相关。
于是有$$C=(C_{0},C_{1})=(A_{0}\otimes B_{0}+A_{1}\otimes B_{1},A_{0}\otimes B_{1}+A_{1}\otimes B_{0})$$
要证的等式
$$右边=tf(C)=tf(C_{0},C_{1})$$$$=tf(A_{0}\otimes B_{0}+A_{1}\otimes B_{1},A_{0}\otimes B_{1}+A_{1}\otimes B_{0})$$$$=(tf(A_{0}\otimes B_{0}+A_{1}\otimes B_{1})+tf(A_{0}\otimes B_{1}+A_{1}\otimes B_{0}),tf(A_{0}\otimes B_{0}+A_{1}\otimes B_{1})-tf(A_{0}\otimes B_{1}+A_{1}\otimes B_{0}))$$$$=(tf(A_{0}\otimes B_{0})+tf(A_{1}\otimes B_{1})+tf(A_{0}\otimes B_{1})+tf(A_{1}\otimes B_{0}),tf(A_{0}\otimes B_{0})+tf(A_{1}\otimes B_{1})-tf(A_{0}\otimes B_{1})-tf(A_{1}\otimes B_{0}))$$$$=tf(A)*tf(B)=左边$$
至此,证毕。

然而这只是一个tf,还有一个逆变换utf。这个逆变换的正确性可以用同样的方法证明,即先看k=1的情况,然后一步一步用数归推上去。
证明方法比较简单(真的很简单),这里略过。

至于其它位运算,其证明方法与异或一致,这里不赘述。

说了这么多,其实这个证明并没有什么卵用(只是使得自己相信它是对的)。。大家还是背代码吧。。。

看完的找个模板题练练手感受一下吧,CSU 1911 Card Game

模板

// 题目要求取模时使用mod,否则去除mod
void FWT(int a[], int n)
{
    for (int d = 1; d < n; d <<= 1) {
        for (int m = d << 1, i = 0; i < n; i += m) {
            for (int j = 0; j < d; j++) {
                int x = a[i + j];
                int y = a[i + j + d];
                a[i + j] = (x + y) % mod;
                a[i + j + d] = (x - y + mod) % mod;
                // xor: a[i+j]=x+y, a[i+j+d]=x-y;
                // and: a[i+j]=x+y;
                // or: a[i+j+d]=x+y;
            }
        }
    }
}
void UFWT(int a[], int n)
{
    for (int d = 1; d < n; d <<= 1) {
        for (int m = d << 1, i = 0; i < n; i += m) {
            for (int j = 0; j < d; j++) {
                int x = a[i + j];
                int y = a[i + j + d];
                a[i + j] = 1LL * (x + y) * rev % mod;
                a[i + j + d] = (1LL * (x - y) * rev % mod + mod) % mod;
                // xor: a[i+j]=(x+y)/2, a[i+j+d]=(x-y)/2;
                // and: a[i+j]=x-y;
                // or: a[i+j+d]=y-x;
            }
        }
    }
}
void solve(int a[], int b[], int n)
{
    FWT(a, n);
    FWT(b, n);
    for (int i = 0; i < n; i++) {
        a[i] = 1LL * a[i] * b[i] % mod;
    }
    UFWT(a, n);
}

互联网面试常见问题整理


高并发系统之限流特技
动态链接库中函数的地址确定---PLT和GOT
Linux 中的各种栈:进程栈 线程栈 内核栈 中断栈
Redis和Memcached的区别
epoll内核源码详解+自己总结的流程
后台开发面试问题整理
Linux内核:poll机制
linux任务调度机制
Linux内核:poll机制
解读Raft(一 算法基础) - 杭州.Mark - 博客园
Linux文件系统详解 - AlanTu - 博客园
Linux c 开发 - 内存管理器ptmalloc - CSDN博客
Linux环境变量及其设置 - CSDN博客
比较全面的gdb调试命令 - 知识天地 - 博客园
把握linux内核设计思想(六):内核时钟中断 - CSDN博客
Linux进程调度原理 - alex.shu - 博客园
Linux系统调用的实现机制分析 - CSDN博客
理解inode - 阮一峰的网络日志
多阶hash表 - juary_的专栏 - CSDN博客
理解 glibc malloc - CSDN博客
Redis与Memcached的比较-zpf1218-ChinaUnix博客
glibc中malloc的详细解释 - CSDN博客
Redis的那些最常见面试问题 - 回首笑人间 - 博客园
浅析基于glibc的malloc - CSDN博客
slab机制 - wangLinuxer - 博客园
有感于STL的内存管理
DNS使用的是TCP协议还是UDP协议 - qq100440110的专栏 - CSDN博客
Linux的任务调度机制 - Nicholas的专栏 - CSDN博客
进程—内存描述符(mm_struct) - CSDN博客
彻底弄懂HTTP缓存机制及原理 - 木上有水 - 博客园
利用CAS操作(Compare & Set)实现无锁队列 - CSDN博客
进程间通信的方式——信号、管道、消息队列、共享内存 - 0giant - 博客园
TCP的数据流——滑动窗口,拥塞窗口,慢启动,Nagle算法,经受时延的确认等 - 千里之外 - CSDN博客
TCP协议总结--停止等待协议,连续ARQ协议,滑动窗口协议 - 杨博东的博客 - 博客园
C/C++ 笔试、面试题目大汇总 - fangyukuan - 博客园
C/C++ 内存对齐原则及作用 - chy19911123的专栏 - CSDN博客
mysql数据库面试总结 - bullets - 博客园
[学习笔记]数据库设计三大范式与BCNF,学习笔记 - ybwang1989 - 博客园
常见面试题整理--数据库篇(每位开发者必备) - weinierzui的专栏 - CSDN博客
知识库 - 你身边的技术百科全书 - CSDN
进程上下文与线程上下文 - bingshanyijiao_fkx的专栏 - CSDN博客
linux线程切换和进程切换的方法_Linux_脚本之家
深入理解计算机系统之虚拟存储器 - Al_xin的专栏 - CSDN博客
tcp的半连接与完全连接队列 - go4it - 简书
数位dp总结 之 从入门到模板 - 努力 - CSDN博客
类中函数的重载、隐藏和覆盖 - beaglebone - 博客园
排序算法____基数排序 - Dingwj_blog - 博客园
面试题干货在此_讨论区_牛客网
排序算法系列:基数排序 - 大鱼 - CSDN博客
位图索引:原理(BitMap index) - zhanlijun - 博客园
fopen与open的区别 - 清清飞扬 - 博客园
《深入理解计算机系统》-虚拟存储器 - gatsby_dhn - 简书
Linux内核解析:进程间通信:管道 - 笨拙的菜鸟 - 博客园
参考别人的面试总结:linux C/C++服务器后台开发面试题总结 - 大孟的博客 - CSDN博客
linux C/C++服务器后台开发面试题总结 - Nancy26 - 博客园
ELF 文件中的section 和 segment - wo_der的博客 - CSDN博客
聊聊Linux动态链接中的PLT和GOT(1)——何谓PLT与GOT - 海枫的专栏 - CSDN博客
ELF文件的加载和动态链接过程 - - ITeye博客
ELF文件的加载过程(load_elf_binary函数详解)--Linux进程的管理与调度(十三) - AderStep - CSDN博客
linux awk命令详解 - ggjucheng - 博客园
IP分片和TCP分片的区别 - cumirror的专栏 - CSDN博客
fork()----父子进程共享 - 程序狗的成长之路 - CSDN博客
Makefile中的wildcard用法 - liangkaiming的专栏 - CSDN博客
深入理解C++的动态绑定和静态绑定 - 常高伟的专栏 - CSDN博客
C++模板元编程(C++ template metaprogramming) - 文章 - 伯乐在线
C++后台开发校招面试常见问题 - oscarwin - CSDN博客
互斥锁的实现(转) - hzhzh007的专栏 - CSDN博客
TCP-IP详解:糊涂窗口综合症(Silly Window syndrome) - 深邃 精致 内涵 坚持 - CSDN博客
浅析Linux下的task_struct结构体 - qq_29503203的博客 - CSDN博客
C++虚继承的概念 - crystal_avast的专栏 - CSDN博客
c++ 虚继承与继承的差异 - Kikim的地盘 - CSDN博客
Linux的inode的理解 - iTech - 博客园
IPC通信:Posix消息队列 - liuhongxiangm的专栏 - CSDN博客
Linux线程的信号量同步 - JollyWing - 博客园
Linux进程间通信——使用共享内存 - ljianhui的专栏 - CSDN博客
gdb调试coredump(使用篇) - 叶落无痕,枫过有情…… - CSDN博客
信号中断 与 慢系统调用 - 许振坪的专栏 - CSDN博客
浅析CPU中断技术 - Funeral - 博客园
Linux信号(signal) 机制分析 - h13 - 博客园
EPOLLIN , EPOLLOUT , EPOLLPRI, EPOLLERR 和 EPOLLHUP事件 - yingying.liu的专栏 - CSDN博客
三种工厂模式的分析以及C++实现 - 曾经的你| - 博客园
STL源码剖析---红黑树原理详解上 - Hackbuteer1的专栏 - CSDN博客
valgrind 的使用简介 - sduliulun的专栏 - CSDN博客
_unix linux_脚本之家
GDT(Global Descriptor Table)全局描述符表 - starlitnext - 博客园
Linux程序加载过程 - 赢在拼搏中 - CSDN博客
linux 用户空间与内核空间——高端内存详解 - 立超的专栏 - 博客园
Linux虚拟地址空间布局以及进程栈和线程栈总结 - wilcohuang's blog - CSDN博客
堆排算法的分析与总结 - HOU_JUN - 博客园
HTTP必知必会——常见面试题总结 - Leeon的博客 - CSDN博客
pthread_once单例模式 - tom555cat - CSDN博客
pthread_once()使用(某个时间在整个程序中仅执行一次,不确定是那个线程) - 轻飘飞扬 - CSDN博客
23种设计模式对比与总结 - 码农恋码 - 博客园
ORM框架使用优缺点 - public - CSDN博客
高性能服务开发之定时器 - 行健 - 博客园
Https协议详解 - CoderZhuang - 博客园
图解SSL/TLS协议 - 阮一峰的网络日志
HTTPS 原理解析 - Zery - 博客园
Linux的用户和用户组管理 - 风生水起 - 博客园
TCP系列13—重传—3、协议中RTO计算和RTO定时器维护 - lshs - 博客园
可执行文件(ELF)格式的理解 - 深海的小鱼儿 - 博客园
GCC/G++编译参数含义 - yasi_xi的专栏 - CSDN博客
Linux内核中cache的实现 - leopard_ray的专栏 - CSDN博客
epoll源码实现分析[整理] - Apprentice89 - 博客园
linux内核内存管理学习之三(slab分配器) - 浩海拾贝 - CSDN博客
深度理解select、poll和epoll - 傻眼哥的博客 - CSDN博客
【经典算法】——KMP,深入讲解next数组的求解 - c_cloud - 博客园
Linux中断(interrupt)子系统之一:中断系统基本原理 - DroidPhone的专栏 - CSDN博客
HTTP Session、Cookie机制详解 - 奔跑的001 - 博客园
HttpSession详解 - 别再顺其自然 - 博客园
HTTP的长连接和短连接 - 烛秋 - 博客园
自动化构建 - 百度
linux内核之进程的基本概念(进程,进程组,会话关系) - 笨拙的菜鸟 - 博客园
Linux--进程组、会话、守护进程 - Alex_Monkey - 博客园
银行家算法学习笔记 - 唯心不易 - 博客园
linux session 浅谈 - younghongjian的专栏 - CSDN博客
Linux-进程、进程组、作业、会话、控制终端详解 - John_ABC - 博客园
关系型数据库到文档型数据库的跨越 - 海天一色是黑色的博客 - CSDN博客
linux系统编程之进程(八):守护进程详解及创建,daemon()使用 - mickole - 博客园
数据库设计三大范式 - Ruthless - 博客园
常见面试题整理--数据库篇 - 铭记遗忘 - 博客园
谈谈数据库的ACID - 敦格 - CSDN博客
关于TCP乱序和重传的问题 - cws1214的专栏 - CSDN博客
DNS 原理入门 - 阮一峰的网络日志
数据结构专题——线段树 - MetalSeed - CSDN博客
一步一步理解线段树 - tenos - 博客园
mysql 数据表读锁机制详解 - joy696163 - 博客园
单例模式全面学习(C++版) - weixliu - 博客园
单例模式及C++实现代码 - 曾经的你| - 博客园
每天进步一点点——五分钟理解一致性哈希算法(consistent hashing) - Cynric 的博客 - CSDN博客
TCP 协议中MSS的理解-frankzfz-ChinaUnix博客
TCP/IP详解学习笔记(15)-- TCP的流量控制和拥塞控制 - newwy - 博客园
TCP/IP详解--拥塞控制 & 慢启动 快恢复 拥塞避免 - losbyday - 博客园
关于C++中公有继承、私有继承、保护继承的讨论 - This is bill的专属博客 - CSDN博客
解决Hash碰撞冲突方法总结 - zeb_perfect的专栏 - CSDN博客
Linux进程通信之POSIX共享内存 - anonymalias的专栏 - CSDN博客
IPC对象持续性 - xiaohuima_dong的专栏 - CSDN博客
Linux环境进程间通信(三):消息队列-hnsyspc-ITPUB博客
Linux进程同步之POSIX信号量 - anonymalias的专栏 - CSDN博客
进程/线程同步的方式和机制,进程间通信 - Icnblog_Wan - 博客园
Linux进程同步之记录锁(fcntl) - jlins - 博客园
Linux 伙伴算法简介 - 浩天之家 - 博客园
孤儿进程与僵尸进程[总结] - Anker's Blog - 博客园
Linux虚拟地址空间布局以及进程栈和线程栈总结 - Xzzzh - 博客园
linux 内核poll/select/epoll实现剖析 - 在思考的路上 - ITeye博客
Linux虚拟地址空间布局 - clover_toeic - 博客园
HTTP详解(1)-工作原理 - guisu,程序人生。 逆水行舟,不进则退。 - CSDN博客
epoll简介及触发模式(accept、read、send) - 留下的只是回忆 - 博客园
linux内核分析笔记----中断和中断处理程序 - ☆&寒 烟☆ - 博客园
标准IO与文件IO 的区别 - bigbit的博客 - CSDN博客
硬中断和软中断 - zhangskd的专栏 - CSDN博客
<A HREF="http://m.blog.csdn.net/wenhui
/article/details/6889013">可重入和不可重入 - wenhui_的专栏 - CSDN博客
浅谈数位DP - zbtrs - 博客园
C++ Queues(队列)、Priority Queues(优先队列) - 面对现实,超越自己 - C++博客
缓存淘汰算法--LRU算法 - 小程故事多 - ITeye博客
Linux内核中内存cache的实现-yfydz-ChinaUnix博客
socket编程中write、read和send、recv之间的区别 - petershina的专栏 - CSDN博客
彻底学会使用epoll(六)——关于ET的若干问题总结 - feeman的专栏 - CSDN博客
linux系统编程之进程(八):守护进程详解及创建,daemon()使用 - mickole - 博客园
Linux IO模式及 select、poll、epoll详解 - 人云思云 - SegmentFault
select、poll、epoll之间的区别总结[整理] - Anker's Blog - 博客园
树状数组彻底入门 - 半根毛线 - 博客园
C++的new、delete及其内存管理 - Kelvin_Yan的专栏 - CSDN博客
malloc 函数详解 - Commence - 博客园
浅谈数据库查询优化的几种思路 - 六尺帐篷 - 简书
硬中断与软中断的区别_Linux编程_Linux公社-Linux系统门户网站
信号的基本概念、信号的产生以及阻塞信号 - 滴巴戈 - 博客园
Linux信号(signal) 机制分析 - h13 - 博客园
linux中断--LINUX中断机制与信号 - 鱼思故渊的专栏 - CSDN博客
进程线程及堆栈关系的总结 - echoisland的专栏 - CSDN博客
栈帧之深入理解c函数调用过程 - jelly_9的博客 - CSDN博客
【经典数据结构】B树与B+树 - vincently - 博客园
linux 物理内存和虚拟内存 - 百度
C/C++函数调用过程分析 - as_ - 博客园
胜者树与败者树 - whz_zb的专栏 - CSDN博客
Epoll详解及源码分析 - 我有我的天空 - CSDN博客
环回地址 - 百度
拓扑排序的原理及其实现 - dm_vincent的专栏 - CSDN博客
Manacher算法--O(n)回文子串算法 - xuanflyer - CSDN博客
【转】二叉树、B树、B-树、B+树、B树 - zhzhang - 博客园
设计模式 之 单例模式 (C++ 懒汉经典实现 & DCL实现 & 饿汉经典实现) - 柠檬不加糖的博客 - CSDN博客
C++中的单例模式 - Hackbuteer1的专栏 - CSDN博客
【C/C++】对于可重入、线程安全、异步信号安全几个概念的理解 - ZhangPY的专栏 - CSDN博客
B树、B-树、B+树、B
树详解(转) - 憨熊之家 - 博客园
红黑树(一)之 原理和算法详细介绍 - 如果天空不死 - 博客园
分布式锁的三种实现方式 - - ITeye技术网站
平衡二叉树详解 - zhangbaochong - 博客园
n个数中任意两个异或最大值


一文带你入门滑动窗口


最早接触滑动窗口是滑动窗口协议,滑动窗口协议(Sliding Window Protocol),属于 TCP 协议的一种应用,用于网络数据传输时的流量控制,以避免拥塞的发生。 发送方和接收方分别有一个窗口大小 w1 和 w2。窗口大小可能会根据网络流量的变化而有所不同,但是在更简单的实现中它们是固定的。窗口大小必须大于零才能进行任何操作。

我们算法中的滑动窗口也是类似,只不过包括的情况更加广泛。实际上上面的滑动窗口在某一个时刻就是固定窗口大小的滑动窗口,随着网络流量等因素改变窗口大小也会随着改变。接下来我们讲下算法中的滑动窗口。

滑动窗口是一种解决问题的思路和方法,通常用来解决一些连续问题。 比如 LeetCode 的 209. 长度最小的子数组。更多滑动窗口题目见下方题目列表

常见套路

滑动窗口主要用来处理连续问题。比如题目求解“连续子串 xxxx”,“连续子数组 xxxx”,就应该可以想到滑动窗口。能不能解决另说,但是这种敏感性还是要有的。

从类型上说主要有:

  • 固定窗口大小
  • 窗口大小不固定,求解最大的满足条件的窗口
  • 窗口大小不固定,求解最小的满足条件的窗口(上面的 209 题就属于这种)

后面两种我们统称为可变窗口。当然不管是哪种类型基本的思路都是一样的,不一样的仅仅是代码细节。

固定窗口大小

对于固定窗口,我们只需要固定初始化左右指针 l 和 r,分别表示的窗口的左右顶点,并且保证:

  1. l 初始化为 0
  2. 初始化 r,使得 r - l + 1 等于窗口大小
  3. 同时移动 l 和 r
  4. 判断窗口内的连续元素是否满足题目限定的条件
    • 4.1 如果满足,再判断是否需要更新最优解,如果需要则更新最优解
    • 4.2 如果不满足,则继续。

固定窗口

可变窗口大小

对于可变窗口,我们同样固定初始化左右指针 l 和 r,分别表示的窗口的左右顶点。后面有所不同,我们需要保证:

  1. l 和 r 都初始化为 0
  2. r 指针移动一步
  3. 判断窗口内的连续元素是否满足题目限定的条件
    • 4.1 如果满足,再判断是否需要更新最优解,如果需要则更新最优解。并尝试通过移动 l 指针缩小窗口大小。循环执行 4.1
    • 4.2 如果不满足,则继续。

形象地来看的话,就是 r 指针不停向右移动,l 指针仅仅在窗口满足条件之后才会移动,起到窗口收缩的效果。

可变窗口

模板代码

以下是 209 题目的代码,使用 Python 编写,大家意会即可。

class Solution:    
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        l = total = 0
        ans = len(nums) + 1
        for r in range(len(nums)):
            total += nums[r]
            while total >= s:
                ans = min(ans, r - l + 1)
                total -= nums[l]
                l += 1
        return  0 if ans == len(nums) + 1 else ans

题目列表

以下题目有的信息比较直接,有的题目信息比较隐蔽,需要自己发掘

扩展阅读