打印从1到最大的n位数
题目描述
输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。
示例：
输入: n = 1
输出: [1,2,3,4,5,6,7,8,9]
提示：
用返回一个整数列表来代替打印
n为正整数
题目分析
这题似乎没什么考点，因为他给出的限制太少了，如果是我出题，会有下面的出法：
- 卡时间，求出最大的数要算10^n，考点是要用快速幂快速求size
- 大数打印，一部分的数爆int甚至是爆long，可以用多个整型数来代表高低位来打印，或者用字符串
在这里我写了一个普通的getSize和用快速幂求解的getSize
快速幂
举个例子：
计算10^10
普通方法：10*10*....*10 一共计算十次乘法
快速幂法：10^10 = 10^5 * 10^5
这里只要计算一次105，然后平方就可，省去一次105的运算，但是增加了一次，以此类推，10^5 = 10^2 * 10^2 *10，显然，这可以看成是一个二分的过程，通过递归调用将大的幂运算分成小的幂运算，时间复杂度由O(N)下降到了O(logN)
class Solution {
fun printNumbers(n: Int): IntArray {
val size = simpleGetSize(n)
return IntArray(size-1){it+1}
}
//普通幂运算
fun simpleGetSize(n: Int):Int{
var size = 1
for(i in 0 until n){
size *= 10
}
return size
}
//递归法快速幂运算，计算m^n的时候，只需要将10替换成m
fun fastGetSize(n: Int):Int{
if(n == 1)
return 10
val tmp = fastGetSize(n/2)
if(n and 1 == 0){
return tmp * tmp
} else{
return tmp * tmp * 10
}
}
}
