专栏首页陌无崖知识分享【golang】剑指offer 最大n位数

【golang】剑指offer 最大n位数

作者 | 陌无崖

转载请联系授权

题目要求

打印一个n位的最大整数,如3位999,4位9999

思路一

分析题目可知n位的最大数一定是n个9组成,举例

n = 1时 max = 9
n = 2时 max = 9*10+9
n = 3时 max = 99*10+9
...

因此我们可以初始化一个9,循环n次即可,当然这里需要注意的是n>0

代码如下

func printMaxN(n int64) bool {
    if n <= 0 {
        fmt.Println(0)
        return false
    }
    // 求出最大的n位数 ,若n为3,则9 *10 +9 = 99 ,99 *10 +9
    sum := int64(9)
    for i := int64(0); i < n-1; i++ {
        sum = sum*10 + 9
    }
    fmt.Println(sum)
    return true
}

思路二

对于思路一,当我们试图让n = 19时,我们发现由于数据过大,产生了溢出,因此我们因该解决溢出,如果要求溢出后的结果打印出取值范围内的最大值,其中最大值为了提高效率,我们仍然采用之前学过的位操作符左移,判断是否移除,我们可以采用字符串长度的比较,我们可以对思路一修改代码如下;

func printMaxN_two(n int64) bool {
    if n <= 0 {
        fmt.Println(0)
        return false
    }

    // 求出int64的最大值 max := math.MaxInt64
    // 求最大值用左移操作符,提升效率,64位成2^62
    max := int64(1<<63 - 1)

    // 求出ma下对应的最大位数,先将max转换成sting
    smax := strconv.FormatInt(max, 10)
    maxn := len(smax)

    // 溢出时打印最大值
    if n >= int64(maxn) {
        // 将发生溢出
        fmt.Println(smax)
        return false
    }

    // 未溢出正常计算
    sum := int64(9)
    for i := int64(0); i < n-1; i++ {
        sum = sum*10 + 9
    }
    fmt.Println(sum)
    return true
}

思路三

如果题目要求溢出情况仍然求出最大值呢?这是就需要我们用字符串进行输出,可以发现,无论是否溢出,都可用转换成字符串的思路,n位最大的数,即包含了n个9的字符串,因此仍然采用该循环的方式

func printMaxN_three(n int64) bool {
    // 判断n是否未负数
    if n <= 0 {
        fmt.Println(0)
        return false
    }

    // 这种情况无论是否溢出都进行打印字符串形式
    str := ""
    for i := int64(0); i < n; i++ {
        str += "9"
    }
    fmt.Println(str)
    return true
}

思路四

基于上述的思路,基本都会用到循环,我们知道任何循环都可用递归的形式,递归结束的条件时n == 0,否则就在原始字符串的基础上追加9,代码如下:

func printMaxN_four(n uint64) (str string) {
    if n <= 0 {
        return ""
    } else {
        str += "9"
        n = n - 1
    }
    return str + printMaxN_four(n)
}

思路五

对于上述的思路,有一个共性就是只能打印出最大值,如果题目要求在打印最大值的基础上模拟数字的加法来计算呢?即我们在输出最大值的时候,控制台会依次打印出1,2,3,4,5….. 对于这个思路我们不防换一种思路求解,对于n位数中的每一位,都是对1~9的全排列,因此我们可以利用全排列+递归的解法,之前的文章已经阐述过相关全排列,这里我们只需要打印出n位数的每一位的全排列的组合即可,那么我们需要一个数组存放我们的n个数,初始化0,因此也就要求我们在打印的时候前面的0不需要进行打印,接着来看具体步骤:

1、初始化数组,从下标0开始进入递归 2、打印的条件为下标等于n 3、当打印的数组中为0的部分不打印 代码如下:

func Print1ToMaxOfDigits(n int) {
    if n <= 0 {
        return
    }
    number := make([]int, n)
    fmt.Println(number)
    for i := 0; i < 10; i++ {
        number[0] = i
        print1ToMaxOfDigitsRecursively(number, n, 0)
    }

}

func print1ToMaxOfDigitsRecursively(number []int, length int, index int) {
    if index == length-1 {
        printNumber(number)
        return
    }

    for i := 0; i < 10; i++ {
        number[index+1] = i
        print1ToMaxOfDigitsRecursively(number, length, index+1)
    }
}

func printNumber(number []int) {
    var isBeginning0 = true
    length := len(number)
    for i := 0; i < length; i++ {
        if isBeginning0 && number[i] != 0 {
            isBeginning0 = false
        }

        if !isBeginning0 {
            fmt.Printf("%d", number[i])
            if i == length-1 {
                fmt.Println()
            }
        }
    }
}

本文分享自微信公众号 - golang技术杂文(gh_ebbdb61f463e)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-01-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【剑指Offer】打印从1到最大的n位数

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

    Rochester
  • 剑指offer - 打印从 1 到最大的 n 位数 - JavaScript

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

    心谭博客
  • 【剑指Offer】17. 打印从1到最大的n位数

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

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

    https://leetcode-cn.com/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof/

    freesan44
  • 剑指OFFER之打印1到最大的N位数(九度OJ1515)

    题目描述: 给定一个数字N,打印从1到最大的N位数。 输入: 每个输入文件仅包含一组测试样例。 对于每个测试案例,输入一个数字N(1<=N<=5)。 输出: 对...

    用户1154259
  • 剑指Offer面试题:11.打印1到最大的n位数

      初看之下好像没有问题,但是其并没有考虑大数问题,有可能即使用整型(int)或长整型(long)都会溢出。

    Edison Zhou
  • 剑指Offer - 面试题17. 打印从1到最大的n位数

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

    Michael阿明
  • 剑指Offer LeetCode 面试题17. 打印从1到最大的n位数

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

    TrueDei
  • C++版 - 剑指Offer 面试题12:打印1到最大的N位数 题解

    九度OJ 1515 提交网址: http://ac.jobdu.com/submitpage.php?pid=1515&sid=1539822

    Enjoy233
  • 2020-11-15:手写代码:行有序、列也有序的二维数组中,找num...

    2020-11-15:手写代码:行有序、列也有序的二维数组中,找num,找到返回true,否则false?

    福大大架构师每日一题
  • 剑指 Offer(C++版本)系列:剑指 Offer 13 机器人的运动范围

    同步GitHub在此 ? https://github.com/TeFuirnever/GXL-Skill-Tree

    我是管小亮
  • 剑指Offer系列刷题笔记汇总

    版权声明:本文为博主原创文章,未经博主允许不得转载。个人网站:http://cuijiahua.com。 ...

    Jack_Cui
  • [剑指offer题解][Java]1到n整数中1出现的次数

    求出1 ~ 13的整数中1出现的次数,并算出100 ~ 1300的整数中1出现的次数?为此他特别数了一下1 ~ 13中包含1的数字有1、10、11、12、13因...

    Rude3Knife的公众号
  • [剑指offer题解][Java]1到n整数中1出现的次数

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    蛮三刀酱
  • 剑指 Offer(C++版本)系列:剑指 Offer 09 用两个栈实现队列

    同步GitHub在此 ? https://github.com/TeFuirnever/GXL-Skill-Tree

    我是管小亮
  • 【剑指Offer】60. n个骰子的点数

    使用一个二维数组 dp 存储点数出现的次数,其中 dp[i][j] 表示前 i 个骰子产生点数 j 的次数。

    瑞新
  • 【剑指offer题解】二维数组中的查找

    如果你和我一样是个算法菜鸡,那么最推荐的是先把剑指offer的题目搞明白,其次再去刷LeetCode等习题,这样对于面试突击非常有用,因为面试官最常考的算法题都...

    蛮三刀酱
  • 剑指 Offer(C++版本)系列:剑指 Offer 10- I 斐波那契数列

    同步GitHub在此 ? https://github.com/TeFuirnever/GXL-Skill-Tree

    我是管小亮
  • [剑指offer题解][Java]连续子数组的最大和

    由 N 个整数元素(有正数也有负数)组成的一维数组 (A[0], A[1],…,A[n-1], A[n]),这个数组有很多连续子数组,那么其中数组之和的最大值是...

    Rude3Knife的公众号

扫码关注云+社区

领取腾讯云代金券