題目描述
輸入一個(gè)整數(shù)n，求1n這n個(gè)整數(shù)的十進(jìn)制表示中1出現(xiàn)的次數(shù)曼氛。例如豁辉，輸入12，112這些整數(shù)中包含1的數(shù)字有1搪锣、10秋忙、11和12，1一共出現(xiàn)了5次构舟。
解法一：
遍歷所有的數(shù)字，不停地將數(shù)字i%10，i/10狗超，求得每個(gè)數(shù)字含有1的個(gè)數(shù)弹澎。每個(gè)數(shù)字i有l(wèi)ogi位，所以時(shí)間復(fù)雜度為O（nlogn）努咐。效率很慢苦蒿，不推薦。
解法二：
觀察數(shù)字規(guī)律渗稍。
假如n=23佩迟，即序列為1，2竿屹，3报强，4，5拱燃，6秉溉，7，8碗誉，9召嘶，10，11哮缺，12弄跌，13，14尝苇，15碟绑，16，17茎匠，18格仲，19，20诵冒，21凯肋，22，23
1-9中共有1個(gè)1汽馋，
10-19中每個(gè)數(shù)字的開頭都有1侮东，如果不考慮開頭的1，則變?yōu)榍?-9中1的個(gè)數(shù)豹芯，與1-9中1的個(gè)數(shù)相同悄雅。10-19一共10個(gè)數(shù)字，算上每個(gè)開頭都有的1铁蹈，加上0-9中1的個(gè)數(shù)宽闲，一共有11個(gè)1，
20-23中每個(gè)數(shù)字的開頭為2，可以不考慮容诬，則變?yōu)榍?-3中1的個(gè)數(shù)娩梨，則20-23中共1個(gè)1
所以1-19中共有13個(gè)1。
由此我們可以看出览徒，位數(shù)更多的數(shù)是由位數(shù)更低的數(shù)組成的狈定，以1-20為例，
我們只需要知道含有多少組0-9习蓬，（為了與10之類的低位0符合纽什，采用0~9而不是1-9），也即各位為1的數(shù)量躲叼，則序列退化為0芦缰，0，0押赊，0饺藤，0，0流礁，0涕俗，0，0神帅，0再姑，10，10找御，10元镀，10，10霎桅，10栖疑，10，10滔驶，10遇革，10，20揭糕，20萝快，20，20著角，
再統(tǒng)計(jì)有多少組10即可揪漩，也即十位為1的數(shù)量。
可以推而廣之吏口，知道任何一位1的數(shù)量奄容，最后相加即可得到1的總數(shù)量冰更。
個(gè)位1的數(shù)量，我們可以計(jì)算n/10的值i1嫩海，n%10的值y1冬殃，若y1>=1囚痴，則s1=i1+1叁怪，若y1=0，則s1=i1
十位1的數(shù)量深滚，我們可以計(jì)算n/100的值i2奕谭，n%100的值y2，若y2>=20痴荐，則s2=i2 * 10+10血柳，若10<=y2<20，則s2=i2 * 10 + y2 % 10 + 1生兆，若0<=y2<10,則s2=i2 * 10
百位1的數(shù)量难捌，我們可以計(jì)算n/1000的值i3，n%1000的值y3鸦难，若y3>=200根吁，則s3=i3 * 100 + 100，若100<=y3<200合蔽，則s3=i2 * 100 + y3 % 100 + 1, 若0<=y3<100击敌，則s3=i3 * 100
……
……
所以個(gè)位1的數(shù)量也可以寫成
個(gè)位1的數(shù)量，我們可以計(jì)算n/10的值i1拴事，n%10的值y1沃斤，若y1>=2，則s1=i1 * 1 + 1刃宵，若1<=y1<2衡瓶，則s1=i1 * 1 + y1 % 1 + 1，若0<=y1<1牲证，則s1=i1*1
于是可以通過循環(huán)很簡單來實(shí)現(xiàn)哮针，時(shí)間復(fù)雜度為O（logn）
public class Solution {
public int NumberOf1Between1AndN_Solution(int n) {
int num = n;
int divisor = 1;
int sum = 0;
while(num / 10.0 > 0) {
int i = n / (divisor * 10);
int y = n % (divisor * 10);
if(y >= 2 * divisor) {
sum += i * divisor + divisor;
}
else if(y >= divisor && y < 2 * divisor){
sum += i * divisor + y % divisor + 1;
}
else {
sum += i * divisor;
}
divisor *= 10;
num /= 10;
}
return sum;
}
}
注意循環(huán)條件為num/10.0而不是num/10，這是為了保證只有個(gè)位數(shù)的情況从隆。
