跳转至

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' 。

解法

方法一：统计 010 和 101 的出现次数

有效方案只有两种情况：$010$ 和 $101$。枚举中间数字，累计方案数。

时间复杂度 $O(n)$，其中 $n$ 表示 $s$ 的长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def numberOfWays(self, s: str) -> int:
        n = len(s)
        cnt0 = s.count("0")
        cnt1 = n - cnt0
        c0 = c1 = 0
        ans = 0
        for c in s:
            if c == "0":
                ans += c1 * (cnt1 - c1)
                c0 += 1
            else:
                ans += c0 * (cnt0 - c0)
                c1 += 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public long numberOfWays(String s) {
        int n = s.length();
        int cnt0 = 0;
        for (char c : s.toCharArray()) {
            if (c == '0') {
                ++cnt0;
            }
        }
        int cnt1 = n - cnt0;
        long ans = 0;
        int c0 = 0, c1 = 0;
        for (char c : s.toCharArray()) {
            if (c == '0') {
                ans += c1 * (cnt1 - c1);
                ++c0;
            } else {
                ans += c0 * (cnt0 - c0);
                ++c1;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    long long numberOfWays(string s) {
        int n = s.size();
        int cnt0 = 0;
        for (char& c : s) cnt0 += c == '0';
        int cnt1 = n - cnt0;
        int c0 = 0, c1 = 0;
        long long ans = 0;
        for (char& c : s) {
            if (c == '0') {
                ans += c1 * (cnt1 - c1);
                ++c0;
            } else {
                ans += c0 * (cnt0 - c0);
                ++c1;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
func numberOfWays(s string) int64 {
    n := len(s)
    cnt0 := strings.Count(s, "0")
    cnt1 := n - cnt0
    c0, c1 := 0, 0
    ans := 0
    for _, c := range s {
        if c == '0' {
            ans += c1 * (cnt1 - c1)
            c0++
        } else {
            ans += c0 * (cnt0 - c0)
            c1++
        }
    }
    return int64(ans)
}

评论