[已解决]力扣的题76. 最小覆盖子串

202021130162

新写的一个想法,在评论区找不到参考,可以通过题目给的测试,但提交时的测试用例:"a""a";返回结果是"",不知道哪里错了
题目链接:https://leetcode-cn.com/problems/minimum-window-substring/

1. class Solution {
   
2. public:
   
3.     string minWindow(string s, string t) {
   
4.         int k=0;
   
5.         int p=0,q=0;
   
6.         int Minresult=s.size();
   
7.         int Min=0;
   
8.         string result,r;
   
9.         for(int i=0;i<s.size()-t.size();i++)
   
10.         {
    
11.             for(int j=i;j<s.size()&&k<t.size();j++)
    
12.             {
    
13.                 if(t[k]==s[j])
    
14.                 {
    
15.                     k++;
    
16.                     Min=max(Min,j);             //表示以i开头,这一段至少需要的子串
    
17.                     j=i-1;
    
18.                     continue;
    
19.                 }                               //得到从i到Min的一串子串为需要的子串(但不一定是最小子串)
    
20.             }
    
21.             if(Minresult>Min-i&&(Min-i+1)>=t.size()&&k==t.size())
    
22.             {
    
23.                 Minresult=Min-i+1;
    
24.                 p=Min;
    
25.                 q=i;                            //用p,q存储最小子串的首尾位置
    
26.             }
    
27.             Min=0;
    
28.             k=0;
    
29.         }
    
30.         //循环结束,返回以q开头,p结束的最小子串
    
31.         if(p==0&&q==0)
    
32.         {
    
33.             result[0]='""';
    
34.         }
    
35.         else
    
36.         {
    
37.             for(int h=q;h<=p;h++)
    
38.             {
    
39.                 result.push_back(s[h]);
    
40.             }
    
41.         }
    
42.         return result;
    
43.     }
    
44. };

复制代码

希望大佬们可以看看哪里错了,谢谢!

最佳答案

月排行榜 / 总排行榜

人造人

2021-8-10 20:23:26

这个算法不对，你现在是 j 一直后移，k 是在匹配到字符才后移，题目要求不是这样的
用这个思路写吧，虽然这个思路超时，但是至少正确

1. 这道题的思路是：
   
2. 1) begin开始指向0， end一直后移，直到begin - end区间包含T中所有字符。
   
3. 记录窗口长度d
   
4. 2) 然后begin开始后移移除元素，直到移除的字符是T中的字符则停止，此时T中有一个字符没被
   
5. 包含在窗口，
   
6. 3) 继续后移end，直到T中的所有字符被包含在窗口，重新记录最小的窗口d。
   
7. 4) 如此循环知道end到S中的最后一个字符。

复制代码

1. for(size_t j = i; j < s.size() && k < t.size(); j++)
   
2. {
   
3.     if(t[k] == s[j])
   
4.     {
   
5.         k++;
   
6. 
   
7.         // max 赋值给 min ?
   
8.         // 把最大的赋值给最小的？这是什么操作？
   
9.         Min = max(Min, j);             //表示以i开头,这一段至少需要的子串
   
10.         Delete(s, j);               //在这个循环中把s中已经使用过的j删除,避免无法判断重复元素   
    
11.         j = i - 1;
    
12. 
    
13.         // 为什么要加这个 continue ?
    
14.         // 这里的 continue 对程序没有任何影响
    
15.         // 加不加都一样
    
16.         //continue;
    
17.     }                               //得到从i到Min的一串子串为需要的子串(但不一定是最小子串)
    
18. }

复制代码

1. #include <iostream>
   
2. #include <string>
   
3. #include <algorithm>
   
4. 
   
5. using namespace std;
   
6. 
   
7. class Solution {
   
8. public:
   
9.     //void Delete(string x,int n)
   
10.     void Delete(string &x,int n)
    
11.     {
    
12.         size_t i;
    
13.         for(i=n;i<x.size()-1;i++)
    
14.         {
    
15.             x[i]=x[i+1];
    
16.         }
    
17.         x[i-1]=' ';
    
18.     }
    
19. 
    
20.     string minWindow(string s, string t) {
    
21.         size_t k = 0;
    
22.         int p = -1, q = -1;
    
23.         size_t Minresult = s.size();
    
24.         size_t Min = -1;
    
25.         string result, r, S = s;
    
26. #if 0
    
27.         if(s.size()<t.size())
    
28.         {
    
29.             /*
    
30.             result="";
    
31.             return result;
    
32.             */
    
33.             return "";
    
34.         }
    
35.         if(s == t)
    
36.         {
    
37.             return s;
    
38.         }
    
39. #endif
    
40.         if(s == t) return s;
    
41.         if(s.size() < t.size()) return "";
    
42.         for(size_t i = 0; i <= s.size() - t.size(); i++)
    
43.         {
    
44. 
    
45.             std::cout << "i: " << i << std::endl;
    
46. 
    
47.             for(size_t j = i; j < s.size() && k < t.size(); j++)
    
48.             {
    
49. 
    
50.                 std::cout << "k: " << k << ", " << "t[k]: " << "'" << t[k] << "'" << std::endl;
    
51.                 std::cout << "j: " << j << ", " << "s[j]: " << "'" << s[j] << "'" << std::endl;
    
52.                 std::cout << std::endl;
    
53. 
    
54.                 if(t[k] == s[j])
    
55.                 {
    
56.                     k++;
    
57. 
    
58.                     // max 赋值给 min ?
    
59.                     // 把最大的赋值给最小的？这是什么操作？
    
60.                     Min = max(Min, j);             //表示以i开头,这一段至少需要的子串
    
61.                     Delete(s, j);               //在这个循环中把s中已经使用过的j删除,避免无法判断重复元素   
    
62.                     j = i - 1;
    
63. 
    
64.                     // 为什么要加这个 continue ?
    
65.                     // 这里的 continue 对程序没有任何影响
    
66.                     // 加不加都一样
    
67.                     //continue;
    
68.                 }                               //得到从i到Min的一串子串为需要的子串(但不一定是最小子串)
    
69.             }
    
70.             if(Minresult > Min - i && (Min - i + 1) >= t.size() && k == t.size())
    
71.             {
    
72.                 Minresult = Min - i + 1;
    
73.                 p = Min;
    
74.                 q = i;                            //用p,q存储最小子串的首尾位置
    
75.             }
    
76.             Min = -1;
    
77.             k = 0;
    
78.             s = S;                                //还原s,开始下一次循环
    
79.         }
    
80.         //循环结束,返回以q开头,p结束的最小子串
    
81.         if(p == -1 && q == -1) return "";
    
82.         return string(&s[q], &s[p + 1]);
    
83. #if 0
    
84.         if(p==-1&&q==-1)
    
85.         {
    
86.             result="";
    
87.         }
    
88.         else
    
89.         {
    
90.             /*
    
91.             for(int h=q;h<=p;h++)
    
92.             {
    
93.                 result.push_back(s[h]);
    
94.             }
    
95.             */
    
96.             result = string(&s[q], &s[p + 1]);
    
97.         }
    
98.         return result;
    
99. #endif
    
100.     }
     
101. };
     
102. 
     
103. int main() {
     
104.     std::cout << Solution().minWindow("bbaa", "aba") << std::endl;
     
105.     return 0;
     
106. }
     

复制代码

跳转到最佳答案楼层

人造人

这个算法不对，你现在是 j 一直后移，k 是在匹配到字符才后移，题目要求不是这样的
用这个思路写吧，虽然这个思路超时，但是至少正确

1. 这道题的思路是：
   
2. 1) begin开始指向0， end一直后移，直到begin - end区间包含T中所有字符。
   
3. 记录窗口长度d
   
4. 2) 然后begin开始后移移除元素，直到移除的字符是T中的字符则停止，此时T中有一个字符没被
   
5. 包含在窗口，
   
6. 3) 继续后移end，直到T中的所有字符被包含在窗口，重新记录最小的窗口d。
   
7. 4) 如此循环知道end到S中的最后一个字符。

复制代码

1. for(size_t j = i; j < s.size() && k < t.size(); j++)
   
2. {
   
3.     if(t[k] == s[j])
   
4.     {
   
5.         k++;
   
6. 
   
7.         // max 赋值给 min ?
   
8.         // 把最大的赋值给最小的？这是什么操作？
   
9.         Min = max(Min, j);             //表示以i开头,这一段至少需要的子串
   
10.         Delete(s, j);               //在这个循环中把s中已经使用过的j删除,避免无法判断重复元素   
    
11.         j = i - 1;
    
12. 
    
13.         // 为什么要加这个 continue ?
    
14.         // 这里的 continue 对程序没有任何影响
    
15.         // 加不加都一样
    
16.         //continue;
    
17.     }                               //得到从i到Min的一串子串为需要的子串(但不一定是最小子串)
    
18. }

复制代码

1. #include <iostream>
   
2. #include <string>
   
3. #include <algorithm>
   
4. 
   
5. using namespace std;
   
6. 
   
7. class Solution {
   
8. public:
   
9.     //void Delete(string x,int n)
   
10.     void Delete(string &x,int n)
    
11.     {
    
12.         size_t i;
    
13.         for(i=n;i<x.size()-1;i++)
    
14.         {
    
15.             x[i]=x[i+1];
    
16.         }
    
17.         x[i-1]=' ';
    
18.     }
    
19. 
    
20.     string minWindow(string s, string t) {
    
21.         size_t k = 0;
    
22.         int p = -1, q = -1;
    
23.         size_t Minresult = s.size();
    
24.         size_t Min = -1;
    
25.         string result, r, S = s;
    
26. #if 0
    
27.         if(s.size()<t.size())
    
28.         {
    
29.             /*
    
30.             result="";
    
31.             return result;
    
32.             */
    
33.             return "";
    
34.         }
    
35.         if(s == t)
    
36.         {
    
37.             return s;
    
38.         }
    
39. #endif
    
40.         if(s == t) return s;
    
41.         if(s.size() < t.size()) return "";
    
42.         for(size_t i = 0; i <= s.size() - t.size(); i++)
    
43.         {
    
44. 
    
45.             std::cout << "i: " << i << std::endl;
    
46. 
    
47.             for(size_t j = i; j < s.size() && k < t.size(); j++)
    
48.             {
    
49. 
    
50.                 std::cout << "k: " << k << ", " << "t[k]: " << "'" << t[k] << "'" << std::endl;
    
51.                 std::cout << "j: " << j << ", " << "s[j]: " << "'" << s[j] << "'" << std::endl;
    
52.                 std::cout << std::endl;
    
53. 
    
54.                 if(t[k] == s[j])
    
55.                 {
    
56.                     k++;
    
57. 
    
58.                     // max 赋值给 min ?
    
59.                     // 把最大的赋值给最小的？这是什么操作？
    
60.                     Min = max(Min, j);             //表示以i开头,这一段至少需要的子串
    
61.                     Delete(s, j);               //在这个循环中把s中已经使用过的j删除,避免无法判断重复元素   
    
62.                     j = i - 1;
    
63. 
    
64.                     // 为什么要加这个 continue ?
    
65.                     // 这里的 continue 对程序没有任何影响
    
66.                     // 加不加都一样
    
67.                     //continue;
    
68.                 }                               //得到从i到Min的一串子串为需要的子串(但不一定是最小子串)
    
69.             }
    
70.             if(Minresult > Min - i && (Min - i + 1) >= t.size() && k == t.size())
    
71.             {
    
72.                 Minresult = Min - i + 1;
    
73.                 p = Min;
    
74.                 q = i;                            //用p,q存储最小子串的首尾位置
    
75.             }
    
76.             Min = -1;
    
77.             k = 0;
    
78.             s = S;                                //还原s,开始下一次循环
    
79.         }
    
80.         //循环结束,返回以q开头,p结束的最小子串
    
81.         if(p == -1 && q == -1) return "";
    
82.         return string(&s[q], &s[p + 1]);
    
83. #if 0
    
84.         if(p==-1&&q==-1)
    
85.         {
    
86.             result="";
    
87.         }
    
88.         else
    
89.         {
    
90.             /*
    
91.             for(int h=q;h<=p;h++)
    
92.             {
    
93.                 result.push_back(s[h]);
    
94.             }
    
95.             */
    
96.             result = string(&s[q], &s[p + 1]);
    
97.         }
    
98.         return result;
    
99. #endif
    
100.     }
     
101. };
     
102. 
     
103. int main() {
     
104.     std::cout << Solution().minWindow("bbaa", "aba") << std::endl;
     
105.     return 0;
     
106. }
     

复制代码

人造人

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 00:04
for(int i=0;i

!哦哦哦知道了!

202021130162

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

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


代码如下:

1. class Solution {
   
2. public:
   
3.     void Delete(string x,int n)
   
4.     {
   
5.         int i;
   
6.         for(i=n;i<x.size()-1;i++)
   
7.         {
   
8.             x[i]=x[i+1];
   
9.         }
   
10.         x[i-1]=' ';
    
11.     }
    
12.    
    
13.     string minWindow(string s, string t) {
    
14.         int k=0;
    
15.         int p=-1,q=-1;
    
16.         int Minresult=s.size();
    
17.         int Min=-1;
    
18.         string result,r,S=s;
    
19.         if(s.size()<t.size())
    
20.         {
    
21.             result[0]='""';
    
22.             return result;
    
23.         }
    
24.         if(s==t)
    
25.         {
    
26.             return s;
    
27.         }
    
28.         for(int i=0;i<=s.size()-t.size();i++)
    
29.         {
    
30.             for(int j=i;j<s.size()&&k<t.size();j++)
    
31.             {
    
32.                 if(t[k]==s[j])
    
33.                 {
    
34.                     k++;
    
35.                     Min=max(Min,j);             //表示以i开头,这一段至少需要的子串
    
36.                     Delete(s,j);               //在这个循环中把s中已经使用过的j删除,避免无法判断重复元素   
    
37.                     j=i-1;
    
38.                     continue;
    
39.                 }                               //得到从i到Min的一串子串为需要的子串(但不一定是最小子串)
    
40.             }
    
41.             if(Minresult>Min-i&&(Min-i+1)>=t.size()&&k==t.size())
    
42.             {
    
43.                 Minresult=Min-i+1;
    
44.                 p=Min;
    
45.                 q=i;                            //用p,q存储最小子串的首尾位置
    
46.             }
    
47.             Min=-1;
    
48.             k=0;
    
49.             s=S;                                //还原s,开始下一次循环
    
50.         }
    
51.         //循环结束,返回以q开头,p结束的最小子串
    
52.         if(p==-1&&q==-1)
    
53.         {
    
54.             result[0]='""';
    
55.         }
    
56.         else
    
57.         {
    
58.             for(int h=q;h<=p;h++)
    
59.             {
    
60.                 result.push_back(s[h]);
    
61.             }
    
62.         }
    
63.         return result;
    
64.     }
    
65. };
    

复制代码

人造人

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

1. #include <iostream>
   
2. #include <string>
   
3. 
   
4. using namespace std;
   
5. 
   
6. class Solution {
   
7. public:
   
8.     void Delete(string x,int n)
   
9.     {
   
10.         int i;
    
11.         for(i=n;i<x.size()-1;i++)
    
12.         {
    
13.             x[i]=x[i+1];
    
14.         }
    
15.         x[i-1]=' ';
    
16.     }
    
17.    
    
18.     string minWindow(string s, string t) {
    
19.         int k=0;
    
20.         int p=-1,q=-1;
    
21.         int Minresult=s.size();
    
22.         int Min=-1;
    
23.         string result,r,S=s;
    
24.         if(s.size()<t.size())
    
25.         {
    
26.             result[0]='""';
    
27.             return result;
    
28.         }
    
29.         if(s==t)
    
30.         {
    
31.             return s;
    
32.         }
    
33.         for(int i=0;i<=s.size()-t.size();i++)
    
34.         {
    
35.             for(int j=i;j<s.size()&&k<t.size();j++)
    
36.             {
    
37.                 if(t[k]==s[j])
    
38.                 {
    
39.                     k++;
    
40.                     Min=max(Min,j);             //表示以i开头,这一段至少需要的子串
    
41.                     Delete(s,j);               //在这个循环中把s中已经使用过的j删除,避免无法判断重复元素   
    
42.                     j=i-1;
    
43.                     continue;
    
44.                 }                               //得到从i到Min的一串子串为需要的子串(但不一定是最小子串)
    
45.             }
    
46.             if(Minresult>Min-i&&(Min-i+1)>=t.size()&&k==t.size())
    
47.             {
    
48.                 Minresult=Min-i+1;
    
49.                 p=Min;
    
50.                 q=i;                            //用p,q存储最小子串的首尾位置
    
51.             }
    
52.             Min=-1;
    
53.             k=0;
    
54.             s=S;                                //还原s,开始下一次循环
    
55.         }
    
56.         //循环结束,返回以q开头,p结束的最小子串
    
57.         if(p==-1&&q==-1)
    
58.         {
    
59.             result[0]='""';
    
60.         }
    
61.         else
    
62.         {
    
63.             for(int h=q;h<=p;h++)
    
64.             {
    
65.                 result.push_back(s[h]);
    
66.             }
    
67.         }
    
68.         return result;
    
69.     }
    
70. };
    
71. 
    
72. int main() {
    
73.     std::cout << Solution().minWindow("acbbaca", "aba") << std::endl;
    
74.     return 0;
    
75. }
    

复制代码

1. $ g++ -g -Wall -o main main.cpp
   
2. main.cpp:26:23: warning: multi-character character constant [-Wmultichar]
   
3.    26 |             result[0]='""';
   
4.       |                       ^~~~
   
5. main.cpp:59:23: warning: multi-character character constant [-Wmultichar]
   
6.    59 |             result[0]='""';
   
7.       |                       ^~~~
   
8. main.cpp: In member function ‘void Solution::Delete(std::string, int)’:
   
9. 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]
   
10.    11 |         for(i=n;i<x.size()-1;i++)
    
11.       |                 ~^~~~~~~~~~~
    
12. main.cpp: In member function ‘std::string Solution::minWindow(std::string, std::string)’:
    
13. 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]
    
14.    26 |             result[0]='""';
    
15.       |                       ^~~~
    
16. 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]
    
17.    33 |         for(int i=0;i<=s.size()-t.size();i++)
    
18.       |                     ~^~~~~~~~~~~~~~~~~~~
    
19. 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]
    
20.    35 |             for(int j=i;j<s.size()&&k<t.size();j++)
    
21.       |                         ~^~~~~~~~~
    
22. 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]
    
23.    35 |             for(int j=i;j<s.size()&&k<t.size();j++)
    
24.       |                                     ~^~~~~~~~~
    
25. 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]
    
26.    46 |             if(Minresult>Min-i&&(Min-i+1)>=t.size()&&k==t.size())
    
27.       |                                 ~~~~~~~~~^~~~~~~~~~
    
28. 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]
    
29.    46 |             if(Minresult>Min-i&&(Min-i+1)>=t.size()&&k==t.size())
    
30.       |                                                      ~^~~~~~~~~~
    
31. 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]
    
32.    59 |             result[0]='""';
    
33.       |                       ^~~~
    

复制代码

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

202021130162

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

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

而且我在leedcode上没报错啊

                               
登录/注册后可看大图

人造人

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

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

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

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

1. #include <iostream>
   
2. #include <string>
   
3. #include <algorithm>
   
4. 
   
5. using namespace std;
   
6. 
   
7. class Solution {
   
8. public:
   
9.     void Delete(string x,int n)
   
10.     {
    
11.         //int i;
    
12.         size_t i;
    
13.         for(i=n;i<x.size()-1;i++)
    
14.         {
    
15.             x[i]=x[i+1];
    
16.         }
    
17.         x[i-1]=' ';
    
18.     }
    
19. 
    
20.     string minWindow(string s, string t) {
    
21.         //int k=0;
    
22.         size_t k=0;
    
23.         int p=-1,q=-1;
    
24.         //int Minresult=s.size();
    
25.         size_t Minresult=s.size();
    
26.         //int Min=-1;
    
27.         size_t Min=-1;
    
28.         string result,r,S=s;
    
29.         if(s.size()<t.size())
    
30.         {
    
31.             //result[0]='""';
    
32.             result="";
    
33.             return result;
    
34.         }
    
35.         if(s==t)
    
36.         {
    
37.             return s;
    
38.         }
    
39.         //for(int i=0;i<=s.size()-t.size();i++)
    
40.         for(size_t i=0;i<=s.size()-t.size();i++)
    
41.         {
    
42.             //for(int j=i;j<s.size()&&k<t.size();j++)
    
43.             for(size_t j=i;j<s.size()&&k<t.size();j++)
    
44.             {
    
45.                 if(t[k]==s[j])
    
46.                 {
    
47.                     k++;
    
48.                     Min=max(Min,j);             //表示以i开头,这一段至少需要的子串
    
49.                     Delete(s,j);               //在这个循环中把s中已经使用过的j删除,避免无法判断重复元素   
    
50.                     j=i-1;
    
51.                     continue;
    
52.                 }                               //得到从i到Min的一串子串为需要的子串(但不一定是最小子串)
    
53.             }
    
54.             if(Minresult>Min-i&&(Min-i+1)>=t.size()&&k==t.size())
    
55.             {
    
56.                 Minresult=Min-i+1;
    
57.                 p=Min;
    
58.                 q=i;                            //用p,q存储最小子串的首尾位置
    
59.             }
    
60.             Min=-1;
    
61.             k=0;
    
62.             s=S;                                //还原s,开始下一次循环
    
63.         }
    
64.         //循环结束,返回以q开头,p结束的最小子串
    
65.         if(p==-1&&q==-1)
    
66.         {
    
67.             //result[0]='""';
    
68.             result="";
    
69.         }
    
70.         else
    
71.         {
    
72.             for(int h=q;h<=p;h++)
    
73.             {
    
74.                 result.push_back(s[h]);
    
75.             }
    
76.         }
    
77.         return result;
    
78.     }
    
79. };
    
80. 
    
81. int main() {
    
82.     std::cout << Solution().minWindow("bbaa", "aba") << std::endl;
    
83.     return 0;
    
84. }
    

复制代码

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

1. #include <iostream>
   
2. #include <algorithm>
   
3. #include <string>
   
4. 
   
5. using namespace std;
   
6. 
   
7. class Solution {
   
8. public:
   
9.     string minWindow(string s, string t) {
   
10.         size_t begin = 0, end;
    
11.         string s_bak = s;
    
12.         string result;
    
13.         while(true) {
    
14.             if(s.size() - begin < t.size()) break;
    
15.             while(begin < s.size() && t.find(s[begin]) == string::npos) ++begin;
    
16.             end = begin; if(begin >= s.size()) break;
    
17.             for(size_t i = 0; i < t.size(); ++i) {
    
18.                 size_t pos = s.find(t[i], begin);
    
19.                 if(pos == string::npos) {
    
20.                     end = begin; break;
    
21.                 } else {
    
22.                     s[pos] = -1;
    
23.                     if(pos >= end) end = pos + 1;
    
24.                 }
    
25.             }
    
26.             s = s_bak;
    
27.             string new_result(&s[begin], &s[end]);
    
28.             if(!new_result.empty()) {
    
29.                 if(result.empty() || result.size() > new_result.size())
    
30.                     result = new_result;
    
31.             }
    
32.             ++begin;
    
33.         }
    
34.         return result;
    
35.     }
    
36. };
    
37. 
    
38. int main() {
    
39.     std::cout << Solution().minWindow("bbaa", "aba") << std::endl;
    
40.     return 0;
    
41. }
    

复制代码

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

人造人

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

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

人造人

这个函数没有如何效果
有没有调用这个函数都不会对程序有任何影响

1.     void Delete(string x,int n)
   
2.     {
   
3.         int i;
   
4.         for(i=n;i<x.size()-1;i++)
   
5.         {
   
6.             x[i]=x[i+1];
   
7.         }
   
8.         x[i-1]=' ';
   
9.     }

复制代码

要传引用

1.     void Delete(string &x, int n)
   
2.     {
   
3.         int i;
   
4.         for(i=n;i<x.size()-1;i++)
   
5.         {
   
6.             x[i]=x[i+1];
   
7.         }
   
8.         x[i-1]=' ';
   
9.     }

复制代码

202021130162

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

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


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

人造人

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

1. #include <iostream>
   
2. #include <string>
   
3. #include <algorithm>
   
4. 
   
5. using namespace std;
   
6. 
   
7. class Solution {
   
8. public:
   
9.     //void Delete(string x,int n)
   
10.     void Delete(string &x,int n)
    
11.     {
    
12.         size_t i;
    
13.         for(i=n;i<x.size()-1;i++)
    
14.         {
    
15.             x[i]=x[i+1];
    
16.         }
    
17.         x[i-1]=' ';
    
18.     }
    
19. 
    
20.     string minWindow(string s, string t) {
    
21.         size_t k=0;
    
22.         int p=-1,q=-1;
    
23.         size_t Minresult=s.size();
    
24.         size_t Min=-1;
    
25.         string result,r,S=s;
    
26.         if(s.size()<t.size())
    
27.         {
    
28.             /*
    
29.             result="";
    
30.             return result;
    
31.             */
    
32.             return "";
    
33.         }
    
34.         if(s==t)
    
35.         {
    
36.             return s;
    
37.         }
    
38.         for(size_t i=0;i<=s.size()-t.size();i++)
    
39.         {
    
40.             for(size_t j=i;j<s.size()&&k<t.size();j++)
    
41.             {
    
42.                 if(t[k]==s[j])
    
43.                 {
    
44.                     k++;
    
45. 
    
46.                     // max 赋值给 min ?
    
47.                     // 把最大的赋值给最小的？这是什么操作？
    
48.                     Min=max(Min,j);             //表示以i开头,这一段至少需要的子串
    
49.                     Delete(s,j);               //在这个循环中把s中已经使用过的j删除,避免无法判断重复元素   
    
50.                     j=i-1;
    
51. 
    
52.                     // 为什么要加这个 continue ?
    
53.                     // 这里的 continue 对程序没有任何影响
    
54.                     // 加不加都一样
    
55.                     //continue;
    
56.                 }                               //得到从i到Min的一串子串为需要的子串(但不一定是最小子串)
    
57.             }
    
58.             if(Minresult>Min-i&&(Min-i+1)>=t.size()&&k==t.size())
    
59.             {
    
60.                 Minresult=Min-i+1;
    
61.                 p=Min;
    
62.                 q=i;                            //用p,q存储最小子串的首尾位置
    
63.             }
    
64.             Min=-1;
    
65.             k=0;
    
66.             s=S;                                //还原s,开始下一次循环
    
67.         }
    
68.         //循环结束,返回以q开头,p结束的最小子串
    
69.         if(p==-1&&q==-1)
    
70.         {
    
71.             result="";
    
72.         }
    
73.         else
    
74.         {
    
75.             /*
    
76.             for(int h=q;h<=p;h++)
    
77.             {
    
78.                 result.push_back(s[h]);
    
79.             }
    
80.             */
    
81.             result = string(&s[q], &s[p + 1]);
    
82.         }
    
83.         return result;
    
84.     }
    
85. };
    
86. 
    
87. int main() {
    
88.     std::cout << Solution().minWindow("bbaa", "aba") << std::endl;
    
89.     return 0;
    
90. }
    

复制代码

人造人

参考这个

1. #include <iostream>
   
2. #include <algorithm>
   
3. #include <string>
   
4. 
   
5. using namespace std;
   
6. 
   
7. class Solution {
   
8. public:
   
9.     string minWindow(string s, string t) {
   
10.         size_t begin = 0, end;
    
11.         string s_bak = s;
    
12.         string result;
    
13.         while(true) {
    
14.             if(s.size() - begin < t.size()) break;
    
15.             while(begin < s.size() && t.find(s[begin]) == string::npos) ++begin;
    
16.             end = begin; if(begin >= s.size()) break;
    
17.             for(size_t i = 0; i < t.size(); ++i) {
    
18.                 size_t pos = s.find(t[i], begin);
    
19.                 if(pos == string::npos) {
    
20.                     end = begin; break;
    
21.                 } else {
    
22.                     s[pos] = -1;
    
23.                     if(pos >= end) end = pos + 1;
    
24.                 }
    
25.             }
    
26.             s = s_bak;
    
27.             string new_result(&s[begin], &s[end]);
    
28.             if(!new_result.empty()) {
    
29.                 if(result.empty() || result.size() > new_result.size())
    
30.                     result = new_result;
    
31.             }
    
32.             ++begin;
    
33.         }
    
34.         return result;
    
35.     }
    
36. };
    
37. 
    
38. int main() {
    
39.     std::cout << Solution().minWindow("bbaa", "aba") << std::endl;
    
40.     return 0;
    
41. }
    

复制代码

202021130162

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

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