計數的1的中的整數的總數從1到N

給定一個整數n，計數數字1的總數量出現在所有非負整數小於或等於n。

例如：給定n = 13，返回6，因爲位1時發生在以下數字：1，10，11，12，13，

有效解：

int countDigitOne(int n) { 
    if (n <= 0) return 0; 
    int q = n, x = 1, ans = 0; 
    do { 
     int digit = q % 10; 
     q /= 10; 
     ans += q * x; 
     if (digit == 1) ans += n % x + 1; 
     if (digit > 1) ans += x; 
     x *= 10; 
    } while (q > 0); 
    return ans; 
}

我的問題：

我找到了解決問題的論壇之一，我發現很難理解的解決方案。我瞭解它很簡單，但請詳細解釋我的幫助。

謝謝

來源

2016-02-06 L887

這裏是解決這個的一種方法：假設n < 10^k，即n可以通過k十進制數字表示。讓我們嘗試構造所有具有k或更少的小數位的正數，其中1 s。有2^k可能性1 s在一些k位。

對於1展示位置的每種選擇，我們可以很容易地計算出所有正數最大爲k的數字，並且小於n。

例如，匹配的模式yxxx1xx11x，其中每個x可以0或2-9所有數字，並y是2-9。請注意特別y那裏，因爲如果y==0,x它不允許爲零。有8 * 9^6的可能性。所以這個模式貢獻總計數3 * 8 * 9^6，因爲每個這樣的數字包含3個1's。

這會變得有點複雜，因爲我們需要限制那些小於或等於n的數字。這意味着並非每個組合y和x都是有效的。舉例來說，如果n=6239914230，然後y<=6，併爲y<6，第一x必須至多2，等等

來源

2016-02-06 18:41:13

所以，你在你的問題包含的代碼，digit通過數字從右到移動左邊，並且q對應於多少個x，這個增加的冪數是10。 while循環中的每個循環都計算在該位置有多少個循環。我們來看一個例子：

n  => 131 
digit => 1, 3, 1 
q  => 13, 1, 0 
x  => 1, 10,100 

q * x  => 13*1 
// there are 13 ones in the 10^0 position from 0 to 130 (13 counts of 10) 

digit == 1 => n % 1 + 1 = 0 + 1 = 1 
// there is 1 one in the 10^0 position from 131 to 131 
    (the remainder for the counts of 10) 

--- 

q * x  => 1*10 
// there are 10 ones in the 10^1 position from 0 to 100 (1 count of 100): 10 to 19 

digit == 3 => x = 10 
// there are 10 ones in the 10^1 position from 101 to 131: 110 to 119 
    (the remainder for the counts of 100) 

--- 

q * x  => 0*100 
// there are 0 ones in the 10^2 position from 0 to 0 (0 counts of 1000) 

digit == 1 => n % 100 + 1 = 31 + 1 
// there are 32 ones in the 10^2 position from 0 to 131 
    (the remainder for the counts of 1000)

來源

2016-02-07 19:49:16

計數的1的中的整數的總數從1到N

回答

相關問題