[数据结构与算法]第一题 剑指offer 17

打印从1到最大的n位数

题目描述

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

示例1

输入: n = 1
输出: [1,2,3,4,5,6,7,8,9]

说明：

用返回一个整数列表来代替打印
n 为正整数

思路

第一天刷题，主要想跟着小队一起，从养成刷题习惯开始，选择一题简单的hello world级别的题目作为开胃菜，增强自己刷题的兴趣，刷题顺序的是按照剑指offer的电子书的内容出现的问题顺序的。

思路一：暴力解法

根据题目的描述，解法是很简单的，直接用暴力解法。

• 定义数组作为返回值
• 最大n位数： n=1 最大值为 9 ；n=2时，最大值为99 直接使用Math.pow(10,n)-1 即可直接取到最大的值
• 在[1-Math.pow(10,n))遍历数组赋值 即可解题

代码

/**
 * @param {number} n
 * @return {number[]}
 */
var printNumbers = function(n) {
    let a = [];
    for(let i=1; i<Math.pow(10,n);i++){
        a.push(i);
    }
    return a;

};

但是这种解法无法解决大数的问题，假如n=100的情况下，那就太顶了

思路二：字符串解法

使用字符串的方法，主要解解决：当n为大数，使用Math.pow函数无法得出的问题。
题目描述：n是位数，那么就可以知道最大值为 n个9 的组合

• 定义数组作为返回值
• 初始化字符串 max
• 根据n自减运算得到 max的值（最大值：但格式为字符串）
• 循环push进数组

代码

/**
 * @param {number} n
 * @return {number[]}
 */
var printNumbers = function(n) {
    let a = [];
    let max = "";
    while(n--){
        max += '9';
    }
    for(let i=1; i<= (max - '0' ); i++){
        a.push(i);
    }
    return a;

};

思路三 位运算

位运算方法在 数值的整数次方 中使用过，这一题也可以尝试一下

按位与 AND a & b： 在a,b的位表示中，每一个对应的位都为1则返回1， 否则返回0.
算术右移 a >> b： 把a的二进制表示向右移动b位，丢弃被移出的所有位.

使用位运算主要还是解决寻找最大数值 max 的问题

• n&1 如果n最右位是1，将当前m累乘到max
• m = m * m 确定二进制每右移一位 对应max增大的数值
  例如：
  输入：n=3
  n=3时 进入第一次循环 符合if判断条件 max = 110 ->m=100->n=01(二进制) n=1(十进制）
  n=1时 进入第二次循环 符合if判断条件 max=10100->m=1000-> n=00(二进制）n=0(十进制）
  跳出while循环

/**
 * @param {number} n
 * @return {number[]}
 */
var printNumbers = function(n) {
   let max = 1;
   let m = 10;
   let a = [];
   while(n){
       if(n & 1){
           max = max * m;
       }
       m = m * m;
       n = n >> 1;
   }

   for(let i = 1; i < max; i++){
       a.push(i);
   }
    return a;

};