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

【算法】滑动窗口——串联所有单词的子串

今天来以“滑动窗口”的思想来详解一道比较困难的题目——串联所有单词的子串,有需要借鉴即可。

目录

  • 1.题目
  • 2.下面是示例代码
  • 3.总结

1.题目

题目链接:LINK
在这里插入图片描述
这道题如果把每个字符串看成一个字母,就是另外一道中等难度的题目,即,找到字符串中所有字母异位词:LINK

所以说白了,就是把每个字符串来当作一个字母进行处理,当然这仅仅是思想,相比于异位词这个题来说,现在这道比较困难的题目还有以下不同的区别需要注意:

  • ①哈希表不同
  • ②left,right的起始位置,赋值不同
  • ③滑动窗口的执行次数

2.下面是示例代码

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {vector<int> ret;unordered_map<string,int> hash_w;for(int i = 0; i < words.size(); i++){string str = words[i];hash_w[str]++;}for(int i = 0; i < words[0].size(); i++){unordered_map<string,int> hash_s;for(int left = i, right = i,count = 0; right + words[0].size() <= s.size(); right+=words[0].size()){//进窗口string in = s.substr(right,words[0].size());//取子串hash_s[in]++;if(hash_w.count(in) && hash_s[in] <= hash_w[in])count++;//判断if(right - left + 1 > words[0].size() * words.size()){//出窗口string out = s.substr(left,words[0].size());if(hash_w.count(out) && hash_s[out] <= hash_w[out])count--;//这个地方需要注意要在--之前进行判断hash_s[out]--;left+=words[0].size();}//更新结果if(count == words.size())ret.push_back(left);}}return ret;}
};

3.总结

  • 一、经验
    这道题如果有“找到字符串中所有字母异位词”这道题的经验,说实在的不难,但前提是得有这个思想,没做过“找到字符串中所有字母异位词”这道题直接做这个的比较困难的题目的话会很难受。

  • 二、再就是语法上:

    • ①是对容器的基本语法要有点了解,知道会用一些基本的接口。
    • ②是我上面这个代码其实还做了一点点语法优化
      就是在判断count是否++或者–时候那个条件,即:if(hash_w.count(in) && hash_s[in] <= hash_w[in])count++;如果hash_w[in]不存在他会创建一个in,有点消耗时间

EOF

http://www.lryc.cn/news/347630.html

相关文章:

  • 等保测评安全物理环境测评讲解
  • TensorRT-llm入门
  • TinyXML-2介绍
  • JAVA课程设计
  • 基于SpringBoot+Vue的旅游网站系统
  • http代理ip按流量划算还是个数划算?
  • Banana Pi BPI-F3, 进迭时空K1芯片设计,定位工业级应用,网络通信及工业自动化
  • 安科瑞工业IT产品及解决方案—电源不接地,设备外壳接地【监测系统对地绝缘电阻】
  • 栈:概念与实现
  • 【Linux】查找服务器中某个文件的完整路径
  • windows server 2019 安装 docker环境
  • 【Linux】探索 Linux du 命令:管理磁盘空间的利器
  • Service 和 Ingress
  • C++(类和对象—封装)
  • 如何训练一个大模型:LoRA篇
  • Spring Cloud学习笔记(Nacos):基础和项目启动
  • 音频提取特征
  • AJAX前端与后端交互技术知识点以及案例
  • [AutoSar]BSW_Diagnostic_003 ReadDataByIdentifier(0x22)介绍
  • 买卖股票的最佳时机 II(LeetCode 122)
  • Spring Boot:让微服务开发像搭积木一样简单!
  • WordPress 、Typecho 站点的 MySQL/MariaDB 数据库优化
  • ==与===的区别
  • 什么是ACID及基本实现的示例
  • 【启明智显技术分享】SSD202核心板Rootfs下如何烧录mac地址
  • springboot3 集成spring-authorization-server (一 基础篇)
  • AVL树!
  • 知识付费系统怎么安装教程,教师课堂教学该掌握哪些表达技巧?
  • 基于MetaGPT的LLM Agent学习实战(一)
  • 【IMX6ULL项目】IMX6ULL上Linux系统实现产测工具框架