算法超时

好故事慢慢来

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++代码如下：

#include <iostream>
#include <string>
using namespace std;

bool check(string s) {
    int left = 0, right = s.size() - 1;
    while (left < right) {
        while (s[left] == '1' && s[right] == '1') {
            right--;
        }
        if (s[left] != '1') {
            if (s.find('0', left) != string::npos && s.find('0', left) < right) {
                return false;
            }
            left++;
        }
    }
    return true;
}

int main() {
    string s;
    cin >> s;
    cout << (check(s) ? "true" : "false") << endl;
    return 0;
}

时间复杂度：O(n)

陶远航

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

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

#include <string>

bool checkBinaryString(const std::string& s) {
    int count = 0;
    for (int i = 0; i < s.length(); ++i) {
        if (s[ i] == '1') {
            // 如果当前字符是'1'，并且它是第一个字符，或者前一个字符不是'1'，则增加计数
            if (i == 0 || s[i - 1] != '1') {
                ++count;
            }
            // 如果我们找到超过一个连续的'1'，则返回false
            if (count > 1) {
                return false;
            }
        }
    }
    // 如果我们没有找到超过一个连续的'1'，则返回true
    return true;
}

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

Mike_python小

问题分析：

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

解决方案：

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

#include <iostream>#include <string>using namespace std;bool checkBinaryString(const string& s) {    int n = s.length();    for (int i = 0; i < n - 1; i++) {        if (s[i] == '1' && s[i+1] == '1') {            return false;        }    }    return true;}int main() {    string s;    cin >> s;    bool result = checkBinaryString(s);    cout << (result ? "true" : "false") << endl;    return 0;}

这种算法的时间复杂度为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，为什么是两个？