侧边栏壁纸
博主头像
神奇的程序员

今天的努力只为未来

  • 累计撰写 135 篇文章
  • 累计创建 25 个标签
  • 累计收到 32 条评论

目 录CONTENT

文章目录

打印从1到最大的n位数

神奇的程序员
2022-02-09 / 0 评论 / 0 点赞 / 30 阅读 / 2,978 字

大家好久不见呀,最近因为一些烦心事,学习不在状态,这篇文章本来年前就应该跟大家见面的,一耽搁就是半个月🌚 。经过一番调整走出来了,心态调整好了,后续将保持正常的学习进度🤗

前言

有一个数字n,我们需要按照顺序输出从1到最大的n位十进制数,例如:n = 3,则输出1、2、3…一直到最大的3位数999。

本文将将带着大家一起解决这个问题,分析解决思路与实现方法,欢迎各位感兴趣的开发者阅读本文。

循环解法

当我们过一眼这个问题后,脑海中想到的第一个思路肯定是:

  • 先求出这个最大的n位数
  • 用一个循环从1开始逐个打印至最大的n位数

很轻松就能写出如下所示的代码:

export default class PrintMaxNumber {
  // 通过遍历获取最大值
  public traverseForMax(n: number): void {
    let maxNumber = 1;
    let i = 0;
    while (i++ < n) {
      // 每次对结果*10,得出最小的n+1位的值
      maxNumber *= 10;
    }
    // 输出1到最大值-1位置的值,就是n位数的最大值
    for (let i = 1; i < maxNumber; i++) {
      console.log(i);
    }
  }
}

这段代码乍一看没啥问题,当n = 3的时候可以正常输出1~999之间的所有值,但是题目中n并没有规定具体范围,当n很大的时候,超出了js可以表示的最大范围,代码将无法运行。

排列解法

上述思路无法解决大数问题,接下来我们换一种思路来考虑这个问题。如果我们在数字前面补0,就会发现n位所有十进制数其实就是n个从0~9的全排列。也就是说,只要我们把数字的每一位都从0~9排列一遍,就得到了所有的十进制数。

全排列使用递归的方式很容易表达,数字的每一位都只可能是0~9中的一个数,然后设置下一位。递归结束的条件就是我们已经设置了数字的最后一位。

注意:对递归不了解的开发者,请移步我的另一篇文章:递归的理解与实现

接下来,我们来看下实现思路:

  • 准备一个数组用于描述数字的所有位数
  • 从0遍历至9,进入循环
    • 填充数字的最高位,即数组的0号元素
    • 调用递归函数,填充数组其他位置的元素,即除最大位外的其他位
  • 递归函数的实现
    • 接受三个参数:数字位数组、数字的总位数、当前位
    • 基线条件:当前位是最大位的前一位
    • 从0遍历至9,进入循环:
      • 计算下一位,填充数组下一位的值。
      • 继续执行递归函数

我们举个例子,通过一个图来描述下上述思路的执行过程,我们用n来描述所求位数,当n=3时,那么递归树就如下所示:

  • A控制百位,使用递归从0排列至9
  • B控制十位与个位,使用递归从0排列至9

image-20220209004401364

注意:A中的遍历永远只关注最高位数字的排列赋值,B中的遍历关注其它位数字的排列赋值。当执行栈中的B执行完时,则代表其他位已经排列到了9。此时A中的遍历就会继续执行,修改最高位的值。重复上述流程,直至A中的遍历结束,所有的数字也就排列完成了。

提取正确的数字

当递归的基线条件满足时,我们就需要将当前数字位数组中的值打印出来,我们在存储的时候给每一位数字的后面加多了一个0,我们打印时需要进一步处理,取出有效值即可,实现思路如下:

  • 通过遍历,取出数组中每一项字符串的第0号元素
  • 从取出的字符串中,从最高位开始遍历找到第一个非0数,将其存起来
  • 最后,输出存储的值即可。

实现代码

思路有了,理论也可行,那么代码就能轻松写出来了,如下所示:

export default class PrintMaxNumber {
  public maxNumberToStr(n: number): void {
    if (n <= 0) return;
    const numberStr: string[] = [];
    // 控制数字最高位的排列(0 ~ 9)
    for (let i = 0; i < 10; i++) {
      numberStr[0] = i + "0";
      this.printToMaxRecursively(numberStr, n, 0);
    }
  }

	/**
   * 递归获取最大值
   * @param numStr 数字位数组
   * @param length 数字位数
   * @param index 当前位
   * @private
   */
  private printToMaxRecursively(
    numStr: string[],
    length: number,
    index: number
  ): void {
    if (index === length - 1) {
      // 打印
      PrintMaxNumber.printNumber(numStr);
      return;
    }
    // 控制数字其他位的排列(0 ~ 9)
    for (let i = 0; i < 10; i++) {
      const nextIndex = index + 1;
      numStr[nextIndex] = i + "0";
      this.printToMaxRecursively(numStr, length, nextIndex);
    }
  }

  /**
   * 输出数字位数组中的有效数字
   * @param numStr
   * @private
   */
  private static printNumber(numStr: string[]): void {
    const nLength = numStr.length;
    let remove0Val = "";

    // 筛选除去多余0后的值
    // 假设此时的值是3位数,那么对应的数组就为["00","00","10"], 数组每一项值的第0位才是我们需要的值
    for (let i = 0; i < nLength; i++) {
      const strVal = numStr[i];
      // 取数组每一项的第0位
      remove0Val += strVal[0];
    }

    let finalVal = "";
    // 是否从0开始
    let isBeginning0 = true;
    // 筛选出第一个非0值的字符索引
    for (let i = 0; i < remove0Val.length; i++) {
      // 从0开始的状态为true且当前字符不为0
      if (isBeginning0 && remove0Val[i] !== "0") {
        // 表示我们已找到第一个非0数,修改状态
        isBeginning0 = false;
      }

      // 当前位的数非0,将其存起来
      if (!isBeginning0) {
        finalVal += remove0Val[i];
      }
    }
    if (finalVal !== "") {
      console.log(finalVal);
    }
  }
}

测试用例

接下来,我们来测试下当n = 3时,上述代码能否正常运行。

import PrintMaxNumber from "../PrintMaxNumber.ts";

const printNumber = new PrintMaxNumber();
printNumber.maxNumberToStr(3);

运行结果如下所示,符合预期。

image-20220209011016743

示例代码

本文所列举的完整示例代码请移步:

写在最后

至此,文章就分享完毕了。

我是神奇的程序员,一位前端开发工程师。

如果你对我感兴趣,请移步我的个人网站,进一步了解。

  • 文中如有错误,欢迎在评论区指正,如果这篇文章帮到了你,欢迎点赞和关注😊
  • 本文首发于神奇的程序员公众号,未经许可禁止转载💌
0

评论区