刷题

打印从1到最大的n位数

scorlw 发布于

打印从1到最大的n位数

关键词：数学、递归、字符串、大数

题目描述

输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

示例 1：

1
2
输入: n = 1
输出: [1,2,3,4,5,6,7,8,9]

思路

思路一：

针对本题的常规思路，利用pow函数，秒解

思路二：

如果出现大数，则需要借助字符串进行求解。

有大数解法 char版和string版。

思路三：

递归求解

打印的其实是各个位上0-9的一个排列，所以可以采用递归的思想，一次给每个位赋值，赋值到个位（也就是第n位）时将其进行保存。

代码

思路一：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
	vector<int> printNumbers(int n) {
		vector<int> res;
		if (n == 0) return res;
		//打印到数组中
		for (int i=1,max=pow(10,n);i<max;i++)
		{
			res.push_back(i);
		}
		return res;
	}
};

思路二 char：

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
#include <iostream>
#include <vector>
#include <memory.h>
//#include <string.h>
//#include <cstring>

using namespace std;

vector<int> res;
bool Increment(char* number)  //形参传递char*指针，用于计算
{
    bool isOverflow = false;//检测是否越界
    int nTakeOver = 0;//存储进位
    int nLength = strlen(number);//长度为n,不是n+1
    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//非最高位有进位
            {
                nTakeOver = 1;
                number[i] = nSum - 10 + '0';//对第i位进行设置
            }
        }
        else//没有进位
            //设置第i位数字
            //并直接跳出循环
        {
            number[i] = nSum + '0';
            break;
        }
    }
    return isOverflow;
}
void PrintNumber(char* number)
//形参传递char*指针，此处改变形参number指向的位置，不会使原始的number指针所指位置改变
{
    string s = "";
    bool isBegin0 = true;
    while (*number != '\0')
    {
        //只有遇到第一位不为零的数才开始输出
        //只要开始输出，之后的0也会输出
        if (isBegin0 && *number != '0')
            isBegin0 = false;
        if (!isBegin0)
        {
            s += *number;
        }
        number++;
    }
    int num = stoi(s);//转为整数
    res.push_back(num);
}
vector<int> printNumbers(int n)
{
    if (n <= 0)
        return res;
    //创建一个能容纳最大值的字符数组,由于有一位要存储'\0'，因此要开大一格
    char* number = new char[n + 1];
    //初始全部设置为0
    memset(number, '0', n);
    number[n] = '\0';//第n位设为'\0'
    while (!Increment(number))
    {
        PrintNumber(number);
    }
    delete[]number;//注意要释放内存
    return res;
}

int main()
{
    vector<int> vec = printNumbers(3);
    for(int a : vec)
    {
        cout << a << " ";
    }
    cout << endl;
    return 0;
}

思路二 string：

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
#include <iostream>
#include <vector>

using namespace std;

vector<int> res;

bool Increment(string& number)
{
    //注意要使用引用传递，否则无法修改number
    bool isOverflow = false;//检测是否越界
    int nTakeOver = 0;//存储进位
    int nLength = number.size();
    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
            {
                nTakeOver = 1;
                number[i] = nSum - 10 + '0';//对第i位进行设置
            }
        }
        else//没有进位
            //设置第i位数字
            //并直接跳出循环
        {
            number[i] = nSum + '0';
            break;
        }
    }
    return isOverflow;
}
void saveNumber(string number)
//由于此处输出，不需要修改number，因此不需要加引用
{
    string s = "";
    bool isBegin0 = true;
    string::iterator it = number.begin();
    while (it != number.end())
    {
        if (isBegin0 && *it != '0')
            isBegin0 = false;
        if (!isBegin0)
        {
            s += *it;
        }
        it++;
    }
    int num = stoi(s);
    res.push_back(num);
}
vector<int> printNumbers(int n)
{
    if (n <= 0)
        return res;
    //创建一个能容纳最大值的字符数组
    string number(n, '0');
    //初始全部设置为0
    while (!Increment(number))
    {
        saveNumber(number);
    }
    return res;
}

int main()
{
    vector<int> vec = printNumbers(3);
    for(int i : vec){
        cout << i << " ";
    }
    cout << endl;
    return 0;
}

思路三：

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
#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<int> res;

//存储结果
void saveNumber(string number)
{
    bool isBegin0 = true;
    string tempStr = "";
    string::iterator it = number.begin();
    while(it != number.end())
    {
        if(isBegin0 && *it != '\0')
            isBegin0 = false;
        if(!isBegin0){
            tempStr += *it;
        }
        it++;
    }
    if(tempStr != ""){
        int tempNum = stoi(tempStr);
        res.push_back(tempNum);
    }
}

//赋值后面的位
void permutationNumbers(string& number, int length, int index)
{
    //如果赋值进行到最后一位，保存数据
    if(index == length){
        saveNumber(number);
        return;
    }
    else
    {
        //给各个位进行赋值
        for(int i = 0; i <= 9; i++)
        {
            number[index] = '0' + i;
            permutationNumbers(number, length, index + 1);
        }
    }
}

vector<int> printNumbers(int n)
{
    if(n <= 0) return res;
    string number(n, '0');
    for(int i = 0; i <= 9; i++){
        number[0] = i + '0';//number[0]代表的是最高位
        permutationNumbers(number, n, 1);
    }
    return res;
}

int main()
{
    vector<int> tst = printNumbers(3);
    for(int i : tst){
        cout << i << " ";
    }
    cout<<endl;
    return 0;
}

知识点

  1. pow函数的使用

    pow(base, exp)求解base的exp次方，包含于cmath头文件。

  2. 大数问题一般会考虑使用char或者string进行求解，通过设置越界标志和进位标志来辅助运算。

  3. stoi函数的使用

    stoi( const std::string& str, std::size_t* pos = 0, int base = 10 );

    舍弃所有空白符（以调用 isspace() 鉴别），直到找到首个非空白符，然后取尽可能多的字符组成底 n （其中 n=base ）的整数表示，并将它们转换成一个整数值。合法的整数值由下列部分组成：

    • (可选)正或负号
    • (可选)指示八进制底的前缀（ 0 ）（仅当底为 8 或 0 时应用）
    • (可选)指示十六进制底的前缀（ 0x 或 0X ）（仅当底为 16 或 0 时应用）
    • 一个数字序列

    底的合法集是 {0,2,3,…,36} 。合法数字集对于底 2 整数是 {0,1}，对于底3整数是 {0,1,2} ，以此类推。对于大于 10 的底，合法数字包含字母字符，从对于底 11 整数的 Aa 到对于底36整数的 Zz 。忽略字符大小写。