LeetCode 剑指 Offer——数值的整数次方、打印从1到最大的n位数

数值的整数次方

实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。

示例1：

输入: 2.00000, 10
输出: 1024.00000

示例2：

输入: 2.10000, 3
输出: 9.26100

示例3：

输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25

说明：

-100.0 < x < 100.0
n 是 32 位有符号整数，其数值范围是 [−2^31, 2^31 − 1] 。

代码：

class Solution:
    def myPow(self, x: float, n: int) -> float:
        res = 1
        if n < 0:
            x, n = 1 / x, -n
        while n != 0:
            if n % 2 == 0:
                x *= x
                n /= 2
            else:
                res *= x
                n -= 1
        return res

这一题假如一个一个去乘，时间复杂度O(n)，太慢了。

因为是算整数次方，可以考虑如下方法：

• 如果指数为偶数，可以让底数平方，指数减半
• 如果指数为奇数，可以让结果先乘一个数，指数减1

时间复杂度O(logn)，空间复杂度O(1)

打印从1到最大的n位数

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

示例 1:

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

说明：

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

代码：

class Solution:
    def printNumbers(self, n: int) -> List[int]:
        res = []
        for i in range(1, 10 ** n):
            res.append(i)
        return res

Python不考虑大数问题，代码比较简单。

时间复杂度O(10^n)，空间复杂度O(1)。