选择建筑的方案数

说在前面

🎈不知道大家对于算法的学习是一个怎样的心态呢？为了面试还是因为兴趣？不管是出于什么原因，算法学习需要持续保持。

题目描述

给你一个下标从 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，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打羽毛球 🏸 ，平时也喜欢写些东西，既为自己记录 📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解 🙇，写错的地方望指出，定会认真改进 😊，偶尔也会在自己的公众号『前端也能这么有趣』发一些比较有趣的文章，有兴趣的也可以关注下。在此谢谢大家的支持，我们下文再见 🙌。