剑指offer 算法 （代码的完整性）

题目描述

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

class Solution { public:double Power(double base, int exponent) {if(equal(exponent,0.0)&&(exponent<0))//base为零 系数为负数return 0;unsigned int unexponent=(unsigned int) exponent;if(exponent<0)unexponent=(unsigned int) (-exponent);double result;result=powInput(base,unexponent);if(exponent<0)result=1.0/result;return result;}bool equal(double val1,double val2){if(((val1-val2)>-0.000001)&&((val1-val2)<0.000001))return true;elsereturn false;}double powInput(double base,int exponent){int i;double result=1.0;for(i=exponent;i>0;i--)result=base*result;return result;} };
题目描述

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

解析：(方法一)两个指针p1，p2；p1指向奇数，p2指向偶数，当p1指向的奇数在p2指向的偶数后时，保存p1的奇数，后移从p2开始到p1前一位的数组的数，把奇数赋给p2；p1，p2同时后移一位。直到p1指到数组尾（空间复杂度小）

class Solution { public:void reOrderArray(vector<int> &array) {int length = array.size();if(length == 0)return;int i;int *p1;//指向奇数int *p2;//指向偶数int cnt1=0;//p1指针移动次数int cnt2=0;//p2指针移动次数p1 = &array.at(0);//初始化 指向数组首元素p2 = &array.at(0);int temp1=0;//保存p1的奇数值while(!( ( *p1 == array.at(length-1) ) && ( *p2 == array.at(length-1) ) ) )//p1p2指向数字尾元素 退出循环{//printf("%d\t%d\r\n",cnt1,cnt2);while( ( ( *p1 & 0x1) == 0 ) && ( cnt1 < (length-1) ) )//p1指向偶数且不到数组尾 p1移动{p1++;cnt1++;}while( !( (*(p1+1) & 0x1) == 0 ) && ( cnt1 < (length-1) ) && (cnt1<=cnt2))//p1下一位指向奇数时 使p1指向最后一个奇数{p1++;cnt1++;}while( !( (*p2 & 0x1) == 0 ) && ( cnt2 < (length-1) ) )//p2指向奇数且不到数组尾 p2移动{p2++;cnt2++;}if( ( cnt1 < cnt2 ) && ( cnt1 < (length-1) ) )//若奇数在偶数前 p1继续向后移动{p1++;cnt1++;continue;}//此时p1指向乱序的第一个奇数 p2指向第一个偶数 p2在p1前面//保存p1位的奇数值 使p2开始往后到p1前的值全部往后移动一位 把保存的p1的奇数值赋给p2指向的位if(!(( *p1 & 0x1) == 0 ))//*p1是奇数{temp1 = *p1;for( i = cnt1 ; i > cnt2 ; i-- ){array.at(i) = array.at(i-1);//printf("%d:%d",i,array.at(i));}array.at(i)=temp1;}//printf("%d:%d",i,array.at(i));if(cnt1<(length-1)){p1++;cnt1++;}if(cnt2<(length-1)){p2++;cnt2++;}if(cnt1==(length-1)){if((( *p1 & 0x1) == 0 ))//数组尾时偶数 退出循环break;}}} };
解析：（方法二）用两个栈分别存奇偶数，在出栈先赋予数组奇数后偶数（时间复杂度小）

class Solution { public:void reOrderArray(vector<int> &array) {if(array.size()==0){return;}vector<int> odd;vector<int> even;for(int i=0;i<array.size();i++){if(array[i]%2==0){even.push_back(array[i]);}else{odd.push_back(array[i]);}}for(int i=0;i<odd.size();i++){array[i]=odd[i];}for(int i = odd.size();i<array.size();i++){array[i]=even[i-odd.size()];}} };

总结

以上是生活随笔为你收集整理的剑指offer 算法 （代码的完整性）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。