1784.检查二进制字符串字段

【LetMeFly】1784.检查二进制字符串字段

力扣题目链接：https://leetcode.cn/problems/check-if-binary-string-has-at-most-one-segment-of-ones/

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

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

 

示例 1：

输入：s = "1001"
输出：false
解释：字符串中的 1 没有形成一个连续字段。

示例 2：

输入：s = "110"
输出：true

 

提示：

• 1 <= s.length <= 100
• s[i]​​​​ 为 '0' 或 '1'
• s[0] 为 '1'

方法一：统计连续的1的个数

使用连个变量：

• cnt1：连续1的个数
• lastIs1：上一个字符是否是1

初始值

• cnt1 = 0
• lastIs1 = 0

之后遍历字符串，如果上一个字符是0并且这个字符是1，那么“连续1”的个数加一。

记得遍历过程中更新lastIs1

• 时间复杂度$O(n)$，其中$n$是字符串长度
• 空间复杂度$O(1)$

AC代码

C++

class Solution {
public:
    bool checkOnesSegment(string& s) {
        int cnt1 = 0;
        bool lastIs1 = false;
        for (char& c : s) {
            if (c == '0') {
                lastIs1 = false;
            }
            else {
                if (!lastIs1) {
                    lastIs1 = true;
                    cnt1++;
                }
            }
        }
        return cnt1 < 2;
    }
};

方法二：查找“01”是否存在

这道题数据比较有意思：二进制串不含前导零

啥意思呢，意思就是二进制串第一个元素为1。

既然第一个元素为1，并且不能有“两块1”，那么就只能是数个之后全是0

一旦字符串中出现了“01”，就说明字符串中存在不只一个的“连续1”

因此，直接调用编程语言的API，查找字符串中是否存在“01”即可。

• 时间复杂度$O(n)$，其中$n$是字符串长度
• 空间复杂度$O(1)$

AC代码

C++

class Solution {
public:
    bool checkOnesSegment(string& s) {
        return s.find("01") == s.npos;
    }
};

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/127150307