剑指offer（3）

发表于 | 分类于
本文总结剑指offer的编程题目，与使用C++实现的答案，快来挑战一下吧！

说明：本文题目来源于牛客网，答案分析参考《剑指offer》，包含个人理解，仅为参考。强烈大家去阅读《剑指offer》原书。

fengjingtu

数值的整数次方

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

注意

考虑exponent为负数的情况。

考虑base为0的情况。

选择以返回值，全局代码，或者异常的方式处理错误调用。

0的0此方没有意义，返回0还是1都是可以接受的。

使用高效的求平方算法。

判断double类型的数据是否相等的方式。

判断是否为基数。

求一个数的一半。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
public:
    bool error_power=false;//以全局变量返回输入出错的情况。调用者应该检查这个值是否为true。
    double Power(double base, int exponent) {
        error_power=false;
        /* 当base为0时，不能取倒数*/
        if(equel(base,0.0) && exponent<0 )
        {
            error_power=true;
            return 0.0;
        }
        unsigned int absExponent = (unsigned int )exponent;
        if(exponent < 0)
            absExponent=(unsigned int )(-exponent);
        double result=powerWithUnsignedExponent(base,absExponent);
        if(exponent <0)
            result=1.0/result;
        return result;

    }
    //使用优化方式。
    double powerWithUnsignedExponent(double base, unsigned int exponent)
    {
        if(exponent == 0)
        {
            return 1;
        }
        if(exponent == 1)
        {
            return base;
        }
        //n次方=（n/2）次方的平方。
        double result = powerWithUnsignedExponent(base ,exponent >> 1);
        result *=result;
        if((exponent & 0x1) == 1)//判断是否为奇数。
            result *= base;
        return result;
        
    }
    
    bool equel(double num1,double num2)
    {
        //由于精度问题，认为两个数相差0.0000001时，即为相等。
        if((num1-num2<0.0000001)&&(num1-num2>-0.0000001))
            return true;
        else
            return false;
    }
};

打印1到最大的n位数

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

注意

大数问题。

什么时候到达最大值。

递归使用全排列使代码简洁。

不要打印数字前面的0。

第一种思路：

1
2