「算法刷题」数学相关的LeetCode题目实现

[TOC]

一、实现指数函数pow

50. Pow(x, n)（中等函数）

剑指 Offer 16. 数值的整数次方（中等函数）

class Solution {
public:
    // x的n次幂等于n个x相乘,请注意，n可能为负数
    // 直接使用while循环，n非常大时会超时,所以需要用快速幂的位运算
    // 同时注意n可能是一个极大的负数，转换为long
    double myPow(double x, int n) {
        if(x==0.0f) return 0.0f;// 0的任何幂都设为0
        if(x==1.0f) return 1.0f;// 1的任何幂都设为1
        double res=1.0f;
        // 特殊情况:n为负数
        long b = n;//排除n为极大的负数
        if(b<0){
            x=1/x;
            b=-b;
        }
        // 快速幂算法的位运算版本
        while(b){
            if(b&1==1) res=res*x;//如果b是奇数，则res直接*x
            x=x*x;//x自乘
            b>>=1;//b右移1位，相当于/2
        }
        return res;
    }
};

二、n位数

剑指 Offer 17. 打印从1到最大的n位数（简单难度）

class Solution {
public:
    /*本题的难点在于n的增加，会让结果数组指数级增加：
    n=1，只有9个数；n=2，就有99个数；n=3，就有999个数
    所以n=n时，推理有n个9位数的数
    这道题返回一个int数组，测试数据也没有溢出
    如果让返回一个int数，可能存在溢出的情况，则难度会提升。
    */
    vector<int> printNumbers(int n) {
        // 计算需要多少个数
        int sum = 1;
        for (int i = 0; i < n; i++) sum *= 10;
        // 向结果数组中添加数字
        vector<int> res(sum - 1);
        for(int i = 0; i < sum - 1; i++) res[i] = i + 1;
        return res;
    }
};