剑指 Offer 43. 1～n 整数中 1 出现的次数(纵向求解、组合思想、找规律)

一、题目

剑指 Offer 43. 1～n 整数中 1 出现的次数

题目描述

输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。

例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

示例1：

1 2	输入：n = 12 输出：5

示例2：

1 2	输入：n = 13 输出：6

二、分析

方法1 暴力（横向求法）

暴力遍历小于等于n的所有数，针对每一个数字，求其所有位数上1的个数（对每个数字进行横向计数）。但是此方法时间复杂度随着n的增大会变大。时间复杂度过高，导致超时。这种方法不可取。

方法2 纵向求法+数学规律（组合思想）

这道题要求1到n中1出现的个数。我们有两种宏观思路。

第一种是从局部，针对每一个数，判断该数所有位数（横向），将该数字中出现1的个数计算完。再去计算下一个数出现的1的个数，直到计算到n。（方法1）
第二种是针对某一位，求取小于等于n所有数字该位为1的个数和（纵向）。再将所有位置1的总和加起来，就是结果了。（方法2）

这道题思路主要介绍纵向求法。下面举例针对n的某一位cur来分析。

举例,cur为index为1上的数。要求index为1上的1个数总和，先看看小于等于n里面的数有哪些满足,分情况讨论
1. cur=$\color{red}{0}$ 假设 n= 2 3 $\color{red}{0}$ 4
  - （00-22） $\color{red}{1}$ （0-9）：总共有（22-0+1）*（9-0+1）种组合
    
    也即：高位23x10
2. cur=$\color{red}{1}$ 假设 n= 2 3 $\color{red}{1}$ 4
  - （00-22） $\color{red}{1}$ （0-9）：总共有（22-0+1）（9-0+1）种组合
    
    也即：高位23x10
  - （23） $\color{red}{1}$ （0-4）：总共有4-0+1种组合
    
    也即：低位+1
    
    所以该种情况为：高位23x10+低位+1
3. cur=$\color{red}{2}$ （2-9一样）假设 n= 2 3 $\color{red}{2}$ 4
  - （00-22） $\color{red}{1}$ （0-9）：总共有（22-0+1）（9-0+1）种组合
    
    也即：高位23x10
  - （23） $\color{red}{1}$ （0-9）：总共有9-0+1种组合
    
    也即：10
    
    所以该种情况为：高位23x10+10=（高位+1）x10

三、代码

方法1 暴力（横向求法）

/*
* 题目：剑指 Offer 43. 1～n 整数中 1 出现的次数
* 描述：输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。
* 实现: 暴力（超出时间限制）
* 复杂度：时间O(n)
*		 空间 O(1)：常数辅助空间
*/
int countDigitOne(int n) {
	int count = 0;
	int t;
	for (int i = 1; i <=n; i++)
	{
		t = i;
		while (t>0) {
			
			if (t % 10 == 1)count++;
			t = t / 10;
		}
	}
	return count;
}

方法2 纵向求法+数学规律（组合思想）

/*
* 题目：剑指 Offer 43. 1～n 整数中 1 出现的次数
* 描述：输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。
* 实现: 数学找规律
* 复杂度：时间O(logn):循环求n的个数logn。再次logn求解res。一共2xlogn.
*		 空间 O(1)：常数辅助空间
*/
int countDigitOneA(int n) {
	int res = 0,t=n,bitNum=0;
	int low, high;
	int cur;
	//计算n有多少位
	while (t > 0) {
		t = t / 10;
		bitNum++;
	}

	for (int i = 0; i < bitNum; i++)
	{
		low = n % long(pow(10, i));
		high = n / long(pow(10,i+1));//防止溢出

		cur = int(n / (pow(10, i))) % 10;
		if (cur == 0) res += (high*pow(10, i));
		else if (cur == 1) res += (high*pow(10, i)+low+1);
		else res += ((high+1) * pow(10, i));
	}
	return res;
}