JZ-C-12

剑指offer第十二题:打印1到最大的n个数,”大数问题”

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
124
125
126
127
//============================================================================
// Name        : JZ-C-12.cpp
// Author      : Laughing_Lz
// Version     :
// Copyright   : All Right Reserved
// Description : 剑指offer第十二题:打印1到最大的n个数,"大数问题"
//============================================================================
 
#include <iostream>
#include <string.h>
#include  <memory>//memory是C++空间配置器以及new delete定义的头文件,里面定义了空间配置器,new delete以及一些用于调用构造函数的函数。
using namespace std;
 
void PrintNumber(char* number);
bool Increment(char* number);
void Print1ToMaxOfNDigitsRecursively(char* number, int length, int index);
 
void Print1ToMaxOfNDigits_1(int n) {
    if (n <= 0)
        return;
 
    char *number = new char[n + 1];
    memset(number, '0', n);
    number[n] = '\0';
 
    while (!Increment(number)) {
        PrintNumber(number);
    }
 
    delete[] number;
}
// 字符串number表示一个数字,在 number上增加1
// 如果做加法溢出,则返回true;否则为false
bool Increment(char* number) {
    bool isOverflow = false;
    int nTakeOver = 0;
    int nLength = strlen(number);
 
    for (int i = nLength - 1; i >= 0; i--) {
        int nSum = number[i] - '0' + nTakeOver;
        if (i == nLength - 1)
            nSum++;
 
        if (nSum >= 10) {
            if (i == 0)
                isOverflow = true;
            else {
                nSum -= 10;
                nTakeOver = 1;
                number[i] = '0' + nSum;
            }
        } else {
            number[i] = '0' + nSum;
            break;
        }
    }
 
    return isOverflow;
}
// ====================方法二====================
void Print1ToMaxOfNDigits_2(int n) {
    if (n <= 0)
        return;
 
    char* number = new char[n + 1];
    number[n] = '\0';
 
    for (int i = 0; i < 10; ++i) {
        number[0] = i + '0';
        Print1ToMaxOfNDigitsRecursively(number, n, 0);
    }
 
    delete[] number;
}
 
void Print1ToMaxOfNDigitsRecursively(char* number, int length, int index) {
    if (index == length - 1) {
        PrintNumber(number);//打印,结束一次循环
        return;
    }
 
    for (int i = 0; i < 10; ++i) {
        number[index + 1] = i + '0';//可以将整数转成字符
        Print1ToMaxOfNDigitsRecursively(number, length, index + 1);
    }
}
 
// ====================公共函数====================
// 字符串number表示一个数字,数字有若干个0开头
// 打印出这个数字,并忽略开头的0
void PrintNumber(char* number) {
    bool isBeginning0 = true;
    int nLength = strlen(number);
 
    for (int i = 0; i < nLength; ++i) {
        if (isBeginning0 && number[i] != '0')
            isBeginning0 = false;
 
        if (!isBeginning0) {
//            printf("%c", number[i]);
            cout << number[i];
        }
    }
 
//printf("\t");
    cout << " ";
}
 
// ====================测试代码====================
void Test(int n) {
//printf("Test for %d begins:\n", n);
    cout << "Test for " << n << " begins:" << endl;
    Print1ToMaxOfNDigits_1(n);
//    Print1ToMaxOfNDigits_2(n);
 
//printf("Test for %d ends.\n", n);
    cout << endl << "Test for " << n << " ends." << endl;
}
 
int main(int argc, char **argv) {
    Test(1);
    Test(2);
    Test(3);
    Test(0);
    Test(-1);
    return 0;
}

发表评论

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