68.一的个数 - 图1

题目概述

题目详情(点我)

给你两个数字l、r，问在区间[l,r]内的所有数中，二进制表示下“1”的个数最多的一个数是多少，如果有多个相同的，输出所有符合条件的数中最小的一个数。
输入一个整数l,和一个整数r。(1<=l<=r<=10^9)

输入:
输出一个数字表示[l,r]内二进制下“1”的个数最多的数。

输出:
如果有多个，输出符合条件的数中最小的。

题解

解题方法

  • 暴力解法(超时)
  • 找规律

算法知识

  • 二进制

    • 时间复杂度: n
    • 空间复杂度: 1

解题思路

审题

  • int l, r : 左右区间

题目要求

  • 再区间l, r内找到一个数, 这个数的二进制1最多
    如果一样多就取最小的

思路

  • 为了避免重复计算 2^i次方, 耗时太多
    所以直接使用一个for循环将230都求出来, 并存到数组内

  • 判断l, r包含的范围是否跨越多个2的幂次方
    如:
    2^1的范围为[1, 2]
    2^2的范围为[2, 4]
    2^3的范围为[4, 8]

    • 若跨了多个范围, 则取r在内的范围和r的范围的前一个范围
      如果r不是全为1，则最多1的个数的值为前一个范围的最大值-1
      如果r为当前范围的最大值-1, 则r为最多1的值
  • 如果l, r 在同一个范围内, 则从这个范围的最小值开始, 不断添加2^i(i >= 0) 直到这个值 + 2^i 大于r为止, 此时该值便为最小的最多1的值。

步骤

  1. 定义变量

    • int[] arr : 存储2^i次方, 数组大小32
    • int temp : 存储当前值

  2. 计算230, 存入数组内, 并计算r所在的范围arr[i]

  3. 判断l和r是否在同一个范围内, 返回最多i的数

    • 若不是且r不是当前范围最大值, 则直接返回arr[i-1]-1

    • 如果是, 则将arr[i-1]为最小值赋值给temp, 开始遍历数组arr

      • 将最小值temp + arr[i] 直到大于r时停止, 这样就算出了最大值
  4. 将最大值返回

  • 原因:

    • 在2^2, 2^3这两个范围内, 1最多的数为2^3-1, 有三个1. 其次为2^2-1, 有两个1。所以在不同范围内且最大范围内的最大值不为范围内的最大值-1, 则最小且最多1的数即为前一个范围内的最大值-1

    • 在同一个范围, 即这个范围内的所有值的最高位均为1, 其余位均不确定, 而此时, 只要给这个范围内的最小值依次添加上2^i, 直到添加后大于r, 就可以得到最小且最多1的值了。