【错题集-编程题】包含不超过两种字符的最长字串(滑动窗口)

简介: 【错题集-编程题】包含不超过两种字符的最长字串(滑动窗口)

牛客对应题目链接:包含不超过两种字符的最长子串_牛客题霸_牛客网 (nowcoder.com)


一、分析题目

简单的滑动窗口问题。


二、代码

#include <iostream>
#include <unordered_map>
using namespace std;
 
int main()
{
    string s;
    cin >> s;
    int n=s.size();
    int res=0;
    int cnt=0;
    unordered_map<char, int> hash;
    int left=0, right=0;
    while(right<n)
    {
        hash[s[right]]++;
        if(hash[s[right]]==1) //0->1 多了一种字符
            cnt++;
        while(cnt>2)
        {
            hash[s[left]]--;
            if(hash[s[left]]==0) //1->0 少了一种字符
                cnt--;
            left++;
        }
        res=max(res, right-left+1);
        right++;
    }
    cout << res << endl;
    return 0;
}

三、反思与改进

思路基本没错,还是 “滑动窗口” 系列问题的练习量不够,导致问题考虑的不周到。


相关文章
|
Web App开发 运维 前端开发
从0开始搭建一个前端项目的架子
从0开始搭建一个前端项目的架子
279 1
|
开发工具 数据安全/隐私保护 git
Lerna 使用教程 -- 开发脚手架的流程和核心命令详解
Lerna 使用教程 -- 开发脚手架的流程和核心命令详解
418 0
|
定位技术 开发工具 C++
C++绘图库matplotlibcpp在Visual Studio中的配置方法
C++绘图库matplotlibcpp在Visual Studio中的配置方法
551 1
|
JavaScript 关系型数据库 MySQL
❤Nodejs 第三章(操作本地数据库增改查)
【4月更文挑战第3天】该文档介绍了使用Node.js和Express操作本地数据库的增删改查操作。首先,概述了RESTful API的四个基本方法:GET、PUT、DELETE和POST。然后,展示了如何查询用户列表,通过axios发送GET请求,遇到跨域问题后,在app.js中设置允许跨域。接着,添加了POST方法来新增用户,并展示了MySQL的INSERT语句。
142 5
|
传感器 安全
嵌入式 STM32 SHT31温湿度传感器
嵌入式 STM32 SHT31温湿度传感器
|
自然语言处理 算法
KMP算法(A + B for you again—HDU - 1867 )
KMP算法(A + B for you again—HDU - 1867 )
An工具介绍之形状工具及渐变变形工具
An工具介绍之形状工具及渐变变形工具
3290 0
An工具介绍之形状工具及渐变变形工具
|
编解码 人工智能 自然语言处理
AI 生成视频版,英伟达做到最高1280×2048、最长4.7秒
AI 生成视频版,英伟达做到最高1280×2048、最长4.7秒
|
存储 机器学习/深度学习 PyTorch
使用PyTorch Lightning构建轻量化强化学习DQN(附完整源码)(一)
使用PyTorch Lightning构建轻量化强化学习DQN(附完整源码)(一)
405 0
使用PyTorch Lightning构建轻量化强化学习DQN(附完整源码)(一)
阿里云联合思普瑞上线平安社区服务平台 提供物联网一站式管理
2019年6月11日,阿里云联合蚂蚁金服、思普瑞集团携手研发的平安社区服务平台正式上线。
17636 57