【一刷《剑指Offer》】面试题 12:打印 1 到最大的 n 位数

简介: 【一刷《剑指Offer》】面试题 12:打印 1 到最大的 n 位数

力扣对应题目链接:LCR 135. 报数 - 力扣(LeetCode)

牛客对应题目链接:打印从1到最大的n位数_牛客题霸_牛客网 (nowcoder.com)


一、《剑指Offer》内容


二、分析题目

1、暴力解法


2、用字符串模拟数字加法

  • 首先要考虑当 n 很大时(比如:100),打印出来的数很有可能是超过 INT_MAX 的范围,所以我们用字符串来表示每个数。
  • 当然,在这一题中,由于返回的是一个 int 型的数组,所以是不可能超过 INT_MAX 的,但是一般大数问题都不会要求返回 int 数组来保存每一位数,而是循环输出每一位数。
  • 思路:假设 n=3,定义一个字符串,初始化为 "000",然后用它来循环模拟从 1 到最大的 n 位数,并循环保存到 int 数组中(在真实情况下则是循环输出)。

3、递归全排列解法

假设 n=3,要输出的数其实就是三位数的全排列(000,001,002,...,999。注意:000 不能输出),用递归来表示出这个过程即可。


三、代码

1、暴力解法

//写法一
class Solution {
private:
    vector<int> res;
public:
    vector<int> countNumbers(int cnt) {
        int n=1;
        while(cnt--)
            n*=10;
        for(int i=1; i<n; i++)
            res.push_back(i);
        return res;
    }
};
 
//写法二
class Solution {
private:
    vector<int> res;
public:
    vector<int> countNumbers(int cnt) {
        for(int i=1; i<pow(10, cnt); i++)
            res.push_back(i);
        return res;
    }
};
 
//写法三
class Solution {
private:
    vector<int> res;
public:
    vector<int> countNumbers(int cnt) {
        string maxValue;
        while(cnt--)
            maxValue+='9';
        for(int i=1; i<=stoi(maxValue); i++)
            res.push_back(i);
        return res;
    }
};

2、用字符串模拟数字加法

class Solution {
private:
    vector<int> res;
public:
    bool increment(string& s)
    {
        bool isOverflow = false;
        int carry = 0;
        for (int i = s.size() - 1; i >= 0; i--)
        {
            int cur = s[i] - '0' + carry;
            if (i == s.size() - 1)
                cur++;
            if (cur >= 10)
            {
                if (i == 0)
                    isOverflow = true;
                else
                {
                    carry = 1;
                    s[i] = cur - 10 + '0';
                }
            }
            else
            {
                s[i] = cur + '0';
                break;
            }
        }
        return isOverflow;
    }
    void printNumbers(string& s)
    {
        bool isBeginningZero = true;
        string tmp;
        for (int i = 0; i < s.size(); i++)
        {
            if (isBeginningZero && s[i] != '0')
                isBeginningZero = false;
            if (!isBeginningZero)
                tmp += s[i];
        }
        res.push_back(stoi(tmp));
    }
    vector<int> countNumbers(int cnt) {
        if (cnt <= 0) return res;
        string s(cnt, '0');
        while (!increment(s))
            printNumbers(s);
        return res;
    }
};

3、递归全排列解法

class Solution {
private:
    vector<int> res;
public:
    void printNumbers(string& s)
    {
        bool isBeginningZero = true;
        string tmp;
        for (int i=0; i<s.size(); i++)
        {
            if(isBeginningZero && s[i]!='0')
                isBeginningZero=false;
            if(!isBeginningZero)
                tmp+=s[i];
        }
        if(tmp!="") res.push_back(stoi(tmp));
    }
    void permutation(string& s, int length, int index)
    {
        if(index==length-1)
        {
            printNumbers(s);
            return;
        }
        for(int i=0; i<10; i++)
        {
            s[index+1]=i+'0';
            permutation(s, length, index+1);
        }
    }
    vector<int> countNumbers(int cnt) {
        if(cnt<=0) return res;
        string s(cnt, '0');
        for(int i=0; i<10; i++)
        {
            s[0]=i+'0';
            permutation(s, cnt, 0);
        }
        return res;
    }
};

四、扩展

在前面的代码中,我们都是用一个 char 型字符表示十进制数字的一位。8 个 bit 的 char 型字符最多能表示 256 个字符,而十进制数字只有 0~9 的 10 个数字。因此用 char 型字符串来表示十进制的数字并没有充分利用内存,造成了一些浪费。

有没有更高效的方式来表示大数?

通过使用 string 进行求解(上面的方法都可以转换成 string 来求解,下面写一个 dfs)。

  • 第一层遍历 n,1 位数、2 位数、3 位数...
  • 因为第一位数不能取 0,所以第一位数单独拉出来遍历,故第二层遍历 1~9,代表第一位数只能取 1~9
  • 然后 dfs,遍历 2~n 的每一位数字,取值范围 0~9

注意:无需回溯,因为保存结果的是 string,不用引用传递就行。

dfs 的过程:

  • k 表示当前是第 k 个位置,当 k=n 时,dfs 终止,将 string 保存。
  • 当前位置可选 0~9,然后 dfs 下一个位置。
//大数解法(dfs)
class Solution {
private:
    vector<int> res;
public:
    void dfs(int k, int n, string s)
    {
        if(k==n)
        {
            res.push_back(stoi(s));
            return;
        }
        for(int i=0; i<10; i++)
            dfs(k+1, n, s+to_string(i));
    }
    vector<int> countNumbers(int cnt) {
        for(int i=1; i<=cnt; i++)
            for(int j=1; j<10; j++)
                dfs(1, i, to_string(j));
        return res;
    }
};

五、相关题目

定义一个函数,在该函数中可以实现任意两个整数的加法。由于没有限定输入两个数的大小范围,我们也要把它当作大数来处理。在第一个思路中,实现了在字符串表示的数字上加 1 的功能,可以参考这个思路实现两个数字的相加功能。另外还有一个需要注意的问题:

如果输入的数字中有负数,我们应该怎么去处理?

通常对于大数问题,常用的方法就是使用字符串来表示这个大数。可以先将两个整数分别用字符串来表示,然后分别将这两个字符串拆分成对应的字符数组。当两个整数都是正数的时候直接相加结果为正数,同为负数的时候取两者的绝对值相加然后在结果前加一个负号。如果是一正一负,则用两者的绝对值相减,用绝对值大的数减去绝对值小的数,当正数的绝对值大的时候相减的结果为正数,当负数的绝对值大的时候相减的结果为负数,结果为负数时在相减的结果前加一个负号即可。在具体进行相加的时候两个字符数组对应的数字字符相加即可,当有进位的时候做出标记,在更高一位进行相加时再将这个进位加进去。

tips:如果面试题是关于 n 位的整数并且没有限定 n 的取值范围,或者是输入任意大小的整数,那么这个题目很有可能是需要考虑大数问题的。字符串是一个简单、有效的表示大数的方法。


相关文章
|
2月前
【一刷《剑指Offer》】面试题 23:从上往下打印二叉树
【一刷《剑指Offer》】面试题 23:从上往下打印二叉树
|
2月前
【一刷《剑指Offer》】面试题 22:栈的压入、弹出系列
【一刷《剑指Offer》】面试题 22:栈的压入、弹出系列
|
2月前
|
算法
【一刷《剑指Offer》】面试题 21:包含 main 函数的栈
【一刷《剑指Offer》】面试题 21:包含 main 函数的栈
|
2月前
【一刷《剑指Offer》】面试题 20:顺时针打印矩阵
【一刷《剑指Offer》】面试题 20:顺时针打印矩阵
|
2月前
【一刷《剑指Offer》】面试题 19:二叉树的镜像
【一刷《剑指Offer》】面试题 19:二叉树的镜像
|
2月前
【一刷《剑指Offer》】面试题 18:树的子结构
【一刷《剑指Offer》】面试题 18:树的子结构
|
2月前
【一刷《剑指Offer》】面试题 17:合并两个排序的链表
【一刷《剑指Offer》】面试题 17:合并两个排序的链表
|
2月前
【一刷《剑指Offer》】面试题 16:反转链表
【一刷《剑指Offer》】面试题 16:反转链表
|
2月前
【一刷《剑指Offer》】面试题 15:链表中倒数第 k 个结点
【一刷《剑指Offer》】面试题 15:链表中倒数第 k 个结点
|
2月前
|
C++
【一刷《剑指Offer》】面试题 14:调整数组顺序使奇数位于偶数前面
【一刷《剑指Offer》】面试题 14:调整数组顺序使奇数位于偶数前面