侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【暴力, 模拟】二进制字符串重新安排顺序需要的时间

GabrielxD
2022-08-21 / 0 评论 / 0 点赞 / 31 阅读 / 352 字 / 正在检测是否收录...

题目

6157. 二进制字符串重新安排顺序需要的时间


给你一个二进制字符串 s 。在一秒之中,所有 子字符串 "01" 同时 被替换成 "10" 。这个过程持续进行到没有 "01" 存在。

请你返回完成这个过程所需要的秒数。

示例 1:

输入:s = "0110101"
输出:4
解释:
一秒后,s 变成 "1011010" 。
再过 1 秒后,s 变成 "1101100" 。
第三秒过后,s 变成 "1110100" 。
第四秒后,s 变成 "1111000" 。
此时没有 "01" 存在,整个过程花费 4 秒。
所以我们返回 4 。

示例 2:

输入:s = "11100"
输出:0
解释:
s 中没有 "01" 存在,整个过程花费 0 秒。
所以我们返回 0 。

提示:

  • 1 <= s.length <= 1000
  • s[i] 要么是 '0' ,要么是 '1'

解题

方法一:暴力 模拟

思路

字符串长度最大就 1000,直接暴力模拟就完事了。

C++ 我不知道有什么可以代替 Java replace() 的方法。

这题是有时间复杂度更低的解法的。

代码

class Solution {
    public int secondsToRemoveOccurrences(String s) {
        int cnt = 0;
        while (true) {
            String newStr = s.replace("01", "10");
            if (s.equals(newStr)) break;
            s = newStr;
            ++cnt;
        }
        return cnt;
    }
}
0

评论区