首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >力扣 - 剑指 Offer 17. 打印从1到最大的n位数

力扣 - 剑指 Offer 17. 打印从1到最大的n位数

作者头像
冬夜先生
修改2021-10-20 10:25:26
2210
修改2021-10-20 10:25:26
举报
文章被收录于专栏:csicocsico

题目#

剑指 Offer 17. 打印从1到最大的n位数

思路1#

  • 如果有n位,那么最大值就是10n−110n−1,即如果n是2,那么最大就到输出到99
  • 考虑到大数情况,所以使用字符数组
  • 还要把字符数组转化成数字

代码#

class Solution {
    int position = 0;
    
    public int[] printNumbers(int n) {
        int count = 0;
        int[] res = new int[(int)Math.pow(10, n) - 1];

        char[] chars = new char[n];
        for (int i = 0; i < n; i++) {
            chars[i] = '0';
        }

        while (!increment(chars)) {
            convertNumber(chars, res);
        }

        return res;
    }

    public boolean increment(char[] chars) {
        // 是否溢出
        boolean isOverFlow = false;
        // 记录进位
        int takeOver = 0;
        int length = chars.length;

        for (int i = length-1; i >= 0; i--) {
            // 记得加上进位的值
            int sum = chars[i] - '0' + takeOver;
            // 确保每次只increment只增加1
            if (i == length-1) {
                sum++;
            }

            if (sum >= 10) {
                // 如果最高位的值还是大于等于10,说明溢出了
                if (i == 0) {
                    isOverFlow = true;
                    break;
                } else {
                    // 求余,记录进位,写回到数组中,然后进位继续加到下一位
                    sum -= 10;
                    takeOver = 1;
                    chars[i] = (char)('0' + sum);
                }
            } else {
                // 如果没有溢出,直接写入到数组中去即可
                chars[i] = (char)('0' + sum);
                break;
            }
        }
        return isOverFlow;
    }

    // 将字符数组转换成数字添加到结果集中
    public void convertNumber(char[] chars, int[] output) {
        // 用于判断的,不把0计入
        boolean isBeginning = false;
        int length = chars.length;
        StringBuilder sb = new StringBuilder();

        for (char c : chars) {
            if (!isBeginning && c != '0') {
                isBeginning = true;
            }
            if (isBeginning) {
                sb.append(c);
            }
        }
        output[position++] = Integer.parseInt(sb.toString());
    }
}

复杂度分析#

  • 时间复杂度:O(10N)O(10N)
  • 空间复杂度:O(N)O(N)

思路2#

  • n位的所有十进制数都是0~9的全排列
  • 排列的时候,最后还要考虑前面的0要去掉
  • 递归的结束条件就是我们已经排列到了第n位了

代码#

class Solution {
    int[] res;
    int position = 0;
    
    public int[] printNumbers(int n) {
        res = new int[(int)Math.pow(10, n) - 1];

        // 为了去掉无效的0,所以从第1位开始
        for (int digit = 1; digit <= n; digit++) {
            for (char first = '1'; first <= '9'; first++) {
                char[] num = new char[digit];
                num[0] = first;
                dfs(1, digit, num);
            }
        }

        return res;
    }

    public void dfs(int index, int length, char[] num) {
        if (index == length) {
            res[position++] = Integer.parseInt(String.valueOf(num));
            return;
        }

        for (char i = '0'; i <= '9'; i++) {
            num[index] = i;
            dfs(index+1, length, num);
        }
    }
}

复杂度分析#

  • 时间复杂度:O(10N)O(10N)
  • 空间复杂度:O(N)

本文系转载,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文系转载前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目#
  • 思路1#
    • 代码#
      • 复杂度分析#
      • 思路2#
        • 代码#
          • 复杂度分析#
          领券
          问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档