成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲 中文字幕 日韩 无码

資訊專欄INFORMATION COLUMN

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

Shisui / 2329人閱讀

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

分析 解法1

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

解法2

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

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

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

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

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

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

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

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

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

代碼實現(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)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/96389.html

相關(guān)文章

  • 由三道 LeetCode 題目簡單了解一下位運算

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

    daydream 評論0 收藏0

  • 由三道 LeetCode 題目簡單了解一下位運算

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

    劉明 評論0 收藏0

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

    摘要：問題描述求出的整數(shù)中出現(xiàn)的次數(shù)并算出的整數(shù)中出現(xiàn)的次數(shù)為此他特別數(shù)了一下中包含的數(shù)字有因此共出現(xiàn)次但是對于后面問題他就沒轍了。希望你們幫幫他并把問題更加普遍化可以很快的求出任意非負整數(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 評論0 收藏0

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

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

    big_cat 評論0 收藏0

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

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

    lifesimple 評論0 收藏0

發(fā)表評論

0條評論

閱讀需要支付1元查看
<