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

leetcode:最小覆盖字符串

1笨方法

对于算法题目,自己能想到的往往是最基础的笨方法。

代码如下:

如果t的长度是len1,s的长度是len2,那么最小窗口是len1,最大窗口是len2。所以可以从len1到len2,遍历窗口大小,对于每个窗口大小,将窗口从前向后进行移动。因为窗口是从小到大进行遍历,所以第一次遇到满足条件的子串时,就可以直接范围。这种算法的时间复杂度是O(n*n),在leetcode上运行会超时。

class Solution {
public:string minWindow(string s, string t) {std::map<char, int> tConstMap;std::map<char, int> tTmpMap;for (char c : t) {if (tConstMap.count(c) > 0) {tConstMap[c]++;} else {tConstMap[c] = 1;}tTmpMap[c] = 0;}int minWindow = t.size();int maxWindow = s.size();int maxLength = s.size();for (int window = minWindow; window <= maxWindow; window++) {for (int i = 0; i <= maxLength - window; i++) {for (int j = i; j < i + window; j++) {if (tConstMap.count(s[j]) > 0) {tTmpMap[s[j]]++;}}bool result = true;for (auto [c, count] : tTmpMap) {if(count < tConstMap[c]) {result = false;}tTmpMap[c] = 0;}if (result == true) {std::cout << "i:" << i <<",window:" << window <<std::endl;return s.substr(i, window);}}}return "";}
};

 针对上边的代码,我们可以看到,针对一个确定大小的window,在从前向后遍历的过程中,每次只移动了一个字符的位置,但是每次都要对tTmpMap进行清空并重新计算,完全可以只对移出窗口的元素和移入窗口的元素进行处理。但是时间复杂度仍然较高,在leetcode上运行会超时。

class Solution {
public:string minWindow(string s, string t) {std::map<char, int> tConstMap;std::map<char, int> tTmpMap;for (char c : t) {if (tConstMap.count(c) > 0) {tConstMap[c]++;} else {tConstMap[c] = 1;}tTmpMap[c] = 0;}int minWindow = t.size();int maxWindow = s.size();int maxLength = s.size();for (int window = minWindow; window <= maxWindow; window++) {for (int i = 0; i <= maxLength - window; i++) {if (i == 0) {for (auto [c, value] : tTmpMap) {tTmpMap[c] = 0;}for (int j = i; j < i + window; j++) {if (tConstMap.count(s[j]) > 0) {tTmpMap[s[j]]++;}}} else {if (tConstMap.count(s[i +window - 1]) > 0) {tTmpMap[s[i +window - 1]]++;}}bool result = true;for (auto [c, count] : tTmpMap) {if(count < tConstMap[c]) {result = false;break;}}if (result == true) {return s.substr(i, window);}if (tTmpMap.count(s[i]) > 0) {tTmpMap[s[i]]--;}}}return "";}
};

2leetcode题解一

官方题解中没有遍历窗口的大小,而是使用双指针的方式。用窗口的左边沿和右边沿来表示一个窗口,通过左右边沿的移动来遍历不同的情况。

class Solution {
public://t中字符出现的次数unordered_map <char, int> ori; //s中字符出现的次数unordered_map <char, int> cnt;//判断当前子串是不是覆盖了tbool check() {for (const auto &p: ori) {if (cnt[p.first] < p.second) {return false;}}return true;}string minWindow(string s, string t) {//t中字符出现的次数for (const auto &c: t) {ori[c]++;}int l = 0;//窗口左边沿int r = 0;//窗口右边沿int len = INT_MAX;int ansL = -1;int ansR = -1;while (r < int(s.size())) {//统计s中字符的数量,移动窗口右边沿if (ori.find(s[r]) != ori.end()) {cnt[s[r]]++;}//移动窗口左边沿,找到慢去条件的最小窗口while (check() && l <= r) {if (r - l + 1 < len) {len = r - l + 1;ansL = l;}if (ori.find(s[l]) != ori.end()) {cnt[s[l]]--;}l++;}r++;}return ansL == -1 ? string() : s.substr(ansL, len);}
};

3leetcode题解二

题解二比题解一性能更高。

相同点:

①都维护了两个map,分别用于记录s和t中字符出现的次数。

②窗口右边沿的移动均是沿着s进行移动,没有其它的条件约束。


不同点:

①题解二中多了一个count,用count和t的长度是否相等来表示当前子串是不是覆盖了t。当s中的字符出现次数少于t中字符的出现次数时,对count进行递增。而题解一种使用函数check来判断当前子串是不是覆盖了t。

②窗口左边沿的移动方式不同:题解一种移动左边沿,加上check函数进行判断,比较好理解;题解二中移动左边界,是当当前字符出现的次数比t中出现的次数多的时候,才会像猴移动(如果字符在t中没有出现,在s中出现了,那么会移动;如果字符在s和t中都出现了,并且在s中出现的次数比t中多,那么也可以移动)。

class Solution {
public:string minWindow(string s, string t) {for (char c : t) {ht[c]++;}for (int i = 0, j = 0; i < s.size(); i++) {hs[s[i]]++;if (hs[s[i]] <= ht[s[i]]) {count++;}while (hs[s[j]] > ht[s[j]]) {hs[s[j]]--;j++;}if (count == t.size()) {if (ret.empty() || i - j + 1 < ret.size()) {ret = s.substr(j, i - j + 1);}}}return ret;}private:int hs[123] = {0};int ht[123] = {0};int count = 0;std::string ret = "";
};

http://www.xdnf.cn/news/278623.html

相关文章:

  • 【操作系统】吸烟者问题
  • NHANES指标推荐:LC9
  • Android第四次面试总结之Java基础篇(补充)
  • 【NTN 卫星通信】NTN关键问题的一些解决方法(一)
  • 55认知干货:深空产业
  • 2022年第十三届蓝桥杯省赛B组Java题解
  • 128. 最长连续序列
  • 【人工智能】大模型安全的深度剖析:DeepSeek漏洞分析与防护实践
  • 牛客周赛91 D题(数组4.0) 题解
  • 如何用更少的显存训练 PyTorch 模型
  • 【Java JUnit单元测试框架-60】深入理解JUnit:Java单元测试的艺术与实践
  • Spring AI 实战:第九章、Spring AI MCP之万站直通
  • HTML5实战指南:语义化标签与表单表格高级应用
  • AI日报 · 2025年5月04日|Hugging Face 启动 MCP 全球创新挑战赛
  • 《工业社会的诞生》章节
  • 相向双指针-16. 最接近的三数之和
  • 基于AWS Marketplace的快速解决方案:从选型到部署实战
  • OpenFAST 开源软件介绍
  • 大学之大:高丽大学2025.5.4
  • Java并发编程-多线程基础(三)
  • 在 Ubuntu 系统中,查看已安装程序的方法
  • Redis-----认识NoSQL
  • 网络开发基础(游戏)之 心跳机制
  • C++ 多态:原理、实现与应用
  • 科学养生,健康生活
  • Python容器与循环:数据处理的双剑合璧
  • 虚函数 vs 纯虚函数 vs 静态函数(C++)
  • 原型模式(Prototype Pattern)
  • drawDB:打造高效数据库设计流程
  • Go-Spring 全新版本 v1.1.0