国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

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

SQC / 1126人閱讀

摘要：長(zhǎng)話短說(shuō)，讓我們來(lái)看一道題統(tǒng)計(jì)的個(gè)數(shù)給定一個(gè)非負(fù)整數(shù)，對(duì)于任意，，計(jì)算的值對(duì)應(yīng)的二進(jìn)制數(shù)中的個(gè)數(shù)，將這些結(jié)果返回為一個(gè)數(shù)組。第二版本的時(shí)間復(fù)雜度是最后版本的時(shí)間復(fù)雜度是，是的二進(jìn)制數(shù)中的的個(gè)數(shù)，介于之間。

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

長(zhǎng)話短說(shuō)，讓我們來(lái)看一道題：

統(tǒng)計(jì)“1”的個(gè)數(shù)

給定一個(gè)非負(fù)整數(shù)num，對(duì)于任意i，0 ≤ i ≤ num，計(jì)算i的值對(duì)應(yīng)的二進(jìn)制數(shù)中“1” 的個(gè)數(shù)，將這些結(jié)果返回為一個(gè)數(shù)組。

例如：

當(dāng)num = 5時(shí)，返回值為[0,1,1,2,1,2]。

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

這道題咋一看還挺簡(jiǎn)單的，無(wú)非是：

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

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

JavaScript中，計(jì)算countBit可以取巧：

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

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

然后，我們寫(xiě)一下完整的程序：

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;
}

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

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

我們說(shuō)，求一個(gè)整數(shù)的二進(jìn)制表示中“1”的個(gè)數(shù)，最普通的當(dāng)然是一個(gè)O(logN) 的方法：

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

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

更快的countBit

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

有一個(gè)訣竅，是基于以下一個(gè)定律：

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

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

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

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

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

于是，我們有了一個(gè)更快的算法：

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)化到了這個(gè)程度，是不是一切都結(jié)束了呢？從算法上來(lái)說(shuō)似乎已經(jīng)是極致了？真的嗎？再給大家 30 秒時(shí)間思考一下，然后再往下看。

countBits的時(shí)間復(fù)雜度

考慮countBits， 上面的算法：

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

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

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

上面三個(gè)版本的countBits的時(shí)間復(fù)雜度都大于O(N)。那么有沒(méi)有時(shí)間復(fù)雜度O(N)的算法呢？

實(shí)際上，最后版本已經(jīng)為我們提示了答案，答案就在上面的那個(gè)定律里，我把那個(gè)等式再寫(xiě)一遍：

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

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

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

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

原來(lái)就這么簡(jiǎn)單，你想到了嗎 ╮(╯▽╰)╭

以上就是所有的內(nèi)容，簡(jiǎn)單的題目思考起來(lái)很有意思吧？程序員就應(yīng)該追求完美的算法，不是嗎？

轉(zhuǎn)載整理自：http://web.jobbole.com

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.specialneedsforspecialkids.com/yun/79626.html

相關(guān)文章

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

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

    xcc3641 評(píng)論0 收藏0

  • 前端思考 - 收藏集 - 掘金

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

    LinkedME2016 評(píng)論0 收藏0

  • 常見(jiàn)大數(shù)據(jù)和空間面試題

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

    Hydrogen 評(píng)論0 收藏0

  • 【面試被虐】如何只用2GB內(nèi)存從20億，40億，80億個(gè)整數(shù)中找到出現(xiàn)次數(shù)最多的數(shù)？

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

    468122151 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<