- // 面试题 43: 从 1 到 n 整数中 1 出现的次数
- // 题目: 输入一个整数 n, 求从 1 到 n 这 n 个整数的十进制表示中 1 出现的次数. 例如
- // 输入 12, 从 1 到 12 这些整数中包含 1 的数字有 1,10,11 和 12,1 一共出现了 5 次.
- #include <cstdio>
- #include <cstring>
- #include <cstdlib>
- // ==================== 方法一 ====================
- // 笨方法, 时间复杂度 O(nlogn)
- int NumberOf1(unsigned int n);
- int NumberOf1Between1AndN_Solution1(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> 0)
- {
- if (n % 10 == 1)
- ++number;
- n = n / 10;
- }
- return number;
- }
- // ==================== 方法二 ====================
- int NumberOf1(const char* strN);
- int PowerBase10(unsigned int n);
- int NumberOf1Between1AndN_Solution2(int n)
- {
- if (n <= 0)
- return 0;
- char strN[50];
- sprintf_s(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<unsigned int>(strlen(strN));
- // 边界值
- if (length == 1 && first == 0) // 输入为 0
- return 0;
- if (length == 1 && first> 0) // 输入为 0~9
- return 1;
- // 假设 strN 是 21345
- // 数字 10000~19999 中首位为 1 的数目
- int numFirstDigit = 0;
- if (first> 1)
- numFirstDigit = PowerBase10(length - 1);
- // 首位数字为 1, 如 11345, 此时 10000~11345
- else if (first == 1)
- numFirstDigit = atoi(strN + 1) + 1; // 则 1345 + 1 为首位为 1 的数目. atoi 转换字符串为数字
- // numOtherDigits 是 01346-21345 除了第一位之外的数位中 1 的数目
- // 此时 (length - 1) 表示四个位置, (length - 2)表示其余三位可能的取值 0~9
- 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) // 求 10^n 次方
- {
- int result = 1;
- for (unsigned int i = 0; i <n; ++i)
- result *= 10;
- return result;
- }
- // ==================== 测试代码 ====================
- void Test(const char* testName, int n, int expected)
- {
- if (testName != nullptr)
- printf("%s begins: \n", testName);
- if (NumberOf1Between1AndN_Solution1(n) == expected)
- printf("Solution1 passed.\n");
- else
- printf("Solution1 failed.\n");
- if (NumberOf1Between1AndN_Solution2(n) == expected)
- printf("Solution2 passed.\n");
- else
- printf("Solution2 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;
- }
测试代码
分析: 第二种方法需要仔细分析规律.
- class Solution {
- public:
- int NumberOf1Between1AndN_Solution(int n)
- {
- if (n <= 0)
- return 0;
- int number = 0;
- for (int i = 1; i <= n; ++i)
- {
- number += NumberOf1(i);
- }
- return number;
- }
- int NumberOf1(int n)
- {
- int number = 0;
- while(n)
- {
- if (n % 10 == 1)
- ++number;
- n = n / 10;
- }
- return number;
- }
- };
牛客网 - 方法一
- class Solution {
- public:
- int NumberOf1Between1AndN_Solution(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<unsigned int>(strlen(strN));
- if (length == 1 && first == 0)
- return 0;
- if (length == 1 && first> 0)
- return 1;
- int numFirstDigit = 0;
- if (first> 1)
- numFirstDigit = PowerBase10(length - 1);
- else if (first == 1)
- numFirstDigit = atoi(strN + 1) + 1;
- int numOtherDigir = first * (length - 1) * PowerBase10(length - 2);
- int numRecursive = NumberOf1(strN + 1);
- return numFirstDigit + numOtherDigir + numRecursive;
- }
- int PowerBase10(unsigned int n)
- {
- int result = 1;
- for (unsigned int i = 0; i < n; ++i)
- result *= 10;
- return result;
- }
- };
牛客网 - 方法二
来源: http://www.bubuko.com/infodetail-3491701.html