2222-选择建筑的方案数

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:28 2023-09-13 16:06:28 Updated    

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

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

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

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

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

示例 1：

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

示例 2：

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

提示：

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

方法一：枚举中间元素

思路与算法

由于不允许相邻被选择建筑是同一类型，因此选择的长度为 3 子序列只可能有两种情况，即 “010” 与 “101”，那么有效方案数即为字符串 s 中子序列 “010” 与 “101” 的种类数之和。

我们不妨以子序列 “101” 为例，为了计算该子序列的种类数，我们可以遍历字符串 s 枚举子序列的中间元素（此处为 `1’）。

为了表达方便，我们用 n 表示字符串 s 的长度，并用 cnt}_1(i, j) 表示子串 s[i..j]（包含两端）中 1' 的个数。具体地，如果 s 中下标为 i 的元素 s[i] 为 1’，那么由该字符为中间元素组成的 “101” 子序列个数即为 cnt}_1(0, i - 1) \times \textit{cnt}_1(i + 1, n - 1)。

如果我们对于每一个符合要求的下标都通过遍历暴力计算 cnt}_1(0, i - 1) 以及 cnt}_1(i + 1, n - 1)，那么每一次计算的时间复杂度即为 O(n)，总复杂度不符合数据范围要求，因此我们需要对上式的计算进行一定的优化。

由于我们在枚举中间元素时是按照下标顺序对 s 进行遍历，因此在遍历的过程中，我们可以用 cnt 来维护 [0, i - 1] 闭区间内 1' 的个数，即 cnt}_1(0, i - 1)；而如果我们**事先遍历** s 计算出 s 中 1’ 的总个数 n}_1，那么就有 cnt}_1(i + 1, n - 1) = n_1 - \textit{cnt（由于 s[i] **一定为 `0’**）。即由 s[i] 为中间元素组成的 “101” 子序列个数为：

\textit{cnt} \times (n_1 - \textit{cnt}).

我们可以在遍历中间元素的下标时，维护 cnt，并使用 res 维护 “101” 的种类数总和，即对于所有元素为 `0’ 的下标，我们计算上式并将对应的数值加在 res 上即可。

类似地，我们也可以在遍历字符串的同时计算 “010” 的种类数总和并同样加在 res 上。具体地，当遍历到 `1’ 时，我们计算以该下标 i 为中间元素时 “010” 的种类数总和：

(i - \textit{cnt}) \times ((n - n_1) - (i - \textit{cnt})).

其中乘号左边代表 [0, i - 1] 闭区间内 0' 的个数，右边代表 [i + 1, n - 1] **闭区间**内 0’ 的个数。

综上所述，我们需要首先遍历一遍字符串 s 计算出 s 中 1' 的总个数 n}_1，随后**再次遍历**字符串，按照上文的方式维护已经遍历过 1’ 的个数 cnt 与符合要求子串种数总和 res。当遍历完成后，我们返回 res 即可。

细节

对于 C++ 等语言，在计算上面两个中间值时，数值有可能超过 32 位有符号整数的上界，因此我们需要在乘法操作前将任一乘数转化为 64 位整数。

代码

[sol1-C++]
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 n1 = count(s.begin(), s.end(), '1');   // s 中 '1' 的个数
        long long res = 0;   // 两种子序列的个数总和
        int cnt = 0;   // 遍历到目前为止 '1' 的个数
        for (int i = 0; i < n; ++i) {
            if (s[i] == '1') {
                res += (long long) (i - cnt) * (n - n1 - i + cnt);
                ++cnt;
            } else {
                res += (long long) cnt * (n1 - cnt);
            }
        }
        return res;
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def numberOfWays(self, s: str) -> int:
        n = len(s)
        n1 = s.count('1')   # s 中 '1' 的个数
        res = 0   # 两种子序列的个数总和
        cnt = 0   # 遍历到目前为止 '1' 的个数
        for i in range(n):
            if s[i] == '1':
                res += (i - cnt) * (n - n1 - i + cnt)
                cnt += 1
            else:
                res += cnt * (n1 - cnt)
        return res

复杂度分析

  • 时间复杂度：O(n)，其中 n 为字符串 s 的长度，即为遍历计算字符串中 1 的数量以及计算方案总数的时间复杂度。

  • 空间复杂度：O(1)。

 Comments
On this page
2222-选择建筑的方案数