当前位置:网站首页>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;
}
边栏推荐
猜你喜欢
新 Nsight Graph、Nsight Aftermath 版本中的性能提升和增强功能
Win11勒索软件防护怎么打开?Win11安全中心勒索软件防护如何设置
南瓜科学产品升级 开启益智探索新篇章
按键控制开关4017芯片数字电路
职场漫谈:为什么越是内卷的行业越有人争着抢着往里冲?好奇怪的说...
面试官:如何查看/etc目录下包含abc字符串的文件?
State security organs conduct criminal arrest and summons review on Yang Zhiyuan, a suspect suspected of endangering national security
《社会企业开展应聘文职人员培训规范》团体标准在新华书店上架
用过Apifox这个API接口工具后,确实感觉postman有点鸡肋......
AutoCAD DWG,DXF文件导出高清图片、PDF
随机推荐
橄榄枝大课堂APP正式启动上线
Utility function---string processing
(记录)异步并发,多线程处理表的统计
《社会企业开展应聘文职人员培训规范》团体标准在新华书店上架
项目里的各种配置,你都了解吗?
从理论到实践:MySQL性能优化和高可用架构,一次讲清
开发者独立搭建一个跨模态搜索应用有多难?
国家安全机关对涉嫌危害国家安全犯罪嫌疑人杨智渊实施刑事拘传审查
php中的ceil和floo以及round函数「建议收藏」
【无标题】
C# 复制列表
router---模式
人像分割技术解析与应用
AVR学习笔记之熔丝位
错误 AttributeError type object 'Callable' has no attribute '_abc_registry' 解决方案
卷积神经网络 基础
大势所趋之下的nft拍卖,未来艺术品的新赋能
Analysis and application of portrait segmentation technology
sqlplus报错ORA-12547: TNS:lost contact解决
如何才能有效、高效阅读?猿辅导建议“因材因时施教”