JZ-C-32

剑指offer第三十二题：从1到n整数中1出现的次数
  1 //============================================================================
  2 // Name        : JZ-C-32.cpp
  3 // Author      : Laughing_Lz
  4 // Version     :
  5 // Copyright   : All Right Reserved
  6 // Description : 从1到n整数中1出现的次数
  7 //============================================================================
  8 
  9 #include <iostream>
 10 #include <stdio.h>
 11 #include <string.h>
 12 #include <stdlib.h>
 13 using namespace std;
 14 
 15 // ====================方法一:未考虑时间效率，时间复杂度O(n*logn)====================
 16 int NumberOf1(unsigned int n);
 17 
 18 int NumberOf1Between1AndN_Solution1(unsigned int n) {
 19     int number = 0;
 20 
 21     for (unsigned int i = 1; i <= n; ++i)
 22         number += NumberOf1(i); //对每个数字都要做除法和求余运算
 23 
 24     return number;
 25 }
 26 
 27 int NumberOf1(unsigned int n) {
 28     int number = 0;
 29     while (n) {
 30         if (n % 10 == 1)
 31             number++;
 32 
 33         n = n / 10;
 34     }
 35 
 36     return number;
 37 }
 38 
 39 // ====================方法二：将数字分为两段，如21345分为从1到1345 和 1346到21345，时间复杂度O(logn)====================
 40 int NumberOf1(const char* strN);
 41 int PowerBase10(unsigned int n);
 42 
 43 int NumberOf1Between1AndN_Solution2(int n) {
 44     if (n <= 0)
 45         return 0;
 46 
 47     char strN[50];
 48     sprintf(strN, "%d", n); //把格式化的数据写入某个字符串，这里是将整数写入strN字符数组中
 49 
 50     return NumberOf1(strN);
 51 }
 52 
 53 int NumberOf1(const char* strN) {
 54     if (!strN || *strN < '0' || *strN > '9' || *strN == '')
 55         return 0;
 56 
 57     int first = *strN - '0';
 58     unsigned int length = static_cast<unsigned int>(strlen(strN));
 59 
 60     if (length == 1 && first == 0)
 61         return 0;
 62 
 63     if (length == 1 && first > 0)
 64         return 1;
 65 
 66     // 假设strN是"21345"
 67     // numFirstDigit是数字10000-19999的第一个位中1的数目
 68     int numFirstDigit = 0;
 69     if (first > 1)
 70         numFirstDigit = PowerBase10(length - 1);
 71     else if (first == 1)
 72         numFirstDigit = atoi(strN + 1) + 1;    //atoi函数：将字符串转成整数
 73 
 74     // numOtherDigits是01346-21345除了第一位之外的数位中1的数目
 75     int numOtherDigits = first * (length - 1) * PowerBase10(length - 2);    //★★
 76     // numRecursive是1-1345中1的数目
 77     int numRecursive = NumberOf1(strN + 1);
 78 
 79     return numFirstDigit + numOtherDigits + numRecursive;
 80 }
 81 
 82 int PowerBase10(unsigned int n) {
 83     int result = 1;
 84     for (unsigned int i = 0; i < n; ++i)
 85         result *= 10;
 86 
 87     return result;
 88 }
 89 
 90 // ====================测试代码====================
 91 void Test(char* testName, int n, int expected) {
 92     if (testName != NULL)
 93         printf("%s begins: 
", testName);
 94 
 95     if (NumberOf1Between1AndN_Solution1(n) == expected)
 96         printf("Solution1 passed.
");
 97     else
 98         printf("Solution1 failed.
");
 99 
100     if (NumberOf1Between1AndN_Solution2(n) == expected)
101         printf("Solution2 passed.
");
102     else
103         printf("Solution2 failed.
");
104 
105     printf("
");
106 }
107 
108 void Test() {
109     Test("Test1", 1, 1);
110     Test("Test2", 5, 1);
111     Test("Test3", 10, 2);
112     Test("Test4", 55, 16);
113     Test("Test5", 99, 20);
114     Test("Test6", 10000, 4001);
115     Test("Test7", 21345, 18821);
116     Test("Test8", 0, 0);
117 }
118 
119 int main(int argc, char** argv) {
120     Test();
121 
122     return 0;
123 }