一 数值的整数次方
题目描述：
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
问题解析：
这道题算是比较麻烦和难一点的一个了。我这里采用的是二分幂思想，当然也可以采用快速幂。
更具剑指offer书中细节，该题的解题思路如下：
1.当底数为0且指数<0时，会出现对0求倒数的情况，需进行错误处理，设置一个全局变量；
2.判断底数是否等于0，由于base为double型，所以不能直接用==判断
3.优化求幂函数（二分幂）。
当n为偶数，a^n =（a^n/2）*（a^n/2）；
当n为奇数，a^n = a^[(n-1)/2] a^[(n-1)/2] a。时间复杂度O(logn)
时间复杂度：O(logn)
示例代码：
public class Solution {
boolean invalidInput=false;
public double Power(double base, int exponent) {
//如果底数等于0并且指数小于0
//由于base为double型，不能直接用==判断
if(equal(base,0.0)&&exponent<0){
invalidInput=true;
return 0.0;
}
int absexponent=exponent;
//如果指数小于0，将指数转正
if(exponent<0)
absexponent=-exponent;
//getPower方法求出base的exponent次方。
double res=getPower(base,absexponent);
//如果指数小于0，所得结果为上面求的结果的倒数
if(exponent<0)
res=1.0/res;
return res;
}
//比较两个double型变量是否相等的方法
boolean equal(double num1,double num2){
if(num1-num2>-0.000001&&num1-num2<0.000001)
return true;
else
return false;
}
//求出b的e次方的方法
double getPower(double b,int e){
//如果指数为0，返回1
if(e==0)
return 1.0;
//如果指数为1，返回b
if(e==1)
return b;
//e>>1相等于e/2，这里就是求a^n =（a^n/2）*（a^n/2）
double result=getPower(b,e>>1);
result*=result;
//如果指数n为奇数，则要再乘一次底数base
if((e&1)==1)
result*=b;
return result;
}
}当然这一题也可以采用笨方法：累乘。不过这种方法的时间复杂度为O（n），这样没有前一种方法效率高。
// 使用累乘
public double powerAnother(double base, int exponent) {
double result = 1.0;
for (int i = 0; i < Math.abs(exponent); i++) {
result *= base;
}
if (exponent >= 0)
return result;
else
return 1 / result;
}二 调整数组顺序使奇数位于偶数前面
题目描述：
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
问题解析：
这道题有挺多种解法的，给大家介绍一种我觉得挺好理解的方法：
我们首先统计奇数的个数假设为n,然后新建一个等长数组，然后通过循环判断原数组中的元素为偶数还是奇数。如果是则从数组下标0的元素开始，把该奇数添加到新数组；如果是偶数则从数组下标为n的元素开始把该偶数添加到新数组中。
示例代码：
时间复杂度为O（n），空间复杂度为O（n）的算法
public class Solution {
public void reOrderArray(int [] array) {
//如果数组长度等于0或者等于1，什么都不做直接返回
if(array.length==0||array.length==1)
return;
//oddCount：保存奇数个数
//oddBegin：奇数从数组头部开始添加
int oddCount=0,oddBegin=0;
//新建一个数组
int[] newArray=new int[array.length];
//计算出（数组中的奇数个数）开始添加元素
for(int i=0;i<array.length;i++){
if((array[i]&1)==1) oddCount++;
}
for(int i=0;i<array.length;i++){
//如果数为基数新数组从头开始添加元素
//如果为偶数就从oddCount（数组中的奇数个数）开始添加元素
if((array[i]&1)==1)
newArray[oddBegin++]=array[i];
else newArray[oddCount++]=array[i];
}
for(int i=0;i<array.length;i++){
array[i]=newArray[i];
}
}
}欢迎关注我的微信公众号（分享各种Java学习资源，面试题，以及企业级Java实战项目回复关键字免费领取）：
