[LeetCode] 2222. Number of Ways to Select Buildings

You are given a 0-indexed binary string s which represents the types of buildings along a street where:

• s[i] = '0' denotes that the ith building is an office and
• s[i] = '1' denotes that the ith building is a restaurant.

As a city official, you would like to select 3 buildings for random inspection. However, to ensure variety, no two consecutive buildings out of the selected buildings can be of the same type.

• For example, given s = "001101", we cannot select the 1st, 3rd, and 5th buildings as that would form "011" which is not allowed due to having two consecutive buildings of the same type.

Return the number of valid ways to select 3 buildings. 

Example 1:

Input: s = "001101"
Output: 6
Explanation: 
The following sets of indices selected are valid:
- [0,2,4] from "001101" forms "010"
- [0,3,4] from "001101" forms "010"
- [1,2,4] from "001101" forms "010"
- [1,3,4] from "001101" forms "010"
- [2,4,5] from "001101" forms "101"
- [3,4,5] from "001101" forms "101"
No other selection is valid. Thus, there are 6 total ways.

Example 2:

Input: s = "11100"
Output: 0
Explanation: It can be shown that there are no valid selections.

Constraints:

• 3 <= s.length <= 105
• s[i] is either '0' or '1'.

选择建筑的方案数。

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/number-of-ways-to-select-buildings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路是动态规划。把题意精简一下，其实题目是让你求 input 字符串里有多少类型为 101 或者 010 这样的子序列。这里我选择用几个变量记录 0,1,10,01 的出现次数。遍历字符串，当我们遇到的是 0，我们除了要统计 0 的个数之外，我们要看看之前我们统计了多少个 01，这样我们就知道有多少 010 可以被累加到最后的结果。同理，如果我们遇到的是 1，除了要统计 1 的出现次数以外，我们也要统计之前出现的 10 的次数，这样我们就知道有多少 101 可以被累加到最后的结果。

时间O(n)

空间O(1)

Java实现

 1 class Solution {
 2     public long numberOfWays(String s) {
 3         long res = 0, one = 0, zero = 0, oneZero = 0, zeroOne = 0;
 4         for (int i = 0; i < s.length(); i++) {
 5             char c = s.charAt(i);
 6             // 如果当前是0
 7             if (c == '0') {
 8                 zero++;
 9                 oneZero += one;        // 看看10这种前缀有多少，也就是看看目前找到的1有多少
10                 res += zeroOne;        // 看看01这种前缀有多少，也就是看看010这种答案有多少
11             }
12             // 如果当前是1
13             else {
14                 one++;
15                 zeroOne += zero;    // 看看01这种前缀有多少，也就是看看目前找到的0有多少
16                 res += oneZero;        // 看看10这种前缀有多少，也就是看看101这种答案有多少
17             }
18         }
19         return res;
20     }
21 }

LeetCode 题目总结