首页 > 代码库 > 笔试算法题(23):数值整数次方 & 最大对称子串

笔试算法题(23):数值整数次方 & 最大对称子串

出题:数值的整数次方(不考虑溢出),实现函数double Power(double base, int exponent);

分析:

  • 解法1:最简单的方法是使用直接的乘法运算,但是注意处理几种特殊情况:exponent为负数,base为0;
  • 解法2:将exponent分解成2的不同次方相加的表达式,通过重复平方来最大程度的减少乘法运算的次数。 当然,也可以递归实现,当n为偶数时,a^n=a^(n/2) * a^(n/2);当n为奇数时,a^n=a^((n-1)/2) * a^((n-1)/2) * a;

解题:

 1 double power(double base, int exponent) {
 2         if(base==0 && exponent<0) {
 3                 printf("when base is 0, exp cannot be negative");
 4                 return 0;
 5         }
 6         double product=1.0;
 7         if(exponent>0) {
 8                 for(int i=0;i<exponent;i++) {
 9                         product*=base;
10                 }
11         } else {
12                 for(int i=0;i>exponent;i--) {
13                         product*=1.0/base;
14                 }
15         }
16         return product;
17 }
18 
19 double power1(double base, int exp) {
20         if(base == 0) return 0;
21         if(exp == 0) return 1;
22 
23         double product=1.0, temp=1.0;
24         if(exp>0) {
25                 for(int i=exp;i>0;i/=2) {
26                         if(exp & 1 ==1) product*=base;
27                         base*=base;
28                 }
29         } else {
30                 exp=abs(exp);
31                 for(int i=exp;i>0;i/=2) {
32                         if(exp & 1 ==1) product*=1/base;
33                         base*=base;
34                 }
35         }
36         return product;
37 }

 

出题:输入一个字符串,判断是否有对称的子串,并输出最大的对称子串的长度;

分析:

  • 解法1:由于对称子串的最中间的两个字符相同,所以可以遍历判断两个相邻的字符是否相同,并且分别以两个字符为开始向前和向后拓展对称子串的长度,记录当 前最大的对称子串的长度,知道遍历完字符串。最优的时间复杂度为O(N),最差时间复杂度为O(N^2)。本实现没有考虑中心点对称(中间有一个字符), 仅考虑线对称(中心为两个字符);
  • 解法2:也就是判断回文,翻转拼接原始字符串,然后使用后缀数组可以在O(NlogN)的时间复杂度内完成;

解题:

 1 int SymmetricString(char *array, int length) {
 2         int left=0,right=1,max=0;
 3         int leftT,rightT,maxT;
 4         while(right<length) {
 5                 /**
 6                  * 外循环遍历整个字符串
 7                  * */
 8                 leftT=left;rightT=right;
 9                 maxT=0;
10                 while(leftT>=0 && rightT<length) {
11                         /**
12                          * 内循环以当前的left和right为起始
13                          * 分别向左右扩展对称字符串的长度
14                          * */
15                         if(array[leftT]==array[rightT]) {
16                                 maxT++;
17                                 leftT--;rightT++;
18                         } else
19                                 break;
20                 }
21                 /**
22                  * 更新最大对称字符串大小的记录
23                  * */
24                 if(maxT>max) max=maxT;
25                 left++;right++;
26         }
27         return 2*max;
28 }