算法超时

好故事慢慢来

Description
给你一个二进制字符串s，该字符串不含前导零。

如果s包含零个或一个由连续的'1'组成的字段，返回true​​​。否则，返回false


Input
输入一个只含01的字符串s

1≤s.length≤100


Output
输出true或false
求一个高效c++算法

isdkz

这道题可以使用双指针来解决，时间复杂度为O(n)。

算法步骤如下：

1. 定义两个指针left和right，分别指向字符串s的开头和结尾。

2. 当left和right指向的字符都是'1'时，将right向右移动。

3. 当left和right指向的字符不全是'1'时，判断是否存在一个'0'，如果存在则返回false，否则将left向右移动。

4. 重复步骤2和3，直到left和right相遇。

5. 如果没有返回false，则返回true。

C++代码如下：

1. #include <iostream>
   
2. #include <string>
   
3. using namespace std;
   
4. 
   
5. bool check(string s) {
   
6.     int left = 0, right = s.size() - 1;
   
7.     while (left < right) {
   
8.         while (s[left] == '1' && s[right] == '1') {
   
9.             right--;
   
10.         }
    
11.         if (s[left] != '1') {
    
12.             if (s.find('0', left) != string::npos && s.find('0', left) < right) {
    
13.                 return false;
    
14.             }
    
15.             left++;
    
16.         }
    
17.     }
    
18.     return true;
    
19. }
    
20. 
    
21. int main() {
    
22.     string s;
    
23.     cin >> s;
    
24.     cout << (check(s) ? "true" : "false") << endl;
    
25.     return 0;
    
26. }
    

复制代码

时间复杂度：O(n)

陶远航

这是一个相对简单的问题，我们可以通过遍历字符串来解决。我们需要找到连续的'1'，并计数这些连续的'1'的数量。如果我们找到超过一个这样的连续的'1'，我们就返回false。否则，我们返回true。

以下是一个C++的解决方案：

1. #include <string>
   
2. 
   
3. bool checkBinaryString(const std::string& s) {
   
4.     int count = 0;
   
5.     for (int i = 0; i < s.length(); ++i) {
   
6.         if (s[ i] == '1') {
   
7.             // 如果当前字符是'1'，并且它是第一个字符，或者前一个字符不是'1'，则增加计数
   
8.             if (i == 0 || s[i - 1] != '1') {
   
9.                 ++count;
   
10.             }
    
11.             // 如果我们找到超过一个连续的'1'，则返回false
    
12.             if (count > 1) {
    
13.                 return false;
    
14.             }
    
15.         }
    
16.     }
    
17.     // 如果我们没有找到超过一个连续的'1'，则返回true
    
18.     return true;
    
19. }
    

复制代码

这个算法的时间复杂度是O(n)，其中n是字符串s的长度。这是因为我们只遍历了一次字符串。这个算法的空间复杂度是O(1)，因为我们只使用了一个固定大小的变量来存储计数。
请注意，本回答来自GPT-4
如果问题已经解决，请设置最佳答案

Mike_python小

问题分析：

要判断一个二进制字符串是否满足条件，即不包含连续的多个'1'。我们可以遍历字符串，检查是否存在连续的两个字符为'1'的情况。

解决方案：

以下是一种使用C++实现的高效算法，通过遍历字符串判断条件：

2. #include <iostream>
3. #include <string>
4. using namespace std;
6. bool checkBinaryString(const string& s) {
7.     int n = s.length();
8.     for (int i = 0; i < n - 1; i++) {
9.         if (s[i] == '1' && s[i+1] == '1') {
10.             return false;
11.         }
12.     }
13.     return true;
14. }
16. int main() {
17.     string s;
18.     cin >> s;
19.     bool result = checkBinaryString(s);
20.     cout << (result ? "true" : "false") << endl;
21.     return 0;
22. }

复制代码

这种算法的时间复杂度为O(n)，其中n是字符串的长度。遍历一次字符串，逐个比较相邻字符是否为'1'，如果找到连续的两个'1'，则返回false。如果遍历结束都没有找到连续的两个'1'，则返回true。

注意，该算法还假设输入的字符串不包含前导零。

希望这个算法能够帮助到你！如果你有任何其他问题，请随时提问。

球一个最佳答案谢谢啦！这对我非常重要！

好故事慢慢来

Mike_python小 发表于 2023-10-10 21:23
问题分析：

要判断一个二进制字符串是否满足条件，即不包含连续的多个'1'。我们可以遍历字符串，检查是否 ...

哥这回答案不对

好故事慢慢来

Mike_python小 发表于 2023-10-10 21:23
问题分析：

要判断一个二进制字符串是否满足条件，即不包含连续的多个'1'。我们可以遍历字符串，检查是否 ...

结果应该是true

好故事慢慢来

isdkz 发表于 2023-10-10 21:22
这道题可以使用双指针来解决，时间复杂度为O(n)。

算法步骤如下：

超时了哥

额外减小

上面几楼都是GPT回答的，低质量。

你能解释一下第一个样例吗？我觉得连续'1'的字段数应该是3.

yinda_peng

同问，你这个连续的1字段怎么理解？第一个样例11010100，为什么是两个？