本文涉及的基础知识点

C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频

LeetCode2222. 选择建筑的方案数

难度分：1656
给你一个下标从 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 <= 10⁵
  s[i] 要么是 ‘0’ ，要么是 ‘1’ 。

C++前缀和

只有两种选法：010 和101。
preSum[0][i]记录前i间建筑中为0的数量，preSum[1][i]记录前i间建筑物中1的数量。
从小到大枚举i$\in$[1,n-1)
如果nums[i]是1：
nums[0…i)中0的数量 $\times$ nums[i+1,…]中0的数量
如果nums[i]是0:
nums[0…i)中1的数量 $\times$ nums[i+1,…]中1的数量

代码

核心代码

	class Solution {
		public:
			long long numberOfWays(string s) {
				vector<vector<long long>> preSum(2,vector<long long>(1));
				for (const auto& ch : s) {
					preSum[0].emplace_back(preSum[0].back() + ('0' == ch));
					preSum[1].emplace_back(preSum[1].back() + ('1' == ch));
				}
				long long ret = 0;
				for (int i = 1; i + 1 < s.length(); i++) {
					const auto& ps = preSum['0' == s[i]];					
					ret += ps[i] * (ps.back() - ps[i + 1]);
				}
				return ret;
			}
		};

单元测试

string s;
		TEST_METHOD(TestMethod11)
		{
			s = "001101";
			auto res = Solution().numberOfWays(s);
			AssertEx(6LL, res);
		}
		TEST_METHOD(TestMethod12)
		{
			s = "11100";
			auto res = Solution().numberOfWays(s);
			AssertEx(0LL, res);
		}