LWC 54:696. Count Binary Substrings

LWC 54:696. Count Binary Substrings

传送门:696. Count Binary Substrings

Problem:

Give a string s, count the number of non-empty (contiguous) substrings that have the same number of 0’s and 1’s, and all the 0’s and all the 1’s in these substrings are grouped consecutively. Substrings that occur multiple times are counted the number of times they occur.

Example 1:

Input: “00110011” Output: 6 Explanation: There are 6 substrings that have equal number of consecutive 1’s and 0’s: “0011”, “01”, “1100”, “10”, “0011”, and “01”. Notice that some of these substrings repeat and are counted the number of times they occur. Also, “00110011” is not a valid substring because all the 0’s (and 1’s) are not grouped together.

Example 2:

Input: “10101” Output: 4 Explanation: There are 4 substrings: “10”, “01”, “10”, “01” that have equal number of consecutive 1’s and 0’s.

Note:

s.length will be between 1 and 50,000.

s will only consist of “0” or “1” charters.

思路1: 实际上,对于每一位都只可能出现1次合法答案或者0次答案。因为如果存在第二个合法答案,一定不符合group的条件,比如“0011”和“1100”是无法合并在一块构成新的合法答案。

代码如下:

    public int countBinarySubstrings(String s) {

        int n = s.length();
        char[] cs = s.toCharArray();

        int cnt = 0;
        for (int i = 1; i < n; ++i){
            if (group(cs, i)) cnt ++;
        }
        return cnt;
   }

    boolean group(char[] cs, int j){
        int cnt = 1;
        int pre = cs[j] - '0';
        j --;

        while (j >= 0 && cs[j] - '0' == pre) {
            cnt ++;
            j --;
        }

        while (j >= 0 && cs[j] - '0' != pre && cnt != 0) {
            cnt --;
            j --;
        }

        return cnt == 0;
    }

思路2: 单纯的来看”00111”,它的个数为min(0出现的次数,1出现的次数),所以代码如下:(注意交替更新)

    public int countBinarySubstrings(String s) {
        int n = s.length();
        char[] cs = s.toCharArray();

        int now = cs[0] - '0';
        int cnt = 0;
        int ans = 0;
        int lst = 0;

        for (int i = 0; i < n; ++i) {
            if (now != cs[i]) {
                ans += Math.min(cnt, lst);
                lst = cnt;
                cnt = 1;
                now = cs[i];
            }
            else {
                cnt ++;
            }
        }

        ans += Math.min(cnt, lst);
        return ans;
    }

思路3: 采用map,累加和,把0011映射成数组{-1,-1,1,1},再求累加和得到{0,-1,-2,-1,0},所以出现-1的两个位置组成的subSeqence一定是可能的候选值,再判断是否符合group。

代码如下:

    public int countBinarySubstrings(String s) {
        int n = s.length();
        char[] cs = s.toCharArray();
        int[] num = new int[n];
        for (int i = 0; i < n; ++i) {
            num[i] = cs[i] == '0' ? - 1 : 1;
        }

        int[] sum = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            sum[i + 1] = sum[i] + num[i];
        }

        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 0);
        int cnt = 0;
        for (int i = 1; i <= n; ++i) {
            if (map.containsKey(sum[i])) {
                if (group(cs, map.get(sum[i]), i - 1)) cnt++;

            }
            map.put(sum[i], i);
        }
        return cnt;
    }

    boolean group(char[] cs, int i, int j) {
        int prev = cs[i] - '0';
        int n = j - i + 1;
        for (int k = 1; k < n / 2; ++k) {
            if (prev != cs[k + i] - '0') return false; 
        }
        return true;
    } 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏从零开始学 Web 前端

06 - JavaSE之常用类

public StringBuffer append(...) 可以为该 StringBuffer 对象添加字符序列,返回添加后的该 StringBuffer ...

672
来自专栏彭湖湾的编程世界

【算法】归并排序算法的编码和优化

参考资料 《算法(第4版)》          — — Robert Sedgewick, Kevin Wayne 归并排序的概念 归并排序的实现我是这样来描述...

2448
来自专栏Spark学习技巧

Java反射机制深入详解

一.概念   反射就是把Java的各种成分映射成相应的Java类。   Class类的构造方法是private,由JVM创建。   反射是java语言的一个特性...

1.7K7
来自专栏JMCui

Java泛型学习

1、泛型的概念     泛型即“参数化类型”,就比如我们定义方法的时候,定义一个变量,称为形参,变量值根据传进去的实参的值不同而改变。而泛型的出现,就是为了解决...

3154
来自专栏WebDeveloper

跟我学习php数组常用函数-下篇

如果是递归的,结果:array('hobby' => array('a' => 'ping-pong', 'b' => 'basketball'));

822
来自专栏C++

python笔记:#005#算数运算符

1272
来自专栏lgp20151222

ThreadLocal基本原理及运用

ThreadLocal提供本地线程变量。这个变量里面的值(通过get方法获取)是和其他线程分割开来的,变量的值只有当前线程能访问到,不像一般的类型比如Perso...

872
来自专栏三木的博客

Javascript中的数组

数组的定义: var colors = new Array(20); var colors = new Array('red');  // ['red'...

20110
来自专栏Netkiller

Java 反射,开发框架必备技能

反射一般开发者接触不到,反射主要用户框架的开发。例如我举一个例子你就明白了: http://www.netkiller.cn/news/list/2.html...

2735
来自专栏赵俊的Java专栏

删除元素

821

扫码关注云+社区