当前位置: 首页 > article >正文

Leetcode 刷题记录 03 —— 滑动窗口

本系列为笔者的 Leetcode 刷题记录,顺序为 Hot 100 题官方顺序,根据标签命名,记录笔者总结的做题思路,附部分代码解释和疑问解答。

目录

01 无重复字符的最长子串

方法:滑动窗口

02 找到字符串中所有字母异位词

方法一:滑动窗口

方法二:滑动窗口Plus


01 无重复字符的最长子串

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        
    }
};
方法:滑动窗口
  • 建立左指针 lk 和右指针 rk

  • lk 指向滑动窗口第一个元素

  • rk 指向滑动窗口最后一个元素

  • 不断地去掉第一个元素,添加最后一个元素,判断 !occ.count(s[rk+1])

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> occ;
        int n = s.size();
        int rk = -1; //右指针
        int ans = 0;

        for(int lk=0; lk<n; ++lk){ //左指针
            if(lk != 0) occ.erase(s[lk-1]);
            while(rk+1 < n && !occ.count(s[rk+1])){
                occ.insert(s[rk+1]);
                ++rk;
            }
            ans = max(ans, rk-lk+1);
        }
        return ans;
    }
};

02 找到字符串中所有字母异位词

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        
    }
};
方法一:滑动窗口
  • 建立两个数组 sCount(26)pCount(26)

  • sCount(26) 记录 s 中的字母情况

  • pCount(26) 记录 p 中的字母情况

  • 不断地去掉第一个元素,添加最后一个元素,判断 sCount == pCount

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int sLen = s.size(), pLen = p.size();
        if(sLen < pLen) return vector<int>();

        vector<int> ans;
        vector<int> sCount(26);
        vector<int> pCount(26);
        for(int i=0; i<pLen; ++i){
            ++sCount[s[i] - 'a'];
            ++pCount[p[i] - 'a'];
        }
        if(sCount == pCount) ans.emplace_back(0);

        for(int i=0; i<(sLen - pLen); ++i){
            --sCount[s[i] - 'a'];
            ++sCount[s[i + pLen] - 'a'];

            if(sCount == pCount) ans.emplace_back(i + 1);
        }
        return ans;
    }
};
方法二:滑动窗口Plus
  • 建立一个数组 count(26)

  • count(26) 记录 sp 差异情况

  • 不断地去掉第一个元素,添加最后一个元素,判断 differ == 0

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int sLen = s.size(), pLen = p.size();
        if(sLen < pLen) return vector<int>();

        vector<int> ans;
        vector<int> count(26);
        int differ = 0;

        for(int i=0; i<pLen; ++i){
            ++count[s[i] - 'a'];
            --count[p[i] - 'a'];
        }
        for(int j=0; j<26; j++){
            if(count[j]) ++differ;
        }
        if(differ == 0) ans.emplace_back(0);

        for(int i=0; i<(sLen - pLen); ++i){
            if(count[s[i] - 'a'] == 0) ++differ;
            else if(count[s[i] - 'a'] == 1) --differ;
            --count[s[i] - 'a'];

            if(count[s[i + pLen] - 'a'] == 0) ++differ;
            else if(count[s[i + pLen] - 'a'] == -1) --differ;
            ++count[s[i + pLen] - 'a'];

            if(differ == 0) ans.emplace_back(i + 1);
        }
        return ans;
    }
};

文章部分代码来源于力扣(LeetCode)


http://www.kler.cn/a/576424.html

相关文章:

  • 进程存储相关的关键数据结构
  • 网络编程 day4
  • 使用开源OPUS-MT模型进行文本翻译(python)
  • 针对Ollama进行DeepSeek本地部署存在的安全风险,使用nginx进行反向代理配置是一种有效的解决方案
  • 开发环境搭建-07.后端环境搭建-前后端联调-Nginx反向代理和负载均衡配置
  • 微软发布Dragon Copilot,打造医疗行业首款AI语音助手
  • 深度学习代码解读——自用
  • Qt调试功能使用方法
  • bash: uwsgi: 未找到命令
  • 基于Python+openGauss实现(图形界面)多功能本地视频播放系统
  • 使用 Apache POI 实现 Excel 单元格合并
  • uniapp 安卓app图片回显,默认不支持http图片地址,上传图片和回显图片
  • 腾讯 TDF 即将开源 Kuikly 跨端框架,Kotlin 支持全平台
  • 人工智能与深度学习的应用案例:从技术原理到实践创新
  • 紫光无人机AI飞控平台2.0——航线管理模块
  • ⭐算法OJ⭐N-皇后问题【回溯剪枝】(C++实现)N-Queens
  • 不小心更改了/etc权限为777导致sudo,ssh等软件都无法使用
  • Vue基础之Element-ui
  • 2025-03-07 学习记录--C/C++-PTA 习题8-5 使用函数实现字符串部分复制
  • 【如何删除在 Linux 系统中的删除乱码文件】