力扣的题76. 最小覆盖子串,C\C++交流,技术交流,鱼C论坛

202021130162 发表于 2021-8-10 20:23:25

力扣的题76. 最小覆盖子串

新写的一个想法,在评论区找不到参考,可以通过题目给的测试,但提交时的测试用例:"a""a";返回结果是"",不知道哪里错了
题目链接:https://leetcode-cn.com/problems/minimum-window-substring/
class Solution {
public:
string minWindow(string s, string t) {
   int k=0;
   int p=0,q=0;
   int Minresult=s.size();
   int Min=0;
   string result,r;
   for(int i=0;i<s.size()-t.size();i++)
   {
         for(int j=i;j<s.size()&&k<t.size();j++)
         {
            if(t==s)
            {
               k++;
               Min=max(Min,j);          //表示以i开头,这一段至少需要的子串
               j=i-1;
               continue;
            }                            //得到从i到Min的一串子串为需要的子串(但不一定是最小子串)
         }
         if(Minresult>Min-i&&(Min-i+1)>=t.size()&&k==t.size())
         {
            Minresult=Min-i+1;
            p=Min;
            q=i;                         //用p,q存储最小子串的首尾位置
         }
         Min=0;
         k=0;
   }
   //循环结束,返回以q开头,p结束的最小子串
   if(p==0&&q==0)
   {
         result='""';
   }
   else
   {
         for(int h=q;h<=p;h++)
         {
            result.push_back(s);
         }
   }
   return result;
}
};
希望大佬们可以看看哪里错了,谢谢!

人造人 发表于 2021-8-10 20:23:26

这个算法不对，你现在是 j 一直后移，k 是在匹配到字符才后移，题目要求不是这样的
用这个思路写吧，虽然这个思路超时，但是至少正确
这道题的思路是：
1) begin开始指向0， end一直后移，直到begin - end区间包含T中所有字符。
记录窗口长度d
2) 然后begin开始后移移除元素，直到移除的字符是T中的字符则停止，此时T中有一个字符没被
包含在窗口，
3) 继续后移end，直到T中的所有字符被包含在窗口，重新记录最小的窗口d。
4) 如此循环知道end到S中的最后一个字符。

for(size_t j = i; j < s.size() && k < t.size(); j++)
{
if(t == s)
{
   k++;

   // max 赋值给 min ?
   // 把最大的赋值给最小的？这是什么操作？
   Min = max(Min, j);          //表示以i开头,这一段至少需要的子串
   Delete(s, j);             //在这个循环中把s中已经使用过的j删除,避免无法判断重复元素
   j = i - 1;

   // 为什么要加这个 continue ?
   // 这里的 continue 对程序没有任何影响
   // 加不加都一样
   //continue;
}                            //得到从i到Min的一串子串为需要的子串(但不一定是最小子串)
}

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

class Solution {
public:
//void Delete(string x,int n)
void Delete(string &x,int n)
{
   size_t i;
   for(i=n;i<x.size()-1;i++)
   {
         x=x;
   }
   x=' ';
}

string minWindow(string s, string t) {
   size_t k = 0;
   int p = -1, q = -1;
   size_t Minresult = s.size();
   size_t Min = -1;
   string result, r, S = s;
#if 0
   if(s.size()<t.size())
   {
         /*
         result="";
         return result;
         */
         return "";
   }
   if(s == t)
   {
         return s;
   }
#endif
   if(s == t) return s;
   if(s.size() < t.size()) return "";
   for(size_t i = 0; i <= s.size() - t.size(); i++)
   {

         std::cout << "i: " << i << std::endl;

         for(size_t j = i; j < s.size() && k < t.size(); j++)
         {

            std::cout << "k: " << k << ", " << "t: " << "'" << t << "'" << std::endl;
            std::cout << "j: " << j << ", " << "s: " << "'" << s << "'" << std::endl;
            std::cout << std::endl;

            if(t == s)
            {
               k++;

               // max 赋值给 min ?
               // 把最大的赋值给最小的？这是什么操作？
               Min = max(Min, j);          //表示以i开头,这一段至少需要的子串
               Delete(s, j);             //在这个循环中把s中已经使用过的j删除,避免无法判断重复元素
               j = i - 1;

               // 为什么要加这个 continue ?
               // 这里的 continue 对程序没有任何影响
               // 加不加都一样
               //continue;
            }                            //得到从i到Min的一串子串为需要的子串(但不一定是最小子串)
         }
         if(Minresult > Min - i && (Min - i + 1) >= t.size() && k == t.size())
         {
            Minresult = Min - i + 1;
            p = Min;
            q = i;                         //用p,q存储最小子串的首尾位置
         }
         Min = -1;
         k = 0;
         s = S;                            //还原s,开始下一次循环
   }
   //循环结束,返回以q开头,p结束的最小子串
   if(p == -1 && q == -1) return "";
   return string(&s, &s);
#if 0
   if(p==-1&&q==-1)
   {
         result="";
   }
   else
   {
         /*
         for(int h=q;h<=p;h++)
         {
            result.push_back(s);
         }
         */
         result = string(&s, &s);
   }
   return result;
#endif
}
};

int main() {
std::cout << Solution().minWindow("bbaa", "aba") << std::endl;
return 0;
}

人造人 发表于 2021-8-11 00:04:00

for(int i=0;i<s.size()-t.size();i++)
s.size() 是 1
t.size() 是 1
1 - 1 = 0
for(int i=0;i<0;i++)
提问：这个循环执行几次？

202021130162 发表于 2021-8-11 17:35:49

人造人发表于 2021-8-11 00:04
for(int i=0;i

!哦哦哦知道了!

202021130162 发表于 2021-8-11 18:07:37

本帖最后由 202021130162 于 2021-8-11 18:08 编辑

人造人发表于 2021-8-11 00:04
for(int i=0;i

我改了一下之后又有新的问题了,如果子串里面有重复的字符,就会出错
例如:
输入:
"acbbaca"
"aba"
输出:
"bba"
预期结果:
"baca"

代码如下:
class Solution {
public:
void Delete(string x,int n)
{
   int i;
   for(i=n;i<x.size()-1;i++)
   {
         x=x;
   }
   x=' ';
}

string minWindow(string s, string t) {
   int k=0;
   int p=-1,q=-1;
   int Minresult=s.size();
   int Min=-1;
   string result,r,S=s;
   if(s.size()<t.size())
   {
         result='""';
         return result;
   }
   if(s==t)
   {
         return s;
   }
   for(int i=0;i<=s.size()-t.size();i++)
   {
         for(int j=i;j<s.size()&&k<t.size();j++)
         {
            if(t==s)
            {
               k++;
               Min=max(Min,j);          //表示以i开头,这一段至少需要的子串
               Delete(s,j);             //在这个循环中把s中已经使用过的j删除,避免无法判断重复元素
               j=i-1;
               continue;
            }                            //得到从i到Min的一串子串为需要的子串(但不一定是最小子串)
         }
         if(Minresult>Min-i&&(Min-i+1)>=t.size()&&k==t.size())
         {
            Minresult=Min-i+1;
            p=Min;
            q=i;                         //用p,q存储最小子串的首尾位置
         }
         Min=-1;
         k=0;
         s=S;                            //还原s,开始下一次循环
   }
   //循环结束,返回以q开头,p结束的最小子串
   if(p==-1&&q==-1)
   {
         result='""';
   }
   else
   {
         for(int h=q;h<=p;h++)
         {
            result.push_back(s);
         }
   }
   return result;
}
};

人造人 发表于 2021-8-11 18:43:09

202021130162 发表于 2021-8-11 18:07
我改了一下之后又有新的问题了,如果子串里面有重复的字符,就会出错
例如:
输入:

#include <iostream>
#include <string>

using namespace std;

class Solution {
public:
void Delete(string x,int n)
{
   int i;
   for(i=n;i<x.size()-1;i++)
   {
         x=x;
   }
   x=' ';
}

string minWindow(string s, string t) {
   int k=0;
   int p=-1,q=-1;
   int Minresult=s.size();
   int Min=-1;
   string result,r,S=s;
   if(s.size()<t.size())
   {
         result='""';
         return result;
   }
   if(s==t)
   {
         return s;
   }
   for(int i=0;i<=s.size()-t.size();i++)
   {
         for(int j=i;j<s.size()&&k<t.size();j++)
         {
            if(t==s)
            {
               k++;
               Min=max(Min,j);          //表示以i开头,这一段至少需要的子串
               Delete(s,j);             //在这个循环中把s中已经使用过的j删除,避免无法判断重复元素
               j=i-1;
               continue;
            }                            //得到从i到Min的一串子串为需要的子串(但不一定是最小子串)
         }
         if(Minresult>Min-i&&(Min-i+1)>=t.size()&&k==t.size())
         {
            Minresult=Min-i+1;
            p=Min;
            q=i;                         //用p,q存储最小子串的首尾位置
         }
         Min=-1;
         k=0;
         s=S;                            //还原s,开始下一次循环
   }
   //循环结束,返回以q开头,p结束的最小子串
   if(p==-1&&q==-1)
   {
         result='""';
   }
   else
   {
         for(int h=q;h<=p;h++)
         {
            result.push_back(s);
         }
   }
   return result;
}
};

int main() {
std::cout << Solution().minWindow("acbbaca", "aba") << std::endl;
return 0;
}

$ g++ -g -Wall -o main main.cpp
main.cpp:26:23: warning: multi-character character constant [-Wmultichar]
26 |          result='""';
   |                   ^~~~
main.cpp:59:23: warning: multi-character character constant [-Wmultichar]
59 |          result='""';
   |                   ^~~~
main.cpp: In member function ‘void Solution::Delete(std::string, int)’:
main.cpp:11:18: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::basic_string<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
11 |       for(i=n;i<x.size()-1;i++)
   |             ~^~~~~~~~~~~
main.cpp: In member function ‘std::string Solution::minWindow(std::string, std::string)’:
main.cpp:26:23: warning: overflow in conversion from ‘int’ to ‘std::basic_string<char>::value_type’ {aka ‘char’} changes value from ‘8738’ to ‘34’ [-Woverflow]
26 |          result='""';
   |                   ^~~~
main.cpp:33:22: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::basic_string<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
33 |       for(int i=0;i<=s.size()-t.size();i++)
   |                   ~^~~~~~~~~~~~~~~~~~~
main.cpp:35:26: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::basic_string<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
35 |          for(int j=i;j<s.size()&&k<t.size();j++)
   |                      ~^~~~~~~~~
main.cpp:35:38: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::basic_string<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
35 |          for(int j=i;j<s.size()&&k<t.size();j++)
   |                                  ~^~~~~~~~~
main.cpp:46:42: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::basic_string<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
46 |          if(Minresult>Min-i&&(Min-i+1)>=t.size()&&k==t.size())
   |                               ~~~~~~~~~^~~~~~~~~~
main.cpp:46:55: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::basic_string<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
46 |          if(Minresult>Min-i&&(Min-i+1)>=t.size()&&k==t.size())
   |                                                    ~^~~~~~~~~~
main.cpp:59:23: warning: overflow in conversion from ‘int’ to ‘std::basic_string<char>::value_type’ {aka ‘char’} changes value from ‘8738’ to ‘34’ [-Woverflow]
59 |          result='""';
   |                   ^~~~

语法错误
result='""';// 这是什么操作？

202021130162 发表于 2021-8-11 20:24:32

人造人发表于 2021-8-11 18:43
语法错误
result='""';// 这是什么操作？

这是题目要求啊:
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

而且我在leedcode上没报错啊
https://xxx.ilovefishc.com/album/202108/11/202348rgug8w4vozm4yzgs.png.thumb.jpg

人造人 发表于 2021-8-11 22:57:47

202021130162 发表于 2021-8-11 20:24
这是题目要求啊:
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不 ...

你 C++ 语法不过关呀，给一个字符位置赋值一个字符串？
result='""';

下面这 3 个可以
result = '0';
result = '\0';
result = 123;

还有，有符号数和无符号数不要混用
这样就没有语法错误了，但是还有逻辑错误，这个代码无法通过测试的，我看不懂你的算法，可以说一说你的算法实现思路吗？
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

class Solution {
public:
void Delete(string x,int n)
{
   //int i;
   size_t i;
   for(i=n;i<x.size()-1;i++)
   {
         x=x;
   }
   x=' ';
}

string minWindow(string s, string t) {
   //int k=0;
   size_t k=0;
   int p=-1,q=-1;
   //int Minresult=s.size();
   size_t Minresult=s.size();
   //int Min=-1;
   size_t Min=-1;
   string result,r,S=s;
   if(s.size()<t.size())
   {
         //result='""';
         result="";
         return result;
   }
   if(s==t)
   {
         return s;
   }
   //for(int i=0;i<=s.size()-t.size();i++)
   for(size_t i=0;i<=s.size()-t.size();i++)
   {
         //for(int j=i;j<s.size()&&k<t.size();j++)
         for(size_t j=i;j<s.size()&&k<t.size();j++)
         {
            if(t==s)
            {
               k++;
               Min=max(Min,j);          //表示以i开头,这一段至少需要的子串
               Delete(s,j);             //在这个循环中把s中已经使用过的j删除,避免无法判断重复元素
               j=i-1;
               continue;
            }                            //得到从i到Min的一串子串为需要的子串(但不一定是最小子串)
         }
         if(Minresult>Min-i&&(Min-i+1)>=t.size()&&k==t.size())
         {
            Minresult=Min-i+1;
            p=Min;
            q=i;                         //用p,q存储最小子串的首尾位置
         }
         Min=-1;
         k=0;
         s=S;                            //还原s,开始下一次循环
   }
   //循环结束,返回以q开头,p结束的最小子串
   if(p==-1&&q==-1)
   {
         //result='""';
         result="";
   }
   else
   {
         for(int h=q;h<=p;h++)
         {
            result.push_back(s);
         }
   }
   return result;
}
};

int main() {
std::cout << Solution().minWindow("bbaa", "aba") << std::endl;
return 0;
}

我自己也写了一个，但是算法选错了，超时
要学着调试程序呀，其实就是不断调试程序，把不通过的测试一个一个的解决
我的算法思路
这道题的思路是：
1) begin开始指向0， end一直后移，直到begin - end区间包含T中所有字符。
记录窗口长度d
2) 然后begin开始后移移除元素，直到移除的字符是T中的字符则停止，此时T中有一个字符没被
包含在窗口，
3) 继续后移end，直到T中的所有字符被包含在窗口，重新记录最小的窗口d。
4) 如此循环知道end到S中的最后一个字符。
参考: https://www.nowcoder.com/questionTerminal/c466d480d20c4c7c9d322d12ca7955ac

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

class Solution {
public:
string minWindow(string s, string t) {
   size_t begin = 0, end;
   string s_bak = s;
   string result;
   while(true) {
         if(s.size() - begin < t.size()) break;
         while(begin < s.size() && t.find(s) == string::npos) ++begin;
         end = begin; if(begin >= s.size()) break;
         for(size_t i = 0; i < t.size(); ++i) {
            size_t pos = s.find(t, begin);
            if(pos == string::npos) {
               end = begin; break;
            } else {
               s = -1;
               if(pos >= end) end = pos + 1;
            }
         }
         s = s_bak;
         string new_result(&s, &s);
         if(!new_result.empty()) {
            if(result.empty() || result.size() > new_result.size())
               result = new_result;
         }
         ++begin;
   }
   return result;
}
};

int main() {
std::cout << Solution().minWindow("bbaa", "aba") << std::endl;
return 0;
}

试了 19 次，最后 3 次超时，我目前对这个算法没招了，我想不到如何修改这个算法了，要通过这个测试，估计得换一个算法了，这个算法对这样的输入没办法

人造人 发表于 2021-8-11 22:59:30

202021130162 发表于 2021-8-11 20:24
这是题目要求啊:
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不 ...

leedcode 当然不报错了，它又不是用最高级别的警告编译代码的

人造人 发表于 2021-8-11 23:40:37

这个函数没有如何效果
有没有调用这个函数都不会对程序有任何影响
void Delete(string x,int n)
{
   int i;
   for(i=n;i<x.size()-1;i++)
   {
         x=x;
   }
   x=' ';
}

要传引用
void Delete(string &x, int n)
{
   int i;
   for(i=n;i<x.size()-1;i++)
   {
         x=x;
   }
   x=' ';
}

202021130162 发表于 2021-8-12 16:03:11

人造人发表于 2021-8-11 22:57
你 C++ 语法不过关呀，给一个字符位置赋值一个字符串？
result='""';

我的思路:
1.对s中的每个字符s,s...,都去查找以它开头的子串,子串中包含t中所有的字符
2.得到了许多组字符串,再从这些字符中找到长度最小的字符串,即为答案

然后对于那个Delete函数,想要实现的功能就是:
由于题目字符串t中会有重复字符,那么在查找s的子串时,我碰到一个t中的字符,就把对应的s字符删掉,这样就可以让s的子串中包含对应数量的t字符
避免出现以下情况:
输入:s=abca,t=aba
输出:ab

人造人 发表于 2021-8-12 17:31:36

看不懂你的代码
这个代码，输入 Solution().minWindow("bbaa", "aba")
执行到 69 行的时候 p 和 q 都是 -1，也就是 58 行的 if 每一次都不成立
60，61，62 行的代码没有执行过

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

class Solution {
public:
//void Delete(string x,int n)
void Delete(string &x,int n)
{
   size_t i;
   for(i=n;i<x.size()-1;i++)
   {
         x=x;
   }
   x=' ';
}

string minWindow(string s, string t) {
   size_t k=0;
   int p=-1,q=-1;
   size_t Minresult=s.size();
   size_t Min=-1;
   string result,r,S=s;
   if(s.size()<t.size())
   {
         /*
         result="";
         return result;
         */
         return "";
   }
   if(s==t)
   {
         return s;
   }
   for(size_t i=0;i<=s.size()-t.size();i++)
   {
         for(size_t j=i;j<s.size()&&k<t.size();j++)
         {
            if(t==s)
            {
               k++;

               // max 赋值给 min ?
               // 把最大的赋值给最小的？这是什么操作？
               Min=max(Min,j);          //表示以i开头,这一段至少需要的子串
               Delete(s,j);             //在这个循环中把s中已经使用过的j删除,避免无法判断重复元素
               j=i-1;

               // 为什么要加这个 continue ?
               // 这里的 continue 对程序没有任何影响
               // 加不加都一样
               //continue;
            }                            //得到从i到Min的一串子串为需要的子串(但不一定是最小子串)
         }
         if(Minresult>Min-i&&(Min-i+1)>=t.size()&&k==t.size())
         {
            Minresult=Min-i+1;
            p=Min;
            q=i;                         //用p,q存储最小子串的首尾位置
         }
         Min=-1;
         k=0;
         s=S;                            //还原s,开始下一次循环
   }
   //循环结束,返回以q开头,p结束的最小子串
   if(p==-1&&q==-1)
   {
         result="";
   }
   else
   {
         /*
         for(int h=q;h<=p;h++)
         {
            result.push_back(s);
         }
         */
         result = string(&s, &s);
   }
   return result;
}
};

int main() {
std::cout << Solution().minWindow("bbaa", "aba") << std::endl;
return 0;
}

人造人 发表于 2021-8-12 18:02:37

参考这个

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

class Solution {
public:
string minWindow(string s, string t) {
   size_t begin = 0, end;
   string s_bak = s;
   string result;
   while(true) {
         if(s.size() - begin < t.size()) break;
         while(begin < s.size() && t.find(s) == string::npos) ++begin;
         end = begin; if(begin >= s.size()) break;
         for(size_t i = 0; i < t.size(); ++i) {
            size_t pos = s.find(t, begin);
            if(pos == string::npos) {
               end = begin; break;
            } else {
               s = -1;
               if(pos >= end) end = pos + 1;
            }
         }
         s = s_bak;
         string new_result(&s, &s);
         if(!new_result.empty()) {
            if(result.empty() || result.size() > new_result.size())
               result = new_result;
         }
         ++begin;
   }
   return result;
}
};

int main() {
std::cout << Solution().minWindow("bbaa", "aba") << std::endl;
return 0;
}

202021130162 发表于 2021-8-14 19:15:17

人造人发表于 2021-8-12 18:02
参考这个

好的,还是得用滑动窗口写,谢谢啦!

页: [1]

鱼C论坛's Archiver

力扣的题76. 最小覆盖子串