[数据结构与算法]0数组中等 LeetCode6035. 选择建筑的方案数

6035. 选择建筑的方案数

描述

给你一个下标从 0 开始的二进制字符串 s ，它表示一条街沿途的建筑类型，其中：

s[i] = ‘0’ 表示第 i 栋建筑是一栋办公楼，
s[i] = ‘1’ 表示第 i 栋建筑是一间餐厅。
作为市政厅的官员，你需要随机 选择 3 栋建筑。然而，为了确保多样性，选出来的 3 栋建筑 相邻 的两栋不能是同一类型。

比方说，给你 s = “001101” ，我们不能选择第 1 ，3 和 5 栋建筑，因为得到的子序列是 “011” ，有相邻两栋建筑是同一类型，所以 不合 题意。
请你返回可以选择 3 栋建筑的 有效方案数 。

分析

以’010’为例，以中间的1为中心分别计算1两边0的个数，相乘便是以这个1为中心的’010’的全部个数，全部的元素都做这样处理可得出’010’,'101’的全部可能个数。

class Solution {
    public long numberOfWays(String s) {
        int n = s.length();
        int[] l = new int[n];
        int[] r = new int[n];
        int zero = 0;
        int one = 0;
        for(int i = 0; i < n; i++){
            char ch = s.charAt(i);
            if(ch == '1'){
                l[i] = zero;
                one++;
            }else{
                l[i] = one;
                zero++;
            }
        }
        zero = 0;
        one = 0;
        for(int i = n - 1; i >= 0; i--){
            char ch = s.charAt(i);
            if(ch == '1'){
                r[i] = zero;
                one++;
            }else{
                r[i] = one;
                zero++;
            }
        }
        long sum = 0;
        for(int i = 0; i < n; i++){
            sum += l[i]*r[i];
        }
        return sum;
    }
}