剑指 Offer 2022/7/8

• 剑指 Offer 2022/7/8
• • 剑指 Offer 16. 数值的整数次方
  • 剑指 Offer 17. 打印从1到最大的n位数题干内容

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。

示例 1：
输入：x = 2.00000, n = 10
输出：1024.00000

示例 2：
输入：x = 2.10000, n = 3
输出：9.26100

示例 3：
输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25

代码思路

1. 快速幂算法
   迭代

class Solution:
    def myPow(self, x: float, n: int) -> float:
        def quickpow(x,n):
            res=1
            while n:
                if n&1:res*=x
                x*=x
                n>>=1
            return res
        return quickpow(x,n)if n >= 0 else 1.0 / quickpow(x,-n)

2. 思路2
   递归

class Solution:
    def myPow(self, x: float, n: int) -> float:
        def quickpow2(x,n):
            if not n: return 1
            y=quickpow2(x,n>>1)
            return y*y if n&1==0 else y*y*x
        return quickpow2(x,n)if n >= 0 else 1.0 / quickpow2(x,-n)

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

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

代码思路

1. python特性

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

2. 思路2
   这题显然是考大数问题
   参考题解：
   官方题解

class Solution:
    def printNumbers(self, n: int) -> [int]:
        def dfs(x):
            if x == n:
                s = ''.join(num[self.start:])
                if s != '0': res.append(int(s))
                if n - self.start == self.nine: self.start -= 1
                return
            for i in range(10):
                if i == 9: self.nine += 1
                num[x] = str(i)
                dfs(x + 1)
            self.nine -= 1
                num, res = ['0'] * n, []
        self.nine = 0
        self.start = n - 1
        dfs(0)
        return res