本文共 2725 字,大约阅读时间需要 9 分钟。
从 1 到 n 整数中 1 出现的次数。题目 :输入一个整数 n ,求从 1 到 n 这n 个整数的十进制表示中1 出现的次数。 例如 输入 12,从 1 到 12 这些整数中包含 1 的数字 有 1, 10 ,11 和 12, 1 一共出现了 5次。
如果在面试的时候碰到这个问题,应聘者大多能想到最直观的方法,也就是累加 1到 n中每个整数 1 出现的次数。我们可以每次通过对 10 求余数判断整数的个位数字是不是 1.如果这个数字大于 10,除以 10之后再判断个位数字是不是 1.基于这个思路,可以写出以下代码
int NumberOf1Between1AndN( unsigned int n ){ int number = 0; for( unsigned int i=1; i<=n; ++i ) number += NumberOf1( i ); return number;}int NumberOf1( unsigned int n ){ int number = 0; while( n ) { if( n%10 == 1 ) number ++; n = n/10; } return number;}
在上述思路中,我们对每个数字都要做除法和求余运算以求出该数字中 1 出现的次数。如果输入数字 n, n有O(logn)位,我们需要判断每一位是不是 1 ,那么它的时间复杂度是 O(n*logn)。当输入 n 非常大的时候,需要大量的计算,运算效率不高。面试官不会满意这种做法。
如果希望不用计算每个数字的1的个数,那就只能去寻找 1 在数字中出现的规律了。为了找到规律,不妨用一个稍微大一点的数字比如 21345 作为例子来分析。把从 1 到21345的所有数字分为两段,一段是 1到 1345,另一段 是 1346 到 21345.
先看从 1346到21345中 1 出现的次数。 1 的出现分为两种情况。首先分析 1出现在最高位(本例中是万位)的情况。从1346到21345的数字中, 1 出现在10000-19999这 10000个数字的万位中,一共出现了10000(10^4)个。
值得注意的是,并不是对所有5位数而言在万位出现的次数都是10000个。对于万位是1的数字比如输入12345,1只出现在 10000-12345的万位,出现的次数不是10^4次,而是2346次,也就是除去最高数字之后剩下的数字再加上 1(即 2345+1 = 2346 次)。接下来分析 1 出现在除最高位之外的其他四位数中的情况。例子中 1346-21345 这 20000个数字中后4 位中 1 出现的次数是 2000次。由于最高位是 2,我们可以再把 1346-21345分成两段, 1346-11345和11346-21345.每一段剩下的4位数字中,选择其中一位是1 1, 其余三位可以再 0-9 这10个数字中任意选择,因此根据排列组合原则,总共出现的次数 是2*10^3 = 2000次。
至于从1 到 1345中 1出现的次数,我们可以用递归求得。这也是我们为什么要把 1-21345 分成 1-1345 和 1346-21345 两段的原因。因为把 21345 的最高位 去掉就变成 1345,便于 我们采用递归的思路。
int NumberOf1Between1AndN_Solution2(int n){ if(n <= 0) return 0; char strN[50]; sprintf(strN, "%d", n); return NumberOf1(strN);}int NumberOf1(const char* strN){ if(!strN || *strN < '0' || *strN > '9' || *strN == '\0') return 0; int first = *strN - '0'; unsigned int length = static_cast(strlen(strN)); if(length == 1 && first == 0) return 0; if(length == 1 && first > 0) return 1; // 假设strN是"21345" // numFirstDigit是数字10000-19999的第一个位中1的数目 int numFirstDigit = 0; if(first > 1) numFirstDigit = PowerBase10(length - 1); else if(first == 1) numFirstDigit = atoi(strN + 1) + 1; // numOtherDigits是01346-21345除了第一位之外的数位中1的数目 int numOtherDigits = first * (length - 1) * PowerBase10(length - 2); // numRecursive是1-1345中1的数目 int numRecursive = NumberOf1(strN + 1); return numFirstDigit + numOtherDigits + numRecursive;}int PowerBase10(unsigned int n){ int result = 1; for(unsigned int i = 0; i < n; ++ i) result *= 10; return result;}
这种思路是每次去掉最高位做递归,递归的次数和位数相同。一个数字 n 有O(logn)位,因此这种思路的时间复杂度是O(logn),比前面的原始方法要好很多。
(1)功能测试(输入 5、10、55、99 等)
(2)边界值测试(输入 0、1等)
(3)性能测试(输入较大的数字 如 10000、21235等)
复杂问题的思维能力。
转载地址:http://gkerj.baihongyu.com/