(3)剑指Offer之数值的整数次方和调整数组元素顺序
一 数值的整数次方
题目描述:
给定一个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实战项目回复关键字免费领取):
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
(2)剑指Offer之二维数组查找和替换空格问题
一 二维数组查找 题目描述: 在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。 问题解析: 这一道题还是比较简单的,我们需要考虑的是如何做,效率最快。这里有一种很好理解的思路: 矩阵是有序的,从左下角来看,向上数字递减,向右数字递增, 因此从左下角开始查找,当要查找数字比左下角数字大时。右移 要查找数字比左下角数字小时,上移。这样找的速度最快。 示例代码: public boolean Find(int target, int [][] array) { //基本思路从左下角开始找,这样速度最快 int row = array.length-1;//行 int column = 0;//列 //当行数大于0,当前列数小于总列数时循环条件成立 while((row >= 0)&& (column< array[0].length)){ if(array[row][column] > target){ row--; }else if(arr...
- 下一篇
(4)剑指Offer之链表相关编程题
一 链表中倒数第k个节点 题目描述: 输入一个链表,输出该链表中倒数第k个结点 问题分析: 一句话概括:两个指针一个指针p1先开始跑,指针p1跑到k-1个节点后,另一个节点p2开始跑,当p1跑到最后时,p2所指的指针就是倒数第k个节点。 思想的简单理解:前提假设:链表的结点个数(长度)为n。规律一:要找到倒数第k个结点,需要向前走多少步呢?比如倒数第一个结点,需要走n步,那倒数第二个结点呢?很明显是向前走了n-1步,所以可以找到规律是找到倒数第k个结点,需要向前走n-k+1步。算法开始: 设两个都指向head的指针p1和p2,当p1走了k-1步的时候,停下来。p2之前一直不动。 p1的下一步是走第k步,这个时候,p2开始一起动了。至于为什么p2这个时候动呢?看下面的分析。 当p1走到链表的尾部时,即p1走了n步。由于我们知道p2是在p1走了k-1步才开始动的,也就是说p1和p2永远差k-1步。所以当p1走了n步时,p2走的应该是在n-(k-1)步。即p2走了n-k+1步,此时巧妙的是p2正好指向的是规律一的倒数第k个结点处。这样是不是很好理解了呢? 考察内容: 链表+代码的鲁棒性 示例...
相关文章
文章评论
共有0条评论来说两句吧...