輸入一個(gè)整數(shù) n笼吟，求從 1 到 n 這 n 個(gè)整數(shù)的十進(jìn)制表示中 1出現(xiàn)的次數(shù)倘屹。
例如輸入 12密浑，從 1 到 12 這些整數(shù)中包含 “1” 的數(shù)字有 1，10迷郑，11 和 12蛾默，其中 “1” 一共出現(xiàn)了 5次静尼。
樣例
輸入： 12
輸出： 5
分析：
算法一：
暴力枚舉
假如存在abcdef這樣一個(gè)數(shù)：
當(dāng)枚舉到i=2塔逃，即number[i] = c時(shí)：
_ _ c_ _ _
（1）c左邊：00-ab-1；c右邊：000-999 此時(shí)：共ab*1000個(gè)“1”
（2）00-ab-1算完了揽浙，開始算ab這一種状婶，即abc_ _ _
當(dāng)c=0時(shí)，0個(gè)1
當(dāng)c=1時(shí)馅巷，000-def膛虫，共def+1個(gè)“1”
當(dāng)c>1時(shí)，000-999钓猬，共1000個(gè)1
時(shí)間復(fù)雜度：
數(shù)字n共有稍刀，時(shí)間復(fù)雜度為：
class Solution {
public:
int numberOf1Between1AndN_Solution(int n) {
if(!n) return 0;
int res = 0;
vector<int> number;//把n的每一位存到數(shù)組中（高位在右邊）
while(n) number.push_back(n%10), n/=10;//把n的每一位存到數(shù)組中
for(int i = number.size()-1; i>=0; i--) {
//比如abcdef，此時(shí)number[i]=c,則left=ab敞曹，right=def账月，t記錄right是幾位數(shù)
int left = 0, right = 0, t = 1;
for(int j = number.size()-1;j>i;j--) left = left*10 + number[j];
for(int j = i-1;j>=0;j--) right = right*10 + number[j], t*=10;
//比如abcdef，此時(shí)number[i]=c,則c左邊：00-ab-1澳迫，右邊：000-999局齿，總共ab*1000個(gè)“1”
res += left * t;
//00-ab-1算完了，開始算ab這一種橄登，即abc_ _ _
//當(dāng)c=0時(shí)抓歼，0個(gè)1
//當(dāng)c=1時(shí)，000-def拢锹，共def+1個(gè)“1”
//當(dāng)c>1時(shí)谣妻，000-999，共1000個(gè)1
if(number[i] == 1) res += right+1;
else if(number[i] > 1) res += t;
}
return res;
}
};
算法二：
class Solution {
public:
int numberOf1Between1AndN_Solution(int n) {
if(!n) return 0;
int res = 0, left = n, right = 0, t=1, x;
while(left) {
x = left % 10, left /= 10;
res += left * t;
if (x > 1) res += t;
else if (x == 1) res += right + 1;
right += x * t, t *= 10;
}
return res;
}
};
