计算二进制子串

LeetCode每日一题，696. Count Binary Substrings

先看题目描述

大意就是给定一个字符串 s，计算具有相同数量 0 和 1 的非空连续子字符串的个数，并且这些子字符串中所有的 0 和 1 都是组合在一起的

算法和思路

我们可以将字符串 s 按照 0 和 1 的连续段分组，存在 counts 数组中，例如 s = 00111011，可以得到这样的 counts 数组：counts= {2,3,1,2}

这里 counts 数组中两个相邻的数一定代表的是两种不同的字符。假设 counts 数组中两个相邻的数字为 u 和 v，它们对应着 u 个 00 和 v 个 1，或者 u 个 1 和 v 个 0。它们能组成的满足条件的子串数目为 min{u ,v}，即一对相邻的数字对答案的贡献

我们只要遍历所有相邻的数对，求它们的贡献总和，即可得到答案

实现源码

一开始是这样实现的，结果超时了，原因是求 counts 数组所花的时间太长

import java.util.LinkedList;
import java.util.List;

class Solution {
    public int countBinarySubstrings(String s) {
        int len = s.length();
        int res = 0;
        List<Integer> counts = new LinkedList<>();
        int count = 0;
        for (int i = 0; i < len; i++) {
            if (i > 0 && s.charAt(i) != s.charAt(i - 1)) {
                counts.add(count);
                count = 0;
            }
            count += 1;
        }
        counts.add(count);
        for (int i = 0; i< counts.size() - 1; i++) {
            res += Math.min(counts.get(i), counts.get(i + 1));
        }
        return res;
    }
}

后来看了题解发现是自己想错方向了，用两层 while 循环就可以求出需要的 counts 数组

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int countBinarySubstrings(String s) {
        int len = s.length();
        int ptr = 0;
        int res = 0;
        List<Integer> counts = new ArrayList<>();
        while (ptr < len) {
            char c = s.charAt(ptr);
            int count = 0;
            while (ptr < len && c == s.charAt(ptr)) {
                count += 1;
                ptr += 1;
            }
            counts.add(count);
        }
        for (int i = 0; i< counts.size() - 1; i++) {
            res += Math.min(counts.get(i), counts.get(i + 1));
        }
        return res;
    }
}

对于某一个位置 i，其实我们只关心 i - 1 位置的 counts 值是多少，所以可以用一个 last 变量来维护当前位置的前一个位置的 counts 值，这样可以省去 counts 数组的空间，也可以省去最后重复访问 counts 数组计算 res 值的时间，优化代码运行的时间效率和空间效率

class Solution {
    public int countBinarySubstrings(String s) {
        int len = s.length();
        int ptr = 0;
        int res = 0;
        int last = 0;
        while (ptr < len) {
            char c = s.charAt(ptr);
            int count = 0;
            while (ptr < len && c == s.charAt(ptr)) {
                count += 1;
                ptr += 1;
            }
            res += Math.min(count, last);
            last = count;
        }
        return res;
    }
}