题目链接
关键词
- 贪心
- 归纳
解析
- 预置知识:十进制数的二进制表示中,1最早出现的位数越高,其数越大
- 可进行的操作:
- 00 → 10
- 10 → 01
- 根据两个可以进行的操作,要使的变化后的数字最大化,一定要使原字符串中的0,尽可能替换为1,且1的位置要尽量在高位
- 对于字符串str,如果str中
- 没有0,则变化后的字符串就是自身→此时无法变化
- 有一个0,则变化后的字符串就是自身→因为涉及一个0参与的操作,只能从10变为01,反而会变小
- 有两个及以上的0,变化后的字符串只有一个0
- 对于相邻的0,可以变化为10
- 对于非相邻的0,可以利用操作二,借助其前面的1,变为01,实现将0往前移动的操作,然后一直重复该操作,直到有两个0相邻,此时可以变为10,从而减少了0的个数
- 根据上面的分析,最后答案中,只会有一个0,且其出现的位置,与字符串str中出现的0的次数有关,由于00→10,可以发现,每减少一个0,0出现的位置就会往后移动一位
- 问题可以分四步解决:
- 找出0第一次出现的位置index
- 计算出0出现的次数cnt
- 计算出0的偏移量:index+cnt-1
- 构建出变换后的字符串
- 对于不能进行变化的情况,直接返回原字符串
代码
- Author:CoderWdd
- URL:https://www.wuinsights.top//article/01HV44Y3ZFDM3W080KMJKYMF4P
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
Relate Posts
