当前位置:网站首页>1375. 二进制字符串前缀一致的次数-前序遍历法
1375. 二进制字符串前缀一致的次数-前序遍历法
2022-08-04 13:49:00 【Mr Gao】
1375. 二进制字符串前缀一致的次数
给你一个长度为 n 、下标从 1 开始的二进制字符串,所有位最开始都是 0 。我们会按步翻转该二进制字符串的所有位(即,将 0 变为 1)。
给你一个下标从 1 开始的整数数组 flips ,其中 flips[i] 表示对应下标 i 的位将会在第 i 步翻转。
二进制字符串 前缀一致 需满足:在第 i 步之后,在 闭 区间 [1, i] 内的所有位都是 1 ,而其他位都是 0 。
返回二进制字符串在翻转过程中 前缀一致 的次数。
示例 1:
输入:flips = [3,2,4,1,5]
输出:2
解释:二进制字符串最开始是 “00000” 。
执行第 1 步:字符串变为 “00100” ,不属于前缀一致的情况。
执行第 2 步:字符串变为 “01100” ,不属于前缀一致的情况。
执行第 3 步:字符串变为 “01110” ,不属于前缀一致的情况。
执行第 4 步:字符串变为 “11110” ,属于前缀一致的情况。
执行第 5 步:字符串变为 “11111” ,属于前缀一致的情况。
在翻转过程中,前缀一致的次数为 2 ,所以返回 2 。
示例 2:
输入:flips = [4,1,2,3]
输出:1
解释:二进制字符串最开始是 “0000” 。
执行第 1 步:字符串变为 “0001” ,不属于前缀一致的情况。
执行第 2 步:字符串变为 “1001” ,不属于前缀一致的情况。
执行第 3 步:字符串变为 “1101” ,不属于前缀一致的情况。
执行第 4 步:字符串变为 “1111” ,属于前缀一致的情况。
在翻转过程中,前缀一致的次数为 1 ,所以返回 1 。
这题看似很复杂,千万要理解解题原理,不然暴力去求解,会花费很多时间:
int numTimesAllBlue(int* flips, int flipsSize){
int max=flips[0];
int count=0;
if(flips[0]==1){
count++;
}
for(int i=1;i<flipsSize;i++){
if(flips[i]>max){
max=flips[i];
}
if(max==i+1){
count++;
}
}
return count;
}
边栏推荐
猜你喜欢
第六届未来网络发展大会,即将开幕!
秋招攻略秘籍,吃透25个技术栈Offer拿到手软
封装、继承、多态的联合使用实现不同等级学生分数信息的统计
LeetCode 1403 Minimum subsequence in non-increasing order [greedy] HERODING's LeetCode road
新 Nsight Graph、Nsight Aftermath 版本中的性能提升和增强功能
干掉visio,这个画图神器真的绝了
电子行业MES管理系统有哪些特殊功能
"C pitfalls and pitfalls" reading summary
MySQL性能指标TPS\QPS\IOPS如何压测?
Fuse bit of AVR study notes
随机推荐
智能电视可以打开小程序应用,再也不用头痛内存了
[Niu Ke brush questions-SQL big factory interview questions] NO5. Analysis of a treasure store (e-commerce model)
面试官:说一下NIO和BIO的区别
并发刺客(False Sharing)——并发程序的隐藏杀手
面试官:如何查看/etc目录下包含abc字符串的文件?
Win11快速助手在哪里?Win11打开快速助手的方法
文盘Rust -- 配置文件解析
如何查找endnote文献中pdf文件的位置
错误 AttributeError type object 'Callable' has no attribute '_abc_registry' 解决方案
zabbix自定义图形
(记录)异步并发,多线程处理表的统计
国家安全机关对涉嫌危害国家安全犯罪嫌疑人杨智渊实施刑事拘传审查
Haproxy搭建web群集
LeetCode 1403 非递增顺序的最小子序列[贪心] HERODING的LeetCode之路
SLAM 05.视觉里程计-2-特征法
npm install出现的各种问题
router---mode
JSX使用
阿里老鸟终于把测试用例怎么写说的明明白白了,小鸟必看
js深拷贝和浅拷贝具体使用区别_es6深拷贝和浅拷贝