算法筆試模拟題精解之“一的個數”

線上程式設計介紹

阿裡雲開發者社群線上程式設計産品，針對廣大開發者學習、實踐、面試、應聘、考試認證等打造的免費線上刷題神器。題庫來自筆試模拟題、算法大賽模拟題等，界面整潔明了，操作簡單，為使用者營造專心答題的學習環境。點選連結開始體驗：

https://developer.aliyun.com/coding

本文為大家介紹其中的 第68題：一的個數 的題目解析，具體如下：

題目描述

題目等級：容易

知識點：位運算、貪心

檢視題目：一的個數

給你兩個數字l、r，問在區間[l,r]内的所有數中，二進制表示下“1”的個數最多的一個數是多少，如果有多個相同的，輸出所有符合條件的數中最小的一個數。

輸入一個整數l,和一個整數r。(1<=l<=r<=10^9)

輸出一個數字表示[l,r]内二進制下“1”的個數最多的數。如果有多個，輸出符合條件的數中最小的。

示例1

輸入：

5

10

輸出：

7

解題思路：二進制

根據題意，本題的所有數字應從二進制角度考慮。

所求數字可分為兩部分，高位部分和低位部分，高位部分的值等于l, r高位相等的部分，在區間[l,r]中的所有數的高位部分都應該與其相等，即

high = r & (-1<<count)

，其中 count 為

l^r

的二進制的位數。

低位的部分計算過程如下：

如果 r-high 的值的二進制全為1，則低位部分為 r-high。如果不是全為1，則低位部分為

( 1<<(count-1) ) - 1

時間複雜度：O(log_2 n)

空間複雜度：O(1)

看完之後是不是有了想法了呢，快來練練手吧>>