算法集

１:不用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[m/2][n/2]与Ａ比较,这样的话会陷入麻烦.　可以取右上角的数与Ａ比较,如果比Ａ大则移除第n列,如果比Ａ小则移除第１行,然后再用剩下的右上角数与Ａ比较.　复杂度为ｍ+ｎ.
也可以用左下角的数与Ａ比较,但不能用左上角或右下角的数.

３:设计一个stack,实现pop() push() min()复杂度都是１
解:pop, push复杂度本来就是１, 可用辅助栈来实现min,　在向主栈push元素的时候,可比较当前push的元素与辅助栈顶元素比较,如果比栈顶元素小则push到辅助栈;在pop的时候,如果当前pop的元素和辅助栈顶元素相同则把辅助栈顶元素也pop掉.

４:如果两个单向链表(长度分别为m,n)有重合结点,求出复合结点,复杂度m+n
解:如果有重合结点,那么从重合结点后两个链表的所有结点都相同,定义两个指针P1,P2,让长的链表的指针先走|ｍ-ｎ|,然后两指针同时走.