笔试算法模拟题精解之“Alice的01串”-阿里云开发者社区

开发者社区> 算法编程> 正文

笔试算法模拟题精解之“Alice的01串”

简介: 根据题意,本题可以直接用双层循环扫描数组,找到所有的连续子串,查看每个组合是否拥有指定数量的1。

【在线编程产品介绍】

阿里云开发者社区在线编程:

免费刷题大神器,助你拿到好offer

周赛月赛不停歇,做题还能领奖品

大赛笔试全真题,常做常新有惊喜

点击链接开始产品体验:https://developer.aliyun.com/coding

本文为大家介绍的是“65.Alice的01串”的解法探究。先来看一下题目内容:

题目描述:

查看题目:Alice的01串 Alice给了Bob一个字符串s,Alice想让Bob找出这个字符串中有多少个恰好包含了k个1的子串。请你帮助Bob计算出这些子串的个数。
输入一个正整数k,表示包含1的个数(0<=k<=10^6)和一个长度不为0的字符串,字符串的长度不超过10^6
输出一个数字,表示s中恰好包含k个1的子串的个数。
示例1
输入:
2
"01010"
输出:
4

方法 1:暴力搜索

根据题意,本题可以直接用双层循环扫描数组,找到所有的连续子串,查看每个组合是否拥有指定数量的 1。搜索可以做适当优化,比如内层循环找到超出 k 个 1 时,可以停止扫描,但本质上时间复杂度上界仍是二次幂。

时间复杂度:O(n^2)

空间复杂度:O(1)

方法 2:暴力搜索的优化,滑窗法

上面暴力法的主要缺陷是,扫描过程中有过多的无用扫描,比如寻找含有 3 个 1 的 01 串,可以在前一个含有 3 个 1 的 01 串的基础上,去掉第 1 个 1,并寻找到下 1 个 1,而不是像暴力解法一样,每次都要从头扫描。

请试图在暴力搜索二重循环的基础上,用几个标识输入串下标的变量,标识当前搜索 01 串的开头和结尾,尽可能减小时间复杂度。如果设计足够耐心的话,此方法可以达到 1 遍扫描解决的效果,但需要的分支判断会比较多。

时间复杂度:O(n)

方法 3:寻找规律

优化本题的关键是设计合理的数据结构,在方法 2 的基础上避免多余的滑窗操作和分支判断,直接利用每个串两侧赘余 0 的个数,用数学方法算出 01 串数量。记录下每个 1 出现的位置和顺序,及各个 1 之间 0 的数量,这样,只要将 k 个 1 的最短 01 串前后 0 的数量做乘积,就得到了所有含 k 个 1 的 01 串的数量,譬如:

输入:
2
"00101010"

将上面的串转化为 map 映射:

这是第几个 1 这个 1 到上一个 1 之间 0 的数量
1 2
2 1
3 1
# 1

首先考察第 1 个 1 和第 2 个 1 组成的最短 01 串:

"00101010"

前后分别有 21 个 0:

"00101010"

重点: 此时可以直接算出,第 1 个 1 和第 2 个 1 组成的 “含 2 个 1 的 01 串” 的数量为:(2+1)*(1+1)=6;用类似的方法继续计算第 2 和第 3 个 1 组成的 01 串数量,加到一起就得到了答案。

将上面的思路转换为代码,大致分为几步:

  • 遍历输入串,用散列表,或者数组,记录下每个 1 到上个 1(也可以记录每个 1 到下个 1)的 0 的个数。
  • 遍历生成的散列表或数组,同时用两个临时变量标识目标 01 串的第一个 1 和最后一个 1 的位置,直接利用他们前/后的 0 的个数做乘积。累加得到结果。

这种解法写代码的思路会相对清晰,相对解法 2 滑窗的分支判断较少。

注意: 计算时,注意需要将间隔的 0 的数量 21 分别 +1 后再彼此相乘,因为最短 01 串两侧分别不包含任何 0,也是一种符合题意的 Alice01 串。

时间复杂度:O(n)
空间复杂度:O(n)

看完之后是不是有了答题思路了呢,快来练练手吧:65.Alice的01串

在线编程周赛、月赛火热进行中,更有限时答题活动,社区定制卫衣、双肩背包等你来拿~每天都有好礼相送~点击了解周赛详情:在线编程内测中,抢先周赛赢好礼!面试考试前,快来刷刷题!

b462f1d86b44481ca24c0ad63fe55948.png

上一篇:笔试算法模拟题精解之“超车”的两种解法
下一篇:笔试算法模拟题精解之“2的幂次方数”

版权声明:本文中所有内容均属于阿里云开发者社区所有,任何媒体、网站或个人未经阿里云开发者社区协议授权不得转载、链接、转贴或以其他方式复制发布/发表。申请授权请邮件developerteam@list.alibaba-inc.com,已获得阿里云开发者社区协议授权的媒体、网站,在转载使用时必须注明"稿件来源:阿里云开发者社区,原文作者姓名",违者本社区将依法追究责任。 如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:developer2020@service.aliyun.com 进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
+ 订阅

开发者社区在线编程频道官方技术圈。包含算法资源更新,周赛动态,每日一题互动。

官方博客
官网链接