当前位置：首页 > news >正文

【C++前缀和】2222. 选择建筑的方案数|1656

news 2024/9/20 9:28:59

本文涉及的基础知识点

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);}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功