题目链接

关键词

  • 贪心
  • 归纳

解析

  • 预置知识:十进制数的二进制表示中,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
    • 构建出变换后的字符串
  • 对于不能进行变化的情况,直接返回原字符串

代码

Leetcode1026. 节点与其祖先之间的最大差值Docker容器迁移
Loading...