1:不用API,计算power(m, n)要求复杂度在logn
解:n个数相乘,复杂度是n,而logn是典型的折半思维,因此要想办法使每次计算次数减半,在while循环内,求n/2个m^2的和->求n/2/2个m^2^2的和->...
pseudo code:
long result = 1L;
while(n!=1){
if(n & 1 == 1){
result *= m;
}
m=m*m;
n=n/2;
}
这个题还可以通过递归.
2:a[m][n], 其中a[m][n+1] > a[n][n], a[m+1][n] > a[m][n],即一个矩形,右边的数比左边大,下边的数比上边的大.
求:给定一个数A,判断A是否存在于a中
解:不要想取a[m/2][n/2]与A比较,这样的话会陷入麻烦. 可以取右上角的数与A比较,如果比A大则移除第n列,如果比A小则移除第1行,然后再用剩下的右上角数与A比较. 复杂度为m+n.
也可以用左下角的数与A比较,但不能用左上角或右下角的数.
3:设计一个stack,实现pop() push() min()复杂度都是1
解:pop, push复杂度本来就是1, 可用辅助栈来实现min, 在向主栈push元素的时候,可比较当前push的元素与辅助栈顶元素比较,如果比栈顶元素小则push到辅助栈;在pop的时候,如果当前pop的元素和辅助栈顶元素相同则把辅助栈顶元素也pop掉.
4:如果两个单向链表(长度分别为m,n)有重合结点,求出复合结点,复杂度m+n
解:如果有重合结点,那么从重合结点后两个链表的所有结点都相同,定义两个指针P1,P2,让长的链表的指针先走|m-n|,然后两指针同时走.
分享到:
相关推荐
编程语言Python算法集大全 ,学习进步阶梯必备。编程语言Python算法集大全 ,学习进步阶梯必备。编程语言Python算法集大全 ,学习进步阶梯必备。编程语言Python算法集大全 ,学习进步阶梯必备。编程语言Python算法集...
C++算法,经典C++算法集经典C++算法集经典C++算法集经典C++算法集
算法集包括线性代数方程组(LU分解法、追赶法、奇异数分解、矩阵的QR分解)、数值积分(梯形求积法、反常积分、高斯求积法)、插值(拉格朗日插值、有理函数插值、三次样条插值、‘双三次样条插值)
Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法集题大全Java算法...
C语言算法集C语言算法集
《Visual C++常用数值算法集》一书的所有源代码 电子书有人传过了
Java 常用数值算法集Java 常用数值算法集Java 常用数值算法集Java 常用数值算法集Java 常用数值算法集Java 常用数值算法集
VC++常用数值算法集 一些常用的数学算法
C常用算法集(都是比较经典的算法 chm)
所有经典的算法,已经运行成功。排序C#经典排序算法集 所有经典的算法,已经运行成功。排序C#经典排序算法集 所有经典的算法,已经运行成功。
VC常用数值算法集 VC常用数值算法集 VC常用数值算法集
visual fortran常用数值算法集 囊括了大部分经典数值计算方法
C语言常用算法集 的源代码 徐士良
java 常用数值算法集b
数据结构常用算法集.chm 数据结构常用算法集.chm 非常方便
C语言常用算法集,里面有各种各样的常用算法的C语言版本。
不错的数据结构常用算法集,不过是英文的,大家自己斟酌再下吧!
C常用算法集, 非常实用!