常用算法复习归纳

[TOC]

字符串算法

旋转字符串
把abcdef的ef放前面，变成efabcd

思路：摇手法，先把这两组分别旋转，再一起翻转。

dcba fe -> ef abcd

所以解题思路分两步

1，写一个通用的内部旋转方法。
```
reverseStr(s, from, to)
while(from<to)
    t=s[from]
    s[from++]=s[to]
    s[to--]=t
```
这个旋转使用了临时变量，也可以使用异或运算来**交换字符串**，不使用临时变量
2，利用摇手法三步完成。
包含字符串

aef是否在abcdefgA中，不用考虑次序，只考虑单个包含

思路：把长字符串映射到一个hashtable中

26个字母可以放到32位的int中，每个占一个次序的标识符

对每个字母遍历放入int a中
```
while(int i=0;i<s.length();i++)
    a |= 1<<(s[i]-'A');
```
这儿的**1«shift**是一个常用方法，把0x01左移用来代表某位的标示，这儿用位或运算|来忽略重复的情况
然后把要算的aef等字符转换成同样的int，取位与运算，若为0退出
回文判断，abcdcba这种

这种首先可以从两边向中间推进，两个指针，每次的值都应该相等。

然后用栈也行，先依次压入栈，出来的时候就是反向的，也应该等于原来的字符串。
栈的应用

栈先入后出，有对称的特性，所以可以处理这类问题，比如括号，引号这类。

处理路径/a/b/../c/d/../e/f，这种化简也用栈处理，先分隔，然后依次压栈，碰到..后，弹出栈顶的元素。
求最大回文字串，12212321

参考：

Manacher’s ALGORITHM: O(n)时间求字符串的最长回文子串

Longest Palindromic Substring Part II 最长回文子串

数组队列

寻找最小的K个数

一共有n个数，寻找最小的k个，无需排序

思路：先排序然后直接定位前k个？时间复杂度太高

其实只要找出前k个的kmax就行了，把比他小的找出来

先把n分成k块和n-k块

对前面k个数选出最大的，这时的时间复杂度为O(k)，最大值为kmax

然后用kmax和后面的n-k个数进行比对，当kmax<i，继续

当kmax>i，交换kmax和i，然后重新对前k个数排序，找出kmax

所以有O(k(n-k))=O(kn)
这类问题一般都是维持一个大小为k的容器来处理

查找排序

找出n个的数组中次数超过一半的数

思路：可以用hash，val=>次数，再遍历hash

或设两个临时值，candidate是值，ntimes是次数

遍历：

1，当前值赋给ca,nt为1

2，如果下一个也是它，则nT+1

如果不是，则nT-1

如果上面nT-1=0了，还需要把ca重新复制为当前值，nT=1

3，最后留下的就是超过半数的。
已知数组中找和为定值k的两个数

思路：1，用k-i得到互补的数组，然后遍历一个数组遍历另一个数组。

2，首先排序，O（NlogN）

然后有a[i]+a[j]=k

最开始i=0，j=n-1
```
while(i<j)
    if(a[i]+a[j]>k) j--;
    elseif(a[i]+a[j]<k) i++;
    else return;
```
这是一个常用的方法，这儿要意识到是个有序数组，从小到大，所以a[i]只能增大，a[j]只会减小，所以a[i]+a[j]>k，只有a[j]减小来实现，反之亦然。
n阶台阶，每次可挑1或2阶，共有多少种跳法。

思路：当n为1时，有一种，n为2时，有两种。

当n为3时，有两种情况，第一步为1阶或2阶，当第一步为1阶时，剩下的为f(2)种，当第一步为2阶，剩下的为f(1)种。

同理，n阶时，也只有第一步为1阶或2阶的情况，既有f(n)=f(n-1)+f(n-2)种。

即为一个斐波那契数列，调用递归解决。
```
fib(n)
    n<=2: return ret[n);
    else: return fib(n-1)+fib(n-2);
```

有序数组中找出某值是否存在。

思路：二分查找

i=0;j=n-1;
while(i<j)
    mid=i+(j-i)>>1
    if(a[mid]>k) j=mid-1;
    elseif(a[mid]<k) i=mid+1;
    else return mid;

这是个很经典的方法，两个指针，依次推进。

交集，智力题

1000瓶药，其中一个是毒药，只能试一次，最少多少老鼠可以试出。

思路：2^10=1024>1000，用二进制编号，从0000000001到1111101000，而毒药必在其中

0 0 0 0 0 0 0 0 0 1

0 0 0 0 0 0 0 0 1 0

….

0 0 0 1 0 1 0 0 1 0

…

1 1 1 1 1 0 1 0 0 0

这样共有10位，从上到下全部含有1的药混合起来给小鼠吃，若死了则毒药在其中，则该列为1.

全部测完可得到为1的编号，因为只有一瓶毒药，所以得到的二进制数字就是毒药编号。
约瑟夫问题