給定一個整數 n，計算所有小于等于 n 的非負整數中數字 1 出現的個數。

示例 1：

輸入：n = 13
輸出：6
示例 2：

輸入：n = 0
輸出：0

解題思路

正確性證明

例如：對于n=3015，

• 個位為1的數字組成為[000-301]1，所以共有302個數字個位數為1，所以對答案貢獻302個1。
• 十位為1的數字組成為[01-30]1[00-99]和[00]1[00-05]，所以共有300+6個數字個位數為1，所以對答案貢獻306個1。
• 百位為1的數字組成為[0-2]1[00-99]，所以共有300個數字個位數為1，所以對答案貢獻200個1。
• 千位數字為1很明顯只有1000個數字，1[000-999],所以對答案貢獻1000個1。

所以最后的總和為1908

代碼

class Solution {public int countDigitOne(int n) {int bef=0,res=0,w=1;while (n>0){int cur=n%10;n/=10;if (cur>1){res+=(n+1)*w;}else if (cur==1){res+=n*w+bef+1;}else res+=n*w;bef+=cur*w;w*=10;}return res;}
}