1、打印汉诺塔移动步骤，并且计算复杂度。
方法是递归，将n-1层移到中间柱，然后将最底层移到目标柱，然后再把n-1层移到目标柱。
f(n) = 2f(n-1) + 1 , f(1) = 1
f(n) + 1 = 2( f(n-1) + 1 )
f(n) = 2^n - 1
T(n) = O(2^n);
2、计算两个字符串的是否相似（字符的种类，和出现次数相同）
先比较strlen，如果不相等，直接返回false
根据ASCII码建表 str[255],然后比较字符的出现次数，如有一个不同，返回false。
然后比较位置吧。有一个不同，就返回true。
3、定义二叉树，节点值为int，计算二叉树中的值在[a,b]区间的节点的个数。
任意一种方式遍历二叉树，如果值在 [a，b] 之间，计数器+1
4、一条路有k可坑，每次能跳平方数步长（1 4 9 16。。），不能跳到坑里，从a跳到b最少几步？（动态规划题）
动态转移方程
f（n） = min（ f(大于n的第一个平方数 -n) ，f（n- 小于n的第一个完全平方数） +１ ）
【 补充 ing
在一个坐标轴上， 给定两个点，一个起点，一个终点，起点有一个方块，方块可以左右移动，但是移动的长度只能是平方数长（1,4,9,16 ••••） ，同时坐标轴上还有洞，移动的过程中不能越过这个洞，不然会掉下去，问 由起点到终点 至少需要多少次移动，不能到达返回-1】
5、给一个整数数组，求数组中重复出现次数大于数组总个数一半的数。
- int MoreThanHalfNum(int *a , int n )
- {
- int i , k , num = a[0];
- int times = 1;
- for(i = 1 ; i < n ; ++i)
- {
- if(times == 0)
- {
- num = a[i];
- times = 1;
- }
- else if(a[i] != num)
- --times;
- else
- ++times;
- }
- k = 0;
- for(i = 0 ; i < n ; ++i)
- {
- if(a[i] == num)
- ++k;
- }
- if(k*2 <= n)
- return -1; //没有找到
- else
- return num; //找到
- }
6、一个128bits 的二进制流，要求找出 里面包含 某8bits 二进制流的数目。
如果只是一个128bit的流，那就用int对其某个字节，然后移位比较，然后int向后移动3个字节，继续移位比较。如果是很多128bit的流，可以模仿kmp，用上面的方法，每次取int的8bit和目标8bit进行AND操作，结果只有256种可能，事先存一个256的表，查表决定向后跳跃的bit数。
原文链接：http://blog.csdn.net/hackbuteer1/article/details/7581353