笔试算法题（23）：数值整数次方 & 最大对称子串
2024-08-30 18:39:18
出题：数值的整数次方（不考虑溢出），实现函数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；
解题：
double power(double base, int exponent) {
if(base== && exponent<) {
printf("when base is 0, exp cannot be negative");
return ;
}
double product=1.0;
if(exponent>) {
for(int i=;i<exponent;i++) {
product*=base;
}
} else {
for(int i=;i>exponent;i--) {
product*=1.0/base;
}
}
return product;
}
double power1(double base, int exp) {
if(base == ) return ;
if(exp == ) return ;
double product=1.0, temp=1.0;
if(exp>) {
for(int i=exp;i>;i/=) {
if(exp & ==) product*=base;
base*=base;
}
} else {
exp=abs(exp);
for(int i=exp;i>;i/=) {
if(exp & ==) product*=/base;
base*=base;
}
}
return product;
}
出题：输入一个字符串，判断是否有对称的子串，并输出最大的对称子串的长度；
分析：
- 解法1：由于对称子串的最中间的两个字符相同，所以可以遍历判断两个相邻的字符是否相同，并且分别以两个字符为开始向前和向后拓展对称子串的长度，记录当 前最大的对称子串的长度，知道遍历完字符串。最优的时间复杂度为O(N)，最差时间复杂度为O(N^2)。本实现没有考虑中心点对称（中间有一个字符）， 仅考虑线对称（中心为两个字符）；
- 解法2：也就是判断回文，翻转拼接原始字符串，然后使用后缀数组可以在O（NlogN）的时间复杂度内完成；
解题：
int SymmetricString(char *array, int length) {
int left=,right=,max=;
int leftT,rightT,maxT;
while(right<length) {
/**
* 外循环遍历整个字符串
* */
leftT=left;rightT=right;
maxT=;
while(leftT>= && rightT<length) {
/**
* 内循环以当前的left和right为起始
* 分别向左右扩展对称字符串的长度
* */
if(array[leftT]==array[rightT]) {
maxT++;
leftT--;rightT++;
} else
break;
}
/**
* 更新最大对称字符串大小的记录
* */
if(maxT>max) max=maxT;
left++;right++;
}
return *max;
}
最新文章
- MongoDB【第二篇】MongoDB逻辑与物理存储结构
- Infinite loop when using cookieless session ID on Azure
- Android studio快捷键大全 和 eclipse对照（原）
- ftp客户端命令使用简记
- jquery简单笔记(1) - 基础记录
- js中的 ！！
- redis web 客户端工具 redis-admin
- 猜拳 GuessFist
- DebugView图文教程
- SEO 网站URL优化
- ubuntu server配置xmanager
- GitHub上可能用到的开源
- JqGrid的总结大全【转】
- mplayer最全的命令
- SPARK 创建新任务
- 第一篇博客 ---- 分享关于Maven使用的一些技巧
- Node.js基础学习四之注册功能
- CRLF Injection漏洞的利用与实例分析
- mongodb从入门到精通
- 20155325 Exp4 恶意代码分析