说在前面
🎈不知道大家对于算法的学习是一个怎样的心态呢?为了面试还是因为兴趣?不管是出于什么原因,算法学习需要持续保持。
题目描述
给你一个下标从 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' 。
思路分析
题目要求我们计算可以选择3栋建筑的有效方案数,由题意可以得出满足题意的建筑形式只有两种,分别是 010 和 101,那么我们只需要计算出字符串中含有这两个子串的数量即可。
以示例1001101
为例,我们来看看计算过程是怎样的。
1、计算010子串数量
我们可以维护三个变量,分别记录当前位置可以构成子串 ‘0’,‘01’和’010’ 的数量。
- 计算’0’子串
'0’子串即为0的数量,遇到’0’的时候加一即可; - 计算’01’子串
'01’子串数量取决于前面’0’的数量,遇到’1’的时候加上前面’0’的数量即可; - 计算’010’子串
'010’子串数量取决于前面’01’子串的数量,遇到’0’的时候加上前面’01’子串的数量即可。
计算过程如下图:
2、计算101子串数量
101子串数量的计算方式与010子串数量的计算方式是一样的。
我们可以维护三个变量,分别记录当前位置可以构成子串 ‘1’,‘10’和’101’ 的数量。
- 计算’1’子串
'1’子串即为0的数量,遇到’1’的时候加一即可; - 计算’10’子串
'10’子串数量取决于前面’1’的数量,遇到’0’的时候加上前面’1’的数量即可; - 计算’101’子串
'101’子串数量取决于前面’10’子串的数量,遇到’1’的时候加上前面’10’子串的数量即可。
计算过程如下图:
AC代码
/** * @param {string} s * @return {number} */ var numberOfWays = function (s) { let f = function (s, t) { let a = 0, b = 0, c = 0; for (let i = 0; i < s.length; i++) { x = s[i]; if (x == t[2]) c += b; if (x == t[1]) b += a; if (x == t[0]) a += 1; } return c; }; return f(s, "101") + f(s, "010"); };
公众号
关注公众号『前端也能这么有趣
』,获取更多有趣内容。
说在后面
🎉 这里是 JYeontu,现在是一名前端工程师,有空会刷刷算法题,平时喜欢打羽毛球 🏸 ,平时也喜欢写些东西,既为自己记录 📋,也希望可以对大家有那么一丢丢的帮助,写的不好望多多谅解 🙇,写错的地方望指出,定会认真改进 😊,偶尔也会在自己的公众号『
前端也能这么有趣
』发一些比较有趣的文章,有兴趣的也可以关注下。在此谢谢大家的支持,我们下文再见 🙌。