剑指offer面试题[32]：从1到n整数中1出现的次数

缺乏、安全感 2022-06-13 13:25 131阅读 0赞

## 题目描述 ##

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

**(题目意思是：输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数**)

思路分析：

思路一：（不考虑时间效率的解法，靠它想拿offer有点难）

从1到n遍历求每个数字中1的个数，然后累加，每个数用求余运算（%），若余数为1，则说明该位为1。大多数人应该可以求解。

思路二：（从数字规律着手明显提高效率的做法，能让面试官耳目一新）

如果希望不用计算每个数字的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这2000个数字后四位中1出现的次数是8000次。由于最高位是2，我们可以再把1346到21345分为两段，1346到11345和11346到213456.每一段剩下的4位数字中，选择其中一位是1，其余三位可以在0~9这10个数字中任选，因此根据排序组合的原则，总共出现的次数是2\*4\*10^3=8000次。

至于1到1345中1出现的次数，我们就可以根据递归求得了。这也就是为什么把1~21345分为1~1345和1346~21345两段的原因。因为把21345的最高位去掉就变为1345，便于我们采用递归的思路。

参考代码如下：

#include <iostream>
    #include <stdio.h>
    using namespace std;
    
    class Solution {
    public:
    	/*方法1：
    	int NumberOf1Between1AndN_Solution(int n)
    	{
    	if(n<=0)
    	return 0;
    	int number=0;
    	for(int i=1;i<=n;i++)
    	{
    	int temp=i;
    	while(temp)    //注意这里一定是用一个中间临时变量来存取每次读入的数字i
    	{
    	int s=temp%10;
    	if(s==1)
    	number++;
    	temp=temp/10;
    	}
    	}
    	return number;
    	}
    	*/
    	//方法2：
    	int NumberOf1Between1AndN_Solution(int n)
    	{
    		if (n <= 0)
    			return 0;
    
    		char strN[50];
    		sprintf_s(strN, "%d", n);   //为了编程方便，将数字转换为字符串
    
    		return NumberOf1(strN);
    	}
    
    	int powerBase10(int n)
    	{
    		int result = 1;
    		for (int i = 0; i<n; i++)
    			result *= 10;
    		return result;
    	}
    
    	int NumberOf1(char *strN)
    	{
    		if (strN == NULL || *strN<'0' || *strN>'9' || *strN == '\0')
    			return 0;
    		int first = *strN - '0';
    		int length = static_cast<int>(strlen(strN));
    		if (length == 1 && first == 0)
    			return 0;
    		if (length == 1 && first>0)
    			return 1;
    
    		//假设strN是"21345"
    		//numFirstDigit是数字10000~19999的第一位中的数目
    		int numFirstDigits = 0;
    		if (first>1)
    			numFirstDigits = powerBase10(length - 1);
    		else if (first == 1)
    			numFirstDigits = atoi(strN + 1) + 1;   //atoi是把字符串转换成整型数的一个函数
    
    		//numOtherDigits是1346~21345除了第一位之外的数位中的数目
    		int numOtherDigits = first*(length - 1)*powerBase10(length - 2);
    		int numRecursive = NumberOf1(strN + 1);
    
    		return numFirstDigits + numOtherDigits + numRecursive;
    	}
    };
    
    int main()
    {
    	Solution s;
    	int n;
    	cin >> n;
    	int CountOf1=s.NumberOf1Between1AndN_Solution(n);
    	cout << CountOf1 << endl;
    	system("pause");
    }