专栏文章歪解字符串中连续出现次数最多问题

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

最近的学习中遇到一个比较简单的题目：一个字符串由 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;
}

升级版

借助当前思路，我们完全可以解决其他类似问题，如果一个字符串并不是由0和1构成，依然可以采取相同的思路。假设某个字符串由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);
}