題目：求出1~13的整數中1出現的次數,并算出100~1300的整數中1出現的次數襟雷？為此他特別數了一下1~13中包含1的數字有1、10仁烹、11耸弄、12、13因此共出現6次,但是對于后面問題他就沒轍了晃危。ACMer希望你們幫幫他,并把問題更加普遍化,可以很快的求出任意非負整數區(qū)間中1出現的次數（從1 到 n 中1出現的次數）叙赚。
思路：
方法一：
??直接一個數字一個數字的計算每個數字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)
百位
在百位宁否，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次方的歸納就完成了眼溶。
- sum1 = sum(count(i))，i = Math.pow(10, j), 0<=j<=log10(n)
源碼：GitHub源碼
方法一：
public class Solution {
public int NumberOf1Between1AndN_Solution(int n) {
int sum = 0;
for(int i = 1;i <= n;i++){
int temp = i;
while(temp != 0){
if(temp % 10 == 1) sum++;
temp = temp / 10;
}
}
return sum;
}
}
方法二：
public class Solution {
public int NumberOf1Between1AndN_Solution(int n) {
if(n <= 0) return 0;
int count = 0;
for(int i = 1;i <= n;i *= 10){
int sum = i * 10;
count += (n / sum) * i;
if((n % sum) > (i * 2 - 1)) count += i;
else if(n % sum < i) ;
else count += n % sum - i + 1;
}
return count;
}
}
