【剑指】43.从1到n整数中1出现的次数

题目描述

• 输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。例如，输入12，从1到12这些整数中包含1 的数字有1，10，11和12，1一共出现了5次。

算法分析

• 参考博文：计算1至n中数字X出现的次数
• 当计算右数第 i 位包含的 X 的个数时：
  1. 取第 i 位左边（高位）的数字，乘以 10^(i−1)，得到基础值 a。
  2. 取第 i 位数字，计算修正值：
  (1) 如果大于 X，则结果为 a+10^(i−1)。
  (2) 如果小于 X，则结果为 a。
  (3) 如果等 X，则取第 i 位右边（低位）数字，设为 b，最后结果为 a+b+1。
  

提交代码：

class Solution {
public:
	int NumberOf1Between1AndN_Solution(int n)
	{
		/* 高、低、当前位 */
		int high, low, curr, temp;
		int result = 0, i = 1;
		/* judgeVal的出现次数,可以改为1-9中任意的数 */
		int judgeVal = 1;
		
		do {
			high = n / (int)pow(10, i);
			temp = n % (int)pow(10, i);
			curr = temp / (int)pow(10, i - 1);
			low = n % (int)pow(10, i - 1);

			result += high * (int)pow(10, i - 1);

			if (curr > judgeVal)
				result += (int)pow(10, i - 1);
			else if (curr == judgeVal)
				result = result + low + 1;

			++i;
		} while (high != 0);

		return result;
	}
};

测试代码：

// ====================测试代码====================
void Test(const char* testName, int n, int expected)
{
	if (testName != nullptr)
		printf("%s begins: \n", testName);

	Solution s;
	if (s.NumberOf1Between1AndN_Solution(n) == expected)
		printf("Solution1 passed.\n");
	else
		printf("Solution1 failed.\n");

	printf("\n");
}

void Test()
{
	Test("Test1", 1, 1);
	Test("Test2", 5, 1);
	Test("Test3", 10, 2);
	Test("Test4", 55, 16);
	Test("Test5", 99, 20);
	Test("Test6", 10000, 4001);
	Test("Test7", 21345, 18821);
	Test("Test8", 0, 0);
}

int main(int argc, char* argv[])
{
	Test();

	return 0;
}