跳转至

2222. 选择建筑的方案数

题目描述

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

  • s[i] = '0' 表示第 i 栋建筑是一栋办公楼，
  • s[i] = '1' 表示第 i 栋建筑是一间餐厅。

作为市政厅的官员，你需要随机 选择 3 栋建筑。然而，为了确保多样性，选出来的 3 栋建筑 相邻 的两栋不能是同一类型。

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

请你返回可以选择 3 栋建筑的 有效方案数 。

 

示例 1：

输入：s = "001101"
输出：6
解释：
以下下标集合是合法的：
- [0,2,4] ，从 "001101" 得到 "010"
- [0,3,4] ，从 "001101" 得到 "010"
- [1,2,4] ，从 "001101" 得到 "010"
- [1,3,4] ，从 "001101" 得到 "010"
- [2,4,5] ，从 "001101" 得到 "101"
- [3,4,5] ，从 "001101" 得到 "101"
没有别的合法选择，所以总共有 6 种方法。

示例 2：

输入：s = "11100"
输出：0
解释：没有任何符合题意的选择。

 

提示：

  • 3 <= s.length <= 105
  • s[i] 要么是 '0' ，要么是 '1' 。

解法

方法一：计数 + 枚举

思考

要从 \(01\) 串中选三个位置，相邻所选不能同色，即子序列只能是 \(010\) 或 \(101\)。\(n \le 10^5\)，枚举三元组不可行。固定中间那一座楼后，左右必须都是相反颜色，方案数等于左侧相反色个数乘右侧相反色个数。

先统计全串两种颜色的个数作为右侧计数 \(r\)，再从左扫描：经过 \(x\) 前先从 \(r\) 中去掉它，把 \(l[x\oplus 1]\times r[x\oplus 1]\) 加入答案，再把 \(x\) 计入左侧。线性即可。

根据题目描述，我们需要选择 \(3\) 栋建筑，且相邻的两栋不能是同一类型。

我们可以枚举中间的建筑，假设为 \(x\)，那么左右两边的建筑类型只能是 \(x \oplus 1\)，其中 \(\oplus\) 表示异或运算。因此，我们可以使用两个数组 \(l\) 和 \(r\) 分别记录左右两边的建筑类型的数量，然后枚举中间的建筑，计算答案即可。

时间复杂度 \(O(n)\)，其中 \(n\) 是字符串 \(s\) 的长度。空间复杂度 \(O(1)\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def numberOfWays(self, s: str) -> int:
        l = [0, 0]
        r = [s.count("0"), s.count("1")]
        ans = 0
        for x in map(int, s):
            r[x] -= 1
            ans += l[x ^ 1] * r[x ^ 1]
            l[x] += 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
    public long numberOfWays(String s) {
        int n = s.length();
        int[] l = new int[2];
        int[] r = new int[2];
        for (int i = 0; i < n; ++i) {
            r[s.charAt(i) - '0']++;
        }
        long ans = 0;
        for (int i = 0; i < n; ++i) {
            int x = s.charAt(i) - '0';
            r[x]--;
            ans += 1L * l[x ^ 1] * r[x ^ 1];
            l[x]++;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    long long numberOfWays(string s) {
        int n = s.size();
        int l[2]{};
        int r[2]{};
        r[0] = ranges::count(s, '0');
        r[1] = n - r[0];
        long long ans = 0;
        for (int i = 0; i < n; ++i) {
            int x = s[i] - '0';
            r[x]--;
            ans += 1LL * l[x ^ 1] * r[x ^ 1];
            l[x]++;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
func numberOfWays(s string) (ans int64) {
    n := len(s)
    l := [2]int{}
    r := [2]int{}
    r[0] = strings.Count(s, "0")
    r[1] = n - r[0]
    for _, c := range s {
        x := int(c - '0')
        r[x]--
        ans += int64(l[x^1] * r[x^1])
        l[x]++
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function numberOfWays(s: string): number {
    const n = s.length;
    const l: number[] = [0, 0];
    const r: number[] = [s.split('').filter(c => c === '0').length, 0];
    r[1] = n - r[0];
    let ans: number = 0;
    for (const c of s) {
        const x = c === '0' ? 0 : 1;
        r[x]--;
        ans += l[x ^ 1] * r[x ^ 1];
        l[x]++;
    }
    return ans;
}

评论