FunTester 歪解字符串中连续出现次数最多问题

FunTester · 2021年02月15日 · 最后由 FunTester 回复于 2021年02月18日 · 70 次阅读

最近的学习中遇到一个比较简单的题目:一个字符串由 01 组成,求字符串中连续出现 1 的次数,例如:字符串0110011001111000中,连续1出现的最大次数是4。请用Java实现这个功能。

正经解

应该比较好理解,我也第一时间也只想到了一个方法,就是遍历。代码如下:

/*
 *一个字符串由01组成,求字符串中连续出现1的次数
 */
public class FunTester extends SourceCode {

    public static void main(String[] args) {
        String str = "01011001011111101110101010110110";

        int max = 0;//最大连续

        int concurrent = 0;//当前最大连续

        int still = 0; //0默认,2断开
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            char n = i == str.length() - 1 ? '0' : str.charAt(i + 1);
            if (c == '1') {
                concurrent++;
                if (n == '0') {
                    still = 2;
                }
                if (still == 2) {
                    max = concurrent > max ? concurrent : max;
                    still = 0;
                    concurrent = 0;
                }
            }
       }
        output(max);
  }

}

歪解

在看到一串01组成的字符串时候,突然想到可以用正则表达式搞定这个,有两个思路。

spit()

通过spit()方法分隔之后,遍历分隔后的数组中String对象的长度,即可得到答案。具体代码如下:


public static void main(String[] args) {
    String str = "01011001011111101110101010110110";

    int max = 0;//最大连续

    String[] split = str.split("0+");

    for (int i = 0; i < split.length; i++) {
        int length = split[i].length();
        max = length > max ? length : max;
    }
    output(max);
}

正则匹配

这个方法跟spit()类似,通过正则匹配将所有连续1组成的字符串提取出来,这样也可以得到一个完全由1组成的字符串组成的数组。代码如下:

public static void main(String[] args) {
       String str = "01011001011111101110101010110110";

       int max = 0;//最大连续

       List<String> strings = Regex.regexAll(str, "1+");

       for (int i = 0; i < strings.size(); i++) {
           int length = strings.get(i).length();
           max = length > max ? length : max;
       }
       output(max);
   }

其中regexAll()方法是我自己封装的Regex正则工具类中的,代码如下:

/**
 * 返回所有匹配项
 *
 * @param text  需要匹配的文本
 * @param regex 正则表达式
 * @return
 */
public static List<String> regexAll(String text, String regex) {
    Matcher matcher = matcher(text, regex);
    List<String> result = new ArrayList<>();
    while (matcher.find()) {
        result.add(matcher.group());
    }
    return result;
}

升级版

借助当前思路,我们完全可以解决其他类似问题,如果一个字符串并不是由01构成,依然可以采取相同的思路。假设某个字符串由1和其他的字符构成,求解相同的问题。依然可以通过正则的思路解决,当然第二个匹配思路依然是可行的。我下面分享一下,第一个spit分割思路的代码。

public static void main(String[] args) {
    String str = "0dsa10fds1fdsa10010111111fd014341104310fdasfds10fsdafdsfdsa101101gfd10";

    int max = 0;//最大连续

    String[] split = str.split("((?!1).)+");

    for (int i = 0; i < split.length; i++) {
        int length = split[i].length();
        max = length > max ? length : max;
    }
    output(max);
}

FunTester腾讯云年度作者,优秀讲师 | 腾讯云 + 社区权威认证,非著名测试开发,欢迎关注。

如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
共收到 2 条回复 时间 点赞

看样子没咋刷题,滑动窗口、双指针了解一下?

的确不刷题,双指针只是听过。有机会得了解了解这个。

需要 登录 后方可回复, 如果你还没有账号请点击这里 注册