［分析总结：leetcode-Number of Digit One]寻找整数1到n之间所有数字中1出现的次数

109 阅读 0 评论 72 点赞

我是靠谱客的博主真实小熊猫，最近开发中收集的这篇文章主要介绍［分析总结：leetcode-Number of Digit One]寻找整数1到n之间所有数字中1出现的次数，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

leetcode原题链接：https://leetcode.com/problems/number-of-digit-one/

题目描述：要求寻找整数1到n之间所有数字中，1出现的次数。如给定数字15，那么1到15之间出现1的数字为：1、10、11、12、13、14、15，共出现8次。

方法一：我们可以用最简单的办法先尝试一下，遍历1到n中间的每个整数，对每个整数从低位到高位依次检查，如果有1出现则计数器自加。

public int countOnes1(int n){
	int count = 0;
	for(int i = 0; i <= n; i++){
		int cur = i;
		while(cur > 0){
			int tmp = (int) i%10;
			if(tmp == 1) count++;
			cur = cur/10;
		}
	}

	return count;
}

这样计算方式比较直观。但是这个函数在leetcode上提交后会报计算超时的错误。因为两层嵌套的话复杂度提升了，对于大数值来说，计算时间也随之增加。

方法二：

既然直观的方法不能满足要求，那智能寻找规律了。先来看几组数字。

对于两位数：

我们先对数字15来做分析，在个位上可能会出现1的数字有－－01，11；在十位上会出现1的数字为：10，11，12，13，14，15。那么对于1到15的整数，1出现的次数为f(15)= <个位出现1的次数> + <十位出现1的次数> = 2 + 6 = 8。

我们继续看数字21，个位出现1的数字－－01，11，21；十位出现1的数字：10，11，12......18，19。所以f(21)= 3 ＋ 10 ＝ 13。

对数字83，个位出现1的数字－－01，11，21，31，41，51，61，71，81；十位出现1的数字：10，11，12......18，19。所以f(83)=8 + 10 = 18。

综合上面的数字我们发现，在两位数中，在个位上出现1的次数收到十位数和自身个位数的影响。如果个位为0，则出现的次数＝十位数值；如果个位大于等于1，则出现次数＝十位数值＋ 1。

再看十位数的情况，当十位数为1时，十位数出现1的次数＝个位数＋ 1；当十位数大于1时，十位数出现1的次数＝ 10。

下面继续看三位数的情况：

如数字344。个位数出现1的数字有： 01，11，21......301，311，321，331，341，共35个（34 ＋ 1）；十位数出现1的数字：10－19，110－119，210－219，310－319，共40个（（3＋1）＊10）。百位出现1的数字： 100－199，共100个。

但如果是数字110，那么个位出现1的数字：01，11......91，101，共11（110 ／ 10）个；十位出现1的数字：10－19，110，共11个（1＊10 ＋ 1）；百位出现1的数字：100，101...110,共11（0＋10＋1）个。

综上我们总结：对于三位数，个位数出现1的次数受数字本身a（设数字为a，“［］“符号表示取整运算）［a／10］的数值和个位本身的影响，若个位数为0，则个位数出现1的次数为［a/10］，若个位数大于等于1，则个位数出现1的次数为：［a/10 ＋1］。

然而，三位数中，十位出现1的次数，受十位数本身和其高位与低位数值的影响。若十位数等于0，十位出现1的次数＝［a/100］＊10；若十位数等于1，十位出现1的次数＝［a/100］＊10 ＋ a％10 ＋1；若十位数大于等于2，则十位出现1的次数＝（［a/100 ］＊10＋1）＊10。

这里可以发现一个规律，对于数字1 到 a(n)a(n-1)......a(2)a(1)a(0),其第q位（q >= 0 && q <= n)出现数字1的总和公式：

//伪代码片段
if[a(q) == 0]{
	ones = a(n)...a(q+1) * 10^q;
}else if[a(q) == 1]{
	ones = a(n)...a(q+1) * 10^q + [a(q-1)...a(0) + 1];
}else{// a(q) >= 2 的情况
	ones = [a(n)...a(q+1) + 1] * 10^q;
}

出现1的总数，就是上述每一位可能出现1的计数之和。

用Java代码描述：

public int countOnes2(int n){
	int counts = 0;
	for(long factor = 1; factor <= n; factor *= 10){
		int currentNum = (n / factor) % 10;
		int highNum = (n/factor)/10;
		int lowNum = n % factor;
		
		switch(currentNum){
			case 0:
				counts += highNum * factor;
				break;
			case 1:
				counts += highNum * factor + lowNum + 1;
				break;
			default:
				counts += (highNum + 1) * factor;
				break;
		}
	}
}

这个算法中，currentNumber >= 2时，factor算子的乘数为highNum +1, 其余情况factor蒜子的乘数为 highNumber，然而highNum ＝（n／factor）／10 ＝［（highNum ＊ 10 ＋ currentNum）／10］。所以对于currentNum的三个分支可以概括为： counts ＋＝ [(n/factor + 8)/10] * factor + (n/factor)%10 == 1?n%factor +1 : 0;

这样的话，就有一个特别牛叉的共识出来了。看着这个公式，前面我所写的都像废话似的，有没有这种感觉？

public int countOnes3(int n){
	int counts = 0;
	for(long factor = 1; factor <= n; factor *= 10){
	<span style="white-space:pre">	</span>counts += ((n/factor + 8)/10) * factor + (n/factor)%10 == 1? n%factor + 1 : 0;
	}
}

现在来看，这个算法就简单多了，也不用从1到n每个数都遍历一遍。