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

相关文章

来自专栏专注研发

poj-1503-java大数相加

One of the first users of BIT's new supercomputer was Chip Diller. He extended h...

611
来自专栏机器学习入门

LWC 56:443. String Compression

LWC 56:443. String Compression 传送门:443. String Compression Problem: Given an ar...

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

Q771 Jewels and Stones

You're given strings J representing the types of stones that are jewels, and S r...

2974
来自专栏desperate633

LeetCode 13. Roman to Integer题目分析代码

给定一个罗马数字,将其转换成整数。 返回的结果要求在1到3999的范围内。 说明什么是 罗马数字? https://en.wikipedia.org/wi...

532
来自专栏机器学习入门

LWC 54:699. Falling Squares

LWC 54:699. Falling Squares 传送门:699. Falling Squares Problem: On an infinite nu...

1975
来自专栏机器学习入门

LWC 60:736. Parse Lisp Expression

LWC 60:736. Parse Lisp Expression 传送门:736. Parse Lisp Expression Problem: You a...

1887
来自专栏King_3的技术专栏

leetcode-747-Largest Number At Least Twice of Others(求vector的最大值和次大值)

2414
来自专栏菩提树下的杨过

Reactor 3 学习笔记(2)

上面的代码,reduce相当于把1到10累加求和,reduceWith则是先指定一个起始值,然后在这个起始值基础上再累加。(tips: 除了累加,还可以做阶乘)...

1532
来自专栏机器学习入门

LWC 54:697. Degree of an Array

LWC 54:697. Degree of an Array 传送门:697. Degree of an Array Problem: Given a non...

1797
来自专栏绿巨人专栏

Scala underscore的用途

2685

扫码关注云+社区