【刷算法】整數中1出現的次數（從1到n整數中1出現的次數）

Shisui 發布于2019-08-23 10:29 / 2273人閱讀

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

題目描述

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

分析 解法1

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

解法2

例如103這樣的數字：

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

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

百位數是1的有100，101，102，103

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

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

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

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

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

代碼實現

// 解法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);        
}

云服務器 GPU云服務器數據出現次數統計 php統計出現次數 js正則出現次數 js統計字母出現次數

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

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

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

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

daydream 2019-05-21 11:41 評論0 收藏0
由三道 LeetCode 題目簡單了解一下位運算

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

劉明 2019-05-22 14:21 評論0 收藏0
劍指offer: 整數中1出現的次數（從1到n整數中1出現的次數）

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

forsigner 2019-08-16 18:23 評論0 收藏0
劍指offer中的算法題(PHP版)

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

big_cat 2019-06-27 15:43 評論0 收藏0
C語言——一維數組算法問題

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

lifesimple 2021-11-15 11:38 評論0 收藏0