題目描述
求出1~13的整數中1出現的次數,并算出100~1300的整數中1出現的次數？為此他特別數了一下1~13中包含1的數字有1、10、11、12、13因此共出現6次,但是對于后面問題他就沒轍了，ACMer希望你們幫幫他,并把問題更加普遍化,可以很快的求出任意非負整數區間中1出現的次數（從1 到 n 中1出現的次數），
思路
像類似這樣的問題，我們可以通過歸納總結來獲取相關的東西，
首先可以先分類：
個位
我們知道在個位數上，1會每隔10出現一次，例如1、11、21等等，我們發現以10為一個階梯的話，每一個完整的階梯里面都有一個1，例如數字22，按照10為間隔來分三個階梯，在完整階梯0-9，10-19之中都有一個1，但是19之后有一個不完整的階梯，我們需要去判斷這個階梯中會不會出現1，易推斷知，如果最后這個露出來的部分小于1，則不可能出現1（這個歸納換做其它數字也成立），
我們可以歸納個位上1出現的個數為：
n/10 * 1+(n%10!=0 ? 1 : 0)
十位
現在說十位數，十位數上出現1的情況應該是10-19，依然沿用分析個位數時候的階梯理論，我們知道10-19這組數，每隔100出現一次，這次我們的階梯是100，例如數字317，分析有階梯0-99，100-199，200-299三段完整階梯，每一段階梯里面都會出現10次1（從10-19），最后分析露出來的那段不完整的階梯，我們考慮如果露出來的數大于19，那么直接算10個1就行了，因為10-19肯定會出現；如果小于10，那么肯定不會出現十位數的1；如果在10-19之間的，我們計算結果應該是k - 10 + 1，例如我們分析300-317，17個數字，1出現的個數應該是17-10+1=8個，
那么現在可以歸納：十位上1出現的個數為：
設k = n % 100，即為不完整階梯段的數字
歸納式為：(n / 100) * 10 + (if(k > 19) 10 else if(k < 10) 0 else k - 10 + 1)
百位
現在說百位1，我們知道在百位，100-199都會出現百位1，一共出現100次，階梯間隔為1000，100-199這組數，每隔1000就會出現一次，這次假設我們的數為2139，跟上述思想一致，先算階梯數 * 完整階梯中1在百位出現的個數，即n/1000 * 100得到前兩個階梯中1的個數，那么再算漏出來的部分139，沿用上述思想，不完整階梯數k199，得到100個百位1，100<=k<=199則得到k - 100 + 1個百位1，
那么繼續歸納百位上出現1的個數：
設k = n % 1000
歸納式為：(n / 1000) * 100 + (if(k >199) 100 else if(k < 100) 0 else k - 100 + 1)
后面的依次類推....
再次回顧個位
我們把個位數上算1的個數的式子也納入歸納式中
k = n % 10
個位數上1的個數為：n / 10 * 1 + (if(k > 1) 1 else if(k < 1) 0 else k - 1 + 1)
完美！歸納式看起來已經很規整了， 來一個更抽象的歸納，設i為計算1所在的位數，i=1表示計算個位數的1的個數，10表示計算十位數的1的個數等等，
k = n % (i * 10)
count(i) = (n / (i * 10)) * i + (if(k > i * 2 - 1) i else if(k < i) 0 else k - i + 1)
好了，這樣從10到10的n次方的歸納就完成了，
牛客網鏈接
js代碼
function NumberOf1Between1AndN_Solution(n)
{
// write code here
if (n <= 0) return 0
let mod
let res = 0
for (let i = 1; i <= n; i *= 10) {
res += Math.floor(n / (i*10)) * i
mod = n % (i*10)
if (mod > i * 2 -1) res += i
else if (mod >= i && mod <= i * 2 -1 ) res += (mod - i + 1)
}
return res
}```
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/138115.html
標籤：其他
下一篇：leetcode - 反轉鏈表