首页 > 试题广场 >

病毒检测

[编程题]病毒检测
  • 热度指数：3065 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
小明最近在做病毒自动检测，他发现，在某些library 的代码段的二进制表示中，如果包含子串并且恰好有k个1，就有可能有潜在的病毒。library的二进制表示可能很大，并且子串可能很多，人工分析不可能，于是他想写个程序来先算算到底有多少个子串满足条件。如果子串内容相同，但是开始或者结束位置不一样，则被认为是不同的子串。
注：子串一定是连续的。例如"010"有6个子串，分别是 "0, "1", "0", "01", "10", "010"


输入描述:
第一行是一个整数k，表示子串中有k个1就有可能是病毒。其中 0 <= k <= 1 000 000

第二行是一个字符串，就是library的代码部分的二进制表示。字符串长度 <= 1 000 000。并且字符串中只包含"0"或"1".


输出描述:
输出一个整数，所有满足只包含k个1的子串的个数。
示例1

输入

1
1010

输出

6

说明

满足条件的子串有："1", "1", "10", "01", "10", "010".
示例2

输入

2
01010

输出

4

说明

满足条件的子串有： "101", "0101", "1010", "01010".
示例3

输入

100
01010

输出

0
算法知识视频讲解
开通博客
头像 offers++
发表于 2020-03-13 21:43:29
借助HashMap记录之前的数之和时间复杂度：o(n) 空间复杂度：o(n) import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc=new Scann 展开全文
去ta的博客 赞 (8) 回复(4) 收起

问题信息

C++工程师 快手 2020 Java工程师
上传者：小小
难度：
16条回答 6552浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号