题目描述

求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。

分析

解法1

从1到n依次遍历，对于每一个数字都检查一遍它有几个1，然后累加即可，时间复杂度是O(N*logN)

解法2

例如103这样的数字：

• 个位数是1的有001，011，021，031，041，051，061，071，081，091，101，共11个
• 十位数是1的有010，011，012，013，014，015，016，017，018，019，共10个
• 百位数是1的有100，101，102，103 所以对于每一位来说，这一位数字是1的情况是由这一位本身、这一位的所有高位、这一位的所有低位，共同决定的，总结一下，对于abXcd来说：
• X=0时，如果ab=01，那么就有00100~00199这100个数字都是X位是1的数字
• X=1时，如果ab=01，那么就有00100~00199这100个数字 + ab100~ab1cd这个cd个数字
• X>=2时，如果ab=01，那么就有00100~00199这100个数字 + 01100~01199这100个数字 其实这道问题在《编程之美》第134页有详解，看不懂可以看看书。

代码实现

// 解法1function NumberOf1Between1AndN_Solution(n){	var count = 0;	for(var i = 1;i <= n;i++){		var cur = i;		while(cur !== 0) {			if(cur % 10 === 1)				count++;			cur  = Math.floor(cur/10);		}	}	return count;}// 解法2function NumberOf1Between1AndN_Solution(n){    var count = 0;	var factor = 1;    var cur = 0;    var high = 0;    var low = 0;        while(divide(n, factor) !== 0){        low = n - (divide(n, factor))*factor;        cur = (divide(n, factor))%10;        high = divide(n, factor*10);                if(cur === 0)            count += high*factor;        else if(cur === 1)            count += (high*factor + low + 1);        else             count += (high+1)*factor;                factor *= 10;    }    return count;}          function divide(a, b){    return Math.floor(a/b);        }复制代码