成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

【刷算法】整數(shù)中1出現(xiàn)的次數(shù)（從1到n整數(shù)中1出現(xiàn)的次數(shù)）

Shisui / 2306人閱讀

摘要：題目描述求出的整數(shù)中出現(xiàn)的次數(shù)并算出的整數(shù)中出現(xiàn)的次數(shù)為此他特別數(shù)了一下中包含的數(shù)字有因此共出現(xiàn)次但是對(duì)于后面問題他就沒轍了。希望你們幫幫他并把問題更加普遍化可以很快的求出任意非負(fù)整數(shù)區(qū)間中出現(xiàn)的次數(shù)從到中出現(xiàn)的次數(shù)。

題目描述

求出1~13的整數(shù)中1出現(xiàn)的次數(shù),并算出100~1300的整數(shù)中1出現(xiàn)的次數(shù)？為此他特別數(shù)了一下1~13中包含1的數(shù)字有1、10、11、12、13因此共出現(xiàn)6次,但是對(duì)于后面問題他就沒轍了。ACMer希望你們幫幫他,并把問題更加普遍化,可以很快的求出任意非負(fù)整數(shù)區(qū)間中1出現(xiàn)的次數(shù)（從1 到 n 中1出現(xiàn)的次數(shù)）。

分析 解法1

從1到n依次遍歷，對(duì)于每一個(gè)數(shù)字都檢查一遍它有幾個(gè)1，然后累加即可，時(shí)間復(fù)雜度是O(N*logN)

解法2

例如103這樣的數(shù)字：

個(gè)位數(shù)是1的有001，011，021，031，041，051，061，071，081，091，101，共11個(gè)

十位數(shù)是1的有010，011，012，013，014，015，016，017，018，019，共10個(gè)

百位數(shù)是1的有100，101，102，103

所以對(duì)于每一位來(lái)說(shuō)，這一位數(shù)字是1的情況是由這一位本身、這一位的所有高位、這一位的所有低位，共同決定的，總結(jié)一下，對(duì)于abXcd來(lái)說(shuō)：

X=0時(shí)，如果ab=01，那么就有00100~00199這100個(gè)數(shù)字都是X位是1的數(shù)字

X=1時(shí)，如果ab=01，那么就有00100~00199這100個(gè)數(shù)字 + ab100~ab1cd這個(gè)cd個(gè)數(shù)字

X>=2時(shí)，如果ab=01，那么就有00100~00199這100個(gè)數(shù)字 + 01100~01199這100個(gè)數(shù)字

其實(shí)這道問題在《編程之美》第134頁(yè)有詳解，看不懂可以看看書。

代碼實(shí)現(xiàn) 
// 解法1
function NumberOf1Between1AndN_Solution(n)
{
    var count = 0;
    for(var i = 1;i <= n;i++){
        var cur = i;
        while(cur !== 0) {
            if(cur % 10 === 1)
                count++;
            cur  = Math.floor(cur/10);
        }
    }

    return count;
}
// 解法2
function NumberOf1Between1AndN_Solution(n)
{
    var count = 0;
    var factor = 1;
    var cur = 0;
    var high = 0;
    var low = 0;
    
    while(divide(n, factor) !== 0){
        low = n - (divide(n, factor))*factor;
        cur = (divide(n, factor))%10;
        high = divide(n, factor*10);
        
        if(cur === 0)
            count += high*factor;
        else if(cur === 1)
            count += (high*factor + low + 1);
        else 
            count += (high+1)*factor;
        
        factor *= 10;
    }
    return count;
}
          
function divide(a, b){
    return Math.floor(a/b);        
}

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/96389.html

相關(guān)文章

  • 由三道 LeetCode 題目簡(jiǎn)單了解一下位運(yùn)算

    摘要：使用位運(yùn)算數(shù)組只出現(xiàn)一次數(shù)字的數(shù)組得到最低的有效位，即兩個(gè)數(shù)不同的那一位看完上面的解法，我腦海中只有問號(hào)的存在，啥意思啊下面就讓我們簡(jiǎn)單了解一下位運(yùn)算并解析一下這三道題目。另，負(fù)數(shù)按補(bǔ)碼形式參加按位與運(yùn)算。你可做過這幾道題？ 在面試的準(zhǔn)備過程中，刷算法題算是必修課，當(dāng)然我也不例外。某天，我刷到了一道神奇的題目： # 136. 只出現(xiàn)一次的數(shù)字 給定一個(gè)非空整數(shù)數(shù)組，除了某個(gè)元素只出現(xiàn)一次以外...

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

  • 由三道 LeetCode 題目簡(jiǎn)單了解一下位運(yùn)算

    摘要：簡(jiǎn)單介紹一下位運(yùn)算異或運(yùn)算異或邏輯的關(guān)系是當(dāng)不同時(shí)，輸出當(dāng)相同時(shí)，輸出。另，負(fù)數(shù)按補(bǔ)碼形式參加按位與運(yùn)算。使一個(gè)數(shù)的最低位為零，可以表示為。，截止到這兒，三道題目中使用的位運(yùn)算介紹完畢，那么這里我們插入一下的詳細(xì)題解。你可做過這幾道題？ 在面試的準(zhǔn)備過程中，刷算法題算是必修課，當(dāng)然我也不例外。某天，我刷到了一道神奇的題目： # 136. 只出現(xiàn)一次的數(shù)字 給定一個(gè)非空整數(shù)數(shù)組，除了某個(gè)元素只...

    劉明 評(píng)論0 收藏0

  • 劍指offer: 整數(shù)中1出現(xiàn)的次數(shù)（從1到n整數(shù)中1出現(xiàn)的次數(shù)）

    摘要：?jiǎn)栴}描述求出的整數(shù)中出現(xiàn)的次數(shù)并算出的整數(shù)中出現(xiàn)的次數(shù)為此他特別數(shù)了一下中包含的數(shù)字有因此共出現(xiàn)次但是對(duì)于后面問題他就沒轍了。希望你們幫幫他并把問題更加普遍化可以很快的求出任意非負(fù)整數(shù)區(qū)間中出現(xiàn)的次數(shù)從到中出現(xiàn)的次數(shù)。 問題描述：求出1~13的整數(shù)中1出現(xiàn)的次數(shù),并算出100~1300的整數(shù)中1出現(xiàn)的次數(shù)？為此他特別數(shù)了一下1~13中包含1的數(shù)字有1、10、11、12、13因此共出現(xiàn)6...

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

  • 劍指offer中的算法題(PHP版)

    摘要：二維數(shù)組中的查找在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。解法有兩種，一種是遞歸法，一種是迭代法但是遞歸法計(jì)算的時(shí)間復(fù)雜度是以的指數(shù)的方式遞增的，如果面試中千萬(wàn)不要用遞歸法，一定要用迭代法。 二維數(shù)組中的查找 在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請(qǐng)完成一個(gè)函數(shù)，輸入這樣的一個(gè)二維數(shù)組和...

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

  • C語(yǔ)言——一維數(shù)組算法問題

    摘要：算法描述向數(shù)組中輸入元素定義一個(gè)新數(shù)組將數(shù)組中的元素倒序存放將數(shù)組正序輸出，注意結(jié)尾無(wú)空格的格式問題。最后打印出來(lái)數(shù)組中的元素，也就是非共有值，此處注意格式問題。 問題1：將數(shù)組中的數(shù)逆序存放 本題要求編寫程序，將給定的n個(gè)整數(shù)存入數(shù)組中，將數(shù)組中的這n個(gè)數(shù)逆序存放， 再按順序輸出數(shù)組中的元...

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

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

0條評(píng)論

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