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、给一个整数数组，求数组中重复出现次数大于数组总个数一半的数。
1 int MoreThanHalfNum(int *a , int n ) 2 { 3 int i , k , num = a[0]; 4 int times = 1; 5 for(i = 1 ; i < n ; ++i) 6 { 7 if(times == 0) 8 { 9 num = a[i]; 10 times = 1; 11 } 12 else if(a[i] != num) 13 --times; 14 else 15 ++times; 16 } 17 k = 0; 18 for(i = 0 ; i < n ; ++i) 19 { 20 if(a[i] == num) 21 ++k; 22 } 23 if(k*2 <= n) 24 return -1; //没有找到 25 else 26 return num; //找到 27 }
6、一个128bits 的二进制流，要求找出 里面包含 某8bits 二进制流的数目。
如果只是一个128bit的流，那就用int对其某个字节，然后移位比较，然后int向后移动3个字节，继续移位比较。如果是很多128bit的流，可以 模仿kmp，用上面的方法，每次取int的8bit和目标8bit进行AND操作，结果只有256种可能，事先存一个256的表，查表决定向后跳跃的 bit数。
7、交换整型的奇数位和偶数位
问题定义：
Write a program to swap odd and even bits in an integer with as few instructions as possible(e.g, bit 0 and bit 1 are swapped, bit 2 and bit 3 are swapped, etc)
1 int SwapOddEvenBit(int x) 2 { 3 return ( ((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1)); 4 } 5 int main(void) 6 { 7 int a = 171; 8 printf("%d\n", SwapOddEvenBit(a)); 9 return 0; 10 }
8、试着用最小的比较次数去寻找数组中的最大值和最小值。
扫描一次数组找出最大值；再扫描一次数组找出最小值。
比较次数2N-2
解法二：
将数组中相邻的两个数分在一组， 每次比较两个相邻的数，将较大值交换至这两个数的左边，较小值放于右边。
对大者组扫描一次找出最大值，对小者组扫描一次找出最小值。
比较1.5N-2次，但需要改变数组结构
解法三：
每次比较相邻两个数，较大者与MAX比较，较小者与MIN比较，找出最大值和最小值。
方法如下：先将一对元素互相进行比较，然后把最小值跟当前最小值进行比较，把最大值跟当前最大值进行比较。因此每两个元素需要3次比较。如果n为奇数，那么比较的次数是3*(n/2)次比较。如果n为偶数，那么比较的次数是3n/2-2次比较。因此，不管是n是奇数还是偶数，比较的次数至多是3*(n/2)，具体的代码如下：
1 void GetMaxAndMin(int *arr , int n , int &max , int &min) 2 { 3 int i = 0 ; 4 if(n & 1) // 奇数 5 { 6 max = min = arr[i++]; 7 } 8 else 9 { 10 if(arr[0] > arr[1]) 11 { 12 max = arr[0]; 13 min = arr[1]; 14 } 15 else 16 { 17 max = arr[1]; 18 min = arr[0]; 19 } 20 i += 2; 21 } 22 23 for( ; i < n ; i += 2) 24 { 25 if(arr[i] > arr[i+1]) 26 { 27 if(arr[i] > max) 28 max = arr[i]; 29 if(arr[i+1] < min) 30 min = arr[i+1]; 31 } 32 else 33 { 34 if(arr[i+1] > max) 35 max = arr[i+1]; 36 if(arr[i] < min) 37 min = arr[i]; 38 } 39 } 40 }
转自：http://blog.csdn.net/hackbuteer1/article/details/7581353#comments
微信公众号： 猿人谷
如果您认为阅读这篇博客让您有些收获，不妨点击一下右下角的【推荐】
如果您希望与我交流互动，欢迎关注微信公众号
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接。
