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 条评论
登录 后参与评论

相关文章

来自专栏从流域到海域

《数据结构》 栈代码操作集合

栈的基本操作代码,来自《数据结构-用C语言描述》(第二版)高教社 栈的数据结构相当于受限制(只能从栈顶取元素,先进后出LIFO)的顺序表或单链表,可以...

1696
来自专栏拭心的安卓进阶之路

Java 集合深入理解(4):List<E> 接口

蓝瘦!香菇! 连着加班几天,醉了。学学 List 放松下! ? 在 Java 集合深入理解:Collection 中我们熟悉了 Java 集合框架的基本概念和...

21110
来自专栏mathor

C++STL中set的使用策略(二)

683
来自专栏机器学习和数学

[数据结构与算法] 链接表总结

上一次说到了顺序表,链接表和顺序表一样,也是线性表。那为什么有了线性表还要有链接表呢?总之就是当数据过大时,顺序表存在一些存储方面的限制,而链接表比顺序表要更有...

2707
来自专栏恰同学骚年

剑指Offer面试题:4.从尾到头打印链表

  到解决这个问题肯定要遍历链表。遍历的顺序是从头到尾的顺序,可输出的顺序却是从尾到头。也就是说第一个遍历到的结点最后一个输出,而最后一个遍历到的结点第一个输出...

744
来自专栏Bingo的深度学习杂货店

Q66 Plus One

Given a non-negative integer represented as a non-empty array of digits, plus on...

3156
来自专栏计算机视觉与深度学习基础

Leetcode 76 Minimum Window Substring

Given a string S and a string T, find the minimum window in S which will contai...

1778
来自专栏计算机视觉与深度学习基础

Leetcode 179 Largest Number

Given a list of non negative integers, arrange them such that they form the lar...

21210
来自专栏静默虚空的博客

单链表的C++实现(采用模板类)

采用模板类实现的好处是,不用拘泥于特定的数据类型。就像活字印刷术,制定好模板,就可以批量印刷,比手抄要强多少倍! 此处不具体介绍泛型编程,还是着重叙述链表的定义...

1917
来自专栏技术碎碎念

LeetCode-15-3Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b ...

34911

扫码关注云+社区