別人家的面試題：統(tǒng)計“1”的個數(shù)

SQC 發(fā)布于2019-08-19 18:27 / 1117人閱讀

摘要：長話短說，讓我們來看一道題統(tǒng)計的個數(shù)給定一個非負整數(shù)，對于任意，，計算的值對應的二進制數(shù)中的個數(shù)，將這些結果返回為一個數(shù)組。第二版本的時間復雜度是最后版本的時間復雜度是，是的二進制數(shù)中的的個數(shù)，介于之間。

小胡子哥@Barret李靖給我推薦了一個寫算法刷題的地方leetcode.com，沒有ACM那么難，但題目很有趣。而且據(jù)說這些題目都來源于一些公司的面試題。好吧，解解別人公司的面試題其實很好玩，既能整理思路鍛煉能力，又不用擔心漏題 ╮(╯▽╰)╭。

長話短說，讓我們來看一道題：

統(tǒng)計“1”的個數(shù)

給定一個非負整數(shù)num，對于任意i，0 ≤ i ≤ num，計算i的值對應的二進制數(shù)中“1” 的個數(shù)，將這些結果返回為一個數(shù)組。

例如：

當num = 5時，返回值為[0,1,1,2,1,2]。

/** 
  * @param {number} num 
  * @return {number[]} 
  * /
var countBits = function(num) {
    //在此處實現(xiàn)代碼
};

解題思路

這道題咋一看還挺簡單的，無非是：

實現(xiàn)一個方法countBit，對任意非負整數(shù)n，計算它的二進制數(shù)中“1”的個數(shù)

循環(huán)i從0到num，求countBit(i)，將值放在數(shù)組中返回。

JavaScript中，計算countBit可以取巧：

function countBit(n){
    return n.toString(2).replace(/0/g,"").length;
}

上面的代碼里，我們直接對n用toString(2)轉成二進制表示的字符串，然后去掉其中的0，剩下的就是“1”的個數(shù)。

然后，我們寫一下完整的程序：

function countBit(n){
    return n.toString(2).replace(/0/g,"").length;
}
function countBits(nums){
    var ret = [];?? 
    for(var i = 0; i <= nums; i++){
        ret.push(countBit(i));
    }
    return ret;
}

上面這種寫法十分討巧，好處是countBit利用JavaScript語言特性實現(xiàn)得十分簡潔，壞處是如果將來要將它改寫成其他語言的版本，就有可能懵B了，它不是很通用，而且它的性能還取決于Number.prototype.toString(2)和String.prototype.replace的實現(xiàn)。

所以為了追求更好的寫法，我們有必要考慮一下countBit的通用實現(xiàn)法。

我們說，求一個整數(shù)的二進制表示中“1”的個數(shù)，最普通的當然是一個O(logN) 的方法：

function countBit(n){
    var ret = 0;
    while(n > 0){
        ret += n & 1;
        n >>= 1;
    }
    return ret;
}

這么實現(xiàn)也很簡潔不是嗎？但是這么實現(xiàn)是否最優(yōu)？建議此處思考10秒鐘再往下看。

更快的countBit

上一個版本的countBit的時間復雜度已經是O(logN) 了，難道還可以更快嗎？當然是可以的，我們不需要去判斷每一位是不是“1”，也能知道n的二進制中有幾個“1”。

有一個訣竅，是基于以下一個定律：

對于任意 n， n ≥ 1，有如下等式成立：

countBit(n & (n - 1)) === countBit(n) - 1

這個很容易理解，大家只要想一下，對于任意n，n – 1的二進制數(shù)表示正好是n的二進制數(shù)的最末一個“1”退位，因此n & n – 1正好將n的最末一位“1”消去，例如：

6的二進制數(shù)是110，?5 = 6 – 1的二進制數(shù)是101，6 & 5的二進制數(shù)是110 & 101 == 100

88的二進制數(shù)是1011000，87 = 88 – 1的二進制數(shù)是 1010111，88 & 87的二進制數(shù)是1011000 & 1010111 == 1010000

于是，我們有了一個更快的算法：

function countBit(n){
    var ret = 0;
    while(n > 0){
        ret++;
        n &= n - 1;
    }
    return ret;
}
function countBits(nums){
    var ret = [];
    for(var i = 0; i <= nums; i++){
        ret.push(countBit(i));
    }
    return ret;
}

上面的countBit(88)只循環(huán)3次，而上一版本的countBit(88)卻需要循環(huán)7次。

優(yōu)化到了這個程度，是不是一切都結束了呢？從算法上來說似乎已經是極致了？真的嗎？再給大家 30 秒時間思考一下，然后再往下看。

countBits的時間復雜度

考慮countBits，上面的算法：

最初版本的時間復雜度是O(N*M)，M取決于Number.prototype.toString和String.prototype.replace的復雜度。

第二版本的時間復雜度是O(N*logN)

最后版本的時間復雜度是O(N*M)，M是N的二進制數(shù)中的“1”的個數(shù)，介于1 ~ logN之間。

上面三個版本的countBits的時間復雜度都大于O(N)。那么有沒有時間復雜度O(N)的算法呢？

實際上，最后版本已經為我們提示了答案，答案就在上面的那個定律里，我把那個等式再寫一遍：

countBit(n & (n - 1)) === countBit(n) - 1

也就是說，如果我們知道了countBit(n & (n - 1))，那么我們也就知道了countBit(n)！

而我們知道countBit(0)的值是 0，于是，我們可以很簡單的遞推：

function countBits(nums){
    var ret = [0];
    for(var i = 1; i <= nums; i++){
        ret.push(ret[i & i - 1] + 1);
    }
    return ret;
}

原來就這么簡單，你想到了嗎 ╮(╯▽╰)╭

以上就是所有的內容，簡單的題目思考起來很有意思吧？程序員就應該追求完美的算法，不是嗎？

轉載整理自：http://web.jobbole.com

GPU云服務器云服務器別人家的元數(shù)據(jù)系統(tǒng)是怎么設計的 linux的面試題 js的基礎面試題面試題

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/79626.html

全職爸爸，是程序員的加試題

摘要：但周自恒輕描淡寫地說，這是理性分析之后的結果，談不上多艱難。到今年月，是他做全職爸爸的周年。對此，周自恒建議老爸們雖然無法天天陪孩子學習，但是得了解自己孩子思維的發(fā)育特點，在哪方面比較敏感，在孩子的培養(yǎng)方向和計劃上更多地參與進來。 showImg(https://segmentfault.com/img/bVbtYNo); 哥哥：爸爸我問你，有一種鯊魚，它的頭像錘子，是海底的雜食動物，...

xcc3641 2019-07-31 10:35 評論0 收藏0
前端思考 - 收藏集 - 掘金

摘要：并嘗試用為什么你統(tǒng)計的方式是錯的掘金翻譯自工程師的文章。正如你期望的，文中的前端開發(fā)單一職責原則前端掘金單一職責原則又稱單一功能原則，面向對象五個基本原則之一。單頁式應用性能優(yōu)化 - 首屏數(shù)據(jù)漸進式預加載 - 前端 - 掘金前言針對首頁和部分頁面打開速度慢的問題，我們開始對單頁式應用性能進行優(yōu)化。本文介紹其中一個方案：基于 HTTP Chunk 的首屏數(shù)據(jù)漸進式預加載方案，該方案總...

LinkedME2016 2019-08-20 17:19 評論0 收藏0
常見大數(shù)據(jù)和空間面試題

摘要：答案使用，申請一個長度為類型的，每個位置只表示或，該數(shù)組占用空間約。遍歷億個數(shù)，當前數(shù)為，落在區(qū)間，對應。過濾100億黑名單題目假設有100億個URL的黑名單，每個URL最多占用64B，設計一個過濾系統(tǒng)，判斷某條URL是否在黑名單里。要求不高于萬分之一的判斷失誤率；額外內存不超過30GB 答案 100億個64B的URL需要640GB的內存，顯然直接存哈希表不合理。考慮布隆過濾...

Hydrogen 2019-08-15 18:04 評論0 收藏0
【面試被虐】如何只用2GB內存從20億，40億，80億個整數(shù)中找到出現(xiàn)次數(shù)最多的數(shù)？

摘要：這幾天小秋去面試了，不過最近小秋學習了不少和位算法相關文章，例如面試現(xiàn)場如何判斷一個數(shù)是否在億個整數(shù)中算法技巧位運算裝逼指南對于算法題還是有點信心的，，，，于是，發(fā)現(xiàn)了如下對話。這幾天小秋去面試了，不過最近小秋學習了不少和位算法相關文章，例如【面試現(xiàn)場】如何判斷一個數(shù)是否在40億個整數(shù)中？【算法技巧】位運算裝逼指南對于算法題還是有點信心的，，，，于是，發(fā)現(xiàn)了如下對話。 20億級別面試...

468122151 2019-05-27 17:42 評論0 收藏0