JZ-C-32

剑指offer第三十二题:从1到n整数中1出现的次数

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注