专栏首页csico力扣 - 剑指 Offer 17. 打印从1到最大的n位数

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

题目#

剑指 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)

原文链接:https://www.cnblogs.com/linzeliang1222/p/15422209.html

我来说两句

0 条评论
登录 后参与评论

推荐阅读

  • Go Context解析 A Brief Inquiry Into Go Context

    Package context defines the Context type, which carries deadlines,

    takeonme.
    Go
  • Elasticsearch 7.10.1集群压测报告(16核64G*3 本地NVMe SSD,Intel)

    本文描述问题及解决方法同样适用于 腾讯云 Elasticsearch Service(ES)。

    岳涛
    大数据大数据解决方案ElasticsearchService压力测试
  • iOS开发:NSSet的使用

    集合和数组的相同点:都是存储不同元素的地址,不同点:NSSet中的元素都是被自动过滤之后的不会重复的元素,NSArray中的元素却是允许重复的;NSSet是一个无顺序的集合,NSArray是一个有顺序的集合。相对来说,NSSet的处理效率比NSArray的要快。

    三掌柜
    Vue.js
  • 新知 | RT-ONE™&TRTC赋能实时音视频场景创新

    ? 今年腾讯云音视频发布了“三合一”的RT-ONE™网络。该网络整合了腾讯云实时通信网络(TRTC)、即时通信网络(IM)以及流媒体分发网络(CDN)三张网络,为业界最完整的音视频通信PaaS平台构建基座,面向教育、零售、泛娱乐等行业需求提供服务。本次新知系列的第一堂课,我们邀请到了腾讯云音视频的技术导师 —— 刘连响,为大家详解RT-ONE™并分享RT-ONE™&TRTC赋能实时音视频场景的一些创新。 接下来的5周,每周四晚上7:30,我们都会在腾讯云音视频视频号、开源中国、InfoQ、51CTO、云

    腾讯云音视频
  • 【技术种草】我用 1个肉夹馍的钱,搭了整套大数据系统

    下面我分享一下如何用 1 个肉夹馍的钱来搭建一套云上的大数据平台。经过本人反复的钻研,发现薅羊毛这件事简直是太简单了。最后买 MySQL 19.9元,流计算 Oceanus(Flink) 1 元,花了二十几块钱,搭建了这样式的大数据系统。

    吴云涛
    流计算 OceanusElasticsearchServiceMySQL大数据解决方案Flink
  • 巧用 Flink 构建高性能 ClickHouse 实时数仓

    Apache Flink 是流式计算处理领域的领跑者。它凭借易用、高吞吐、低延迟、丰富的算子和原生状态支持等优势,多方位领先同领域的开源竞品。

    KyleMeow
    流计算 Oceanus云数据仓库 ClickHouseFlink
  • 【有奖课程互动-十一月期-配置平台】看视频,贴截图,知识打包,好学到饱

    知识赠与好学人,本期打包了蓝鲸CMDB使用视频汇总,每个视频都包含了该产品的基础使用功能,快来看看运维大牛们平时都是怎么使用蓝鲸CMDB的~

    腾讯蓝鲸助手
    云服务器运维解决方案运维
  • Sentinel 深度剖析 之 流量控制中算法

    Sentinel的流量控制是监控应用流量的 QPS 或 并发线程数等指标,当达到指定的阈值时对流量进行控制,以避免被瞬时的流量⾼峰冲垮,从而保证高可用。

    林淮川
    JavaSpring Cloud
  • GIF压缩小记

    广告素材中,图片类素材都是以静态图片为主,缺少交互感和吸引力,可能导致点击率偏低。为此,腾讯广告多媒体AI团队使用AI技术在图片焦点区域生成动态效果,以提升点击率。在落地页中,如果是以视频的形式不但交互过重,并且影响页面加载速度。因此,需要在保证展示效果的前提下使用压缩比尽可能大的GIF来做落地页展示。

    乾彪
  • 【技术种草】十分钟带你白嫖腾讯云个人专属云盘

    好消息,好消息,只需10分钟,手把手教你利用腾讯云COS存储+网盘cloudreve可以快速搭建个人专属网盘了

    乌龟哥哥
    轻量应用服务器 Lighthouse对象存储

扫码关注云+社区

领取腾讯云代金券