【LeetCode】检查二进制字符串字段 Java 题解

作者：Albert

2022 年 10 月 03 日
北京
本文字数：963 字
阅读完需：约 3 分钟

题目描述

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

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

如果 s 中由连续若干个 '1' 组成的字段数量不超过 1，返回 true 。否则，返回 false 。

示例 1：
输入：s = "1001"输出：false解释：由连续若干个 '1' 组成的字段数量为 2，返回 false
示例 2：
输入：s = "110"输出：true

来源：力扣（LeetCode）链接：https://leetcode.cn/problems/check-if-binary-string-has-at-most-one-segment-of-ones著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的算法题目是字符串处理题目，题目要求判断的是字符串中含有连续 1 的个数，如果连续 1 的个数小于等于 1，则返回 true，否则返回 false。
我们首先可以使用朴素算法，对字符串整体进行遍历，找到连续 1 的个数，然后比较计算出答案即可。
朴素算法完成之后,参看题解,继续深入了解这个题目。由于是二进制字符串，只包含 0 和 1，题目明确指出了字符串不含前导零。说明是以 1 开头的。若字符串 s 存在 "01" 串，那么 s 就是形如 "1...01..." 的字符串，此时 s 出现了至少两个连续的 '1' 片段，不满足题意，直接返回 false。
具体实现代码如下，供参考。

通过代码

朴素算法

class Solution {    public boolean checkOnesSegment(String s) {        boolean ans = false;        int n = s.length();        int cnt = 0;        for (int i = 0; i < n; i++){            if (s.charAt(i) == '1') {                int j = i;                while (j < n && s.charAt(j) == '1') {                    j++;                }                if (i != j) {                    cnt++;                    i = j;                }            }        }
        ans = cnt <= 1;        return ans;    }}

复制代码

优化解法

class Solution {    public boolean checkOnesSegment(String s) {        return !s.contains("01");    }}

复制代码

总结

上述朴素算法虽然是两重嵌套循环，但是是对同一个 i 的操作，因此时间复杂度是 O(n),空间复杂度是 O(1)
优化解法是充分利用题目条件，进行思考分析，代码比较简洁。优化算法的时间复杂度是 O(n),空间复杂度是 O(1)
坚持算法每日一题，加油！

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/45210771b5b0a8d0360c003ac】。文章转载请联系作者。

Albert

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

【LeetCode】检查二进制字符串字段 Java 题解

题目描述

思路分析

通过代码

总结

Albert

评论