选择建筑的方案数

简介: 选择建筑的方案数

说在前面

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

题目描述

给你一个下标从 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栋建筑的有效方案数,由题意可以得出满足题意的建筑形式只有两种,分别是 010101,那么我们只需要计算出字符串中含有这两个子串的数量即可。

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

目录
相关文章
|
2月前
|
安全 UED
再次上演“空间魔法”,方太重新定义水槽洗碗机的能力边界
9月25日,方太在北京品牌超级体验店发布了全新一代水槽洗碗机Y系列,引发广泛关注。这款产品集水槽、洗碗机、果蔬净化机于一体,解决了传统洗碗机安装复杂、空间占用大等问题,尤其适合中国家庭厨房。自2015年推出首代水槽洗碗机以来,方太通过创新设计,如双层可翻转水流清洗系统和自动顶门透气干燥系统,大幅提升用户体验。此次Y系列不仅解决了洗锅难题,还增加了多功能料理台功能,进一步优化了厨房空间利用。方太凭借持续的技术创新和对中国家庭需求的深刻理解,成功引领了洗碗机市场的变革。
|
27天前
|
传感器 监控 物联网
智能水管理:城市水资源的优化分配
【10月更文挑战第9天】在城市化进程中,水资源管理和分配成为关键议题。面对人口增长、工业与农业需求增加导致的资源短缺和污染问题,智能水管理技术应运而生。本文探讨其概念、技术和应用,展示如何通过现代信息技术、物联网、大数据分析及人工智能手段实现水资源的实时监控、精准预测和智能调度,从而提升城市供水系统的安全性与可靠性,促进可持续发展。
|
6月前
[贴装专题] 贴装流程中涉及到的位置关系计算
[贴装专题] 贴装流程中涉及到的位置关系计算
56 0
|
算法 新能源 调度
【二阶锥规划】考虑气电联合需求响应的气电综合能源配网系统协调优化运行【IEEE33节点】(Matlab代码实现)
【二阶锥规划】考虑气电联合需求响应的气电综合能源配网系统协调优化运行【IEEE33节点】(Matlab代码实现)
【二阶锥规划】考虑气电联合需求响应的气电综合能源配网系统协调优化运行【IEEE33节点】(Matlab代码实现)
《城市绿色出行指数白皮书》——3.碳排放计算框架——3.1 交通方式划分
《城市绿色出行指数白皮书》——3.碳排放计算框架——3.1 交通方式划分
191 0
|
SQL 人工智能 安全
把数据中心放到北极圈,也许都没这条绿色计算之路收益高
把数据中心放到北极圈,也许都没这条绿色计算之路收益高
115 0
|
前端开发 API
智慧城市中城市级建筑白膜的加载与动态调色
本文以cesium为例,重点了阐述了在智慧城市场景中,如何基于cesium进行城市级建筑模拟渲染,以及点击展示模型数据的属性信息,支持根据建筑的不同高度来渲染不同的颜色。 cesium支持将城市建筑信息转换成b3dm数据,通过api可进行展示。
2037 0
智慧城市中城市级建筑白膜的加载与动态调色
7-11 分段计算居民水费 (10 分)
7-11 分段计算居民水费 (10 分)
673 0
|
新能源
【资讯】国务院:完善能源消费总量和强度双控制度
健全绿色低碳循环发展的生产体系、健全绿色低碳循环发展的流通体系、健全绿色低碳循环发展的消费体系、加快基础设施绿色升级、构建市场导向的绿色技术创新体系、完善法律法规政策体系和认真抓好组织实施。
【资讯】国务院:完善能源消费总量和强度双控制度
|
存储 边缘计算 运维
数量庞大的电梯设备 阿里云携手西奥电梯为你提供管理思路
阿里云与西奥电梯联合共同打造西奥可信电梯物联网平台,通过工业互联网的规则引擎与阿里云其他云产品打通,实现采集+计算+存储+AI+可信的全栈服务,充分挖掘物联网数据的价值,实现连接到智能的跨越,利用物联网技术,在如今庞大的电梯市场中,实现电梯设备预测性维护、设备全生命周期管理以及提供可信的透明监管和全链路的安全保障。
数量庞大的电梯设备 阿里云携手西奥电梯为你提供管理思路