输入一个字符串,输出该字符串中对称的子字符串的最大长度。比如输入字符串 “google”,由于该字符串里最长的对称子字符串是“goog”,因此输出 4。
该题目比较直观的解法有：
还有后缀树也可以解，不过需要较大的空间，本文使用的是manacher算法：
Manacher最早发现了可以用O(n)的时间复杂度来解决该问题，所以这种方法称之为Manacher算法。
现在以查询字符串”abaab”为例，该算法为了将”aba”和”baab” 奇偶形式统一考虑，做了一个很精妙的预处理：每每两个字符串以及两端都加一个标志符号#，就形成了
“#a#b#a#a#b#”新字符串，那么”aba”则可以看做”#a#b#a#”，同时”baab”转为#b#a#a#b#”，就都为奇数形式了
题目:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个 排好序的数组的一个旋转,
输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转,该数 组的最小值为 1。
该题最容易想到的就是遍历，但是他的复杂度是O(n)，而作为面试题肯定是需要我们找出一种更优的方法
这里使用可以二分法来解决该问题,假设数组a的长度为n，现在使用二分法过程中左端索引s,右端索引t，则中间位置为m=s+(t-s)/2
首先可以知道旋转数组在旋转之后a[0]>a[n-1]是肯定成立的，
当a[s]<=a[m]的时候，我们应该进去右侧继续查找，比如a[0]
可以发现当a[s]<=a[t]的时候 a[s]肯定就是最小值了。
一个 int 数组,里面数据无任何限制,要求求出所有这样的数 a[i],其左边的数都小于等 于它,右边的数都大于等于它。能否只用一个额外数组和少量其它空间实现
想其他的都是泪（递归、分治）
最妙的方法就是将原数组排序得到b，如果b[i]=a[i]，则a[i]就是满足该条件的数
这样正好满足只使用了一个额外数组^_^
最终的复杂度为O(nlogn)
实现函数double Power(double base,int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大树问题。
这题看似简单，但是请别这么写-_-1
2
3
4
5
6
7
8double power(double base,int exp)
{
double result=1.0;
for(int i=1;i<=exp;i++)
result*=result;
return result;
}
还需要考虑：
输入一个正整数数组，将它们连接起来排成一个数，输出能排出的所有数字中最小的一个。例如输入数组{32, 321}，则输出这两个能排成的最小数字32132。请给出解决问题的算法，并证明该算法。
假如有两个数字a,b，其关键思路不是比较a,b，而是比较ab和ba。。。
如果ab<ba,则会有a<b，所以这题的关键就是构建a,b的比较器
不得不说，这个思路太妙了^_^
火车票 查询问题 针对12306设计一个快速的查询系统
这个网上看到的，好像是百度的一道面试题
思想就是将火车票区间的每个站按位映射，然后通过位操作法来查询，这种方式应该比较快，并且存储比较小
比如宁波到上海的高铁G7518有7个站：宁波->余姚北->绍兴北->杭州东->桐乡->嘉善南->上海虹桥
那么这趟车的一张票可以用0X7F来存储：01111111，低位表示出发，高位表示终止
那么我如果需要查询的话：查宁波到杭州东就为:00000111（第4站杭州东站只作为达到之用，不会占用其他票，所以置0即可），然后这两个数做一个与操作就可以，如果与操作之后的值还是00000111的话，就表示有票
还有购买的话 只需要做抑或操作即可,01111111^00000111=01111000，这样就表示余票就只有杭州东到上海虹桥的票了
题目
给定一个长度为N的数组，找出一个最长的单调自增子序列（不一定连续，但是顺序不能乱）。例如：给定一个长度为6的数组A{5， 6， 7， 1， 2， 8}，则其最长的单调递增子序列为{5，6，7，8}，长度为4.
此题面试中非常常见，其实比较简单，一般面试中不要慌，按条理来一般都能答出 ^_^
N长度的数组，关于最长递增子序列有max(l(i))=max(l(i-1)),i>1, a[i]>a[i-1]，这个关系式很重要
再来看假如N=1，那么l=1
如果N=2,有{16,24}，那么可以发现l=2，因为max(l(0))=1,24>16,所以max(l(1))=max(l(0))+1
好了，其实我们可以维护一个N的辅助数组，每个值表示在当前元素下考虑后面的元素可能组成的最长递增子序列,比如刚刚为N=2，有f[0]=2,f[1]=1
打印一个集合所有的子集和，比如{a,b,c}的子集和有{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}以及 空
一个元素个数为n的集合所包含的所有组合的子集个数有2^n个，这样其实就可以将所以集合的情况映射到0~2^n-1个，然后按位取元素即可
比如{a,b,c}这个三元素的集合按位映射
{0,0,0}=>空
{0,0,1}=>{c}
{0,1,0}=>{b}
{0,1,1}=>{b,c}
.
.
.
{1,1,1}=>{a,b,c}
奇数偶数分离 奇数在左侧 偶数在右侧 要求复杂度为O(N)
本题的难点主要是在O(N)复杂度的要求，但是想想有没有类似对数组左右分离的操作？
对，就是快速排序，在使用快速排序的分区中左边都是小于基准，右边都是大于基准
所以，同理，现在按照快排分区的思想，左边都是为奇数，右边都是为偶数，基数无论为奇偶皆可
从52张牌中随意取5张，看是否能组成顺子
其中1~k 表示1~13 大小王可以代替任意数字
首先可以将牌映射到数组上，然后将数组排序
在使用左右两端的指针向中间靠
如果左指针与接下来的值相差1或者接下来的值时大小王 则过到下一个
否则判断右指针是否有大小王 有的话右指针左移一位
