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

笔试算法题（23）：数值整数次方 & 最大对称子串

2024-07-05 14:34:17   226人阅读

出题：数值的整数次方（不考虑溢出），实现函数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 }

 


联系
我们