2.1求8位二进制数中1的个数
解法1：直观法，每次除以2，计算余数为1的个数 O(log2v)
解法2：简单位操作，每次与0x01做与运算，再右移一位。O(log2v)
解法3：使用位操作v & (v-1) , 每次可减少二进制数字中的一个1。（若v & (v-1) == 0, 则v为2的方幂）
解法4：空间换时间，利用题目中字长8位的破绽，建立一个穷举数组。O(1)
知识点：位运算的性质
附：数组有2n+1个数，其中n个数成对出现，找出非成对出现的那个数。
数组所有元素做异或操作。
2.2
1.N!的末尾有多少个零
2.N!二进制表示中最低位1的位置
1.解法：质因数分解可知，0只有2*5可得，所以0的个数就是质因数分解中2的个数与5的个数的最小值，实际上就是
求5的个数Z。
Z= [N/5] + [N/5^2] +［N/5^3］+ ……
[N/5]表示不大于N的数中5的倍数贡献一个5
[N/5^2]表示不大于N的数中5^2再贡献一个5/。
2.解法：因为质因数分解中只有2是偶数，所以Z = [N/2] + [N/2^2] + [N/2^3] + …… +
2.3寻找多数元素问题
解法：减治：每次删除两个不同的ID,水王ID出现的次数仍旧会超过总数的一半。
2.4从1到N的所有数中“1”出现的个数
解法：寻找1出现的规律，比较复杂。
2.5寻找N个整数中最大的K个数
解法1：选择排序，选出最大的K个数。 O(n*k)
一点改进：部分堆排序，先建堆，再排出最大的k个数即可。O(n)+O(logn*k)
解法2：分治，利用快速排序的划分思路。O(n*log2k)
解法3：二分搜索（与《编程珠玑》第二章问题A思路类似），有两种划分方式：
1.设已知N个数中最小值Vmin，最大值Vmax，对区间[Vmin, Vmax]做二分即可。
2.设N个整数是M位长的。从最高位开始，按bi位0、1二分。
此解法适用于大数据量的处理，不过要多次读写若干个临时文件。
解法4：建一个最小堆存储K个数，堆顶为堆中最小值。
对第k到N个数，若A[i]大于堆顶H[0]，令H[0]=A[i]，再调用shift-down过程调整堆。
此解法非常适合于N值很大的情况，复杂度为O(n * log2k)
解法5：空间换时间，用count[Vmax]计算每个数字出现的次数。
如果Vmax很大，将[0, Vmax]分成m个小块，再分别讨论即可。
2.7最大公约数问题
用位运算求解
位运算问题：
1.求一个整数的二进制表示中1的个数
2.逆转一个整数的二进制表示问题
2.9斐波那契数列
·递归 效率最低
·迭代 O(n)
·矩阵分治法
2.14子数组之和的最大值
分治
动态规划
2.15子矩阵之和的最大值
固定一维，另一维转化为子数组之和的最大值问题
2.16求数组中最长递增字符列的长度
解法1：动态规划
假设array[]的前i个元素中，最长递增子序列的长度为LIS[i]，
则，LIS[i + １] = max{1, LIS[k]+1}, array[i+1] > array[k], for any k<=i
int LIS(int[] array) {
int[] LIS = new int[array.length];
for (int i = 0 ; i < array.length; i++) {
LIS[i] = 1;
for (int j = 0; j<i; j++) {
if (array[i] > array[j] && LIS[j] + 1 >LIS[i])
LIS[i] = LIS[j] + １;
}
}
}
O(N^2)的时间复杂度
解法2：
MLIS[i]定义为前i个元素中，以array[i]为最大元素的最长递增子序列的长度。
可以证明，MLIS[i]的最大值也是最终的结果。
MaxV[i]保存长度为i的递增子序列最大元素的最小值。
解法2的程序更新MaxV的部分应该是有问题的，由此导致时间复杂度的分析错误，并且解法3也是错误的。
2.17数组循环移位
void rightshift(int *arr, int N, int k) {
K %= N;
Reverse(arr, 0, N-k-1);
Reverse(arr, N-k, N-1);
Reverse(arr, 0, N-1);
}
数组问题思路：
排序思路
动态规划
看成一个数列或向量
2.18数组分割
3.1字符串移位包含的问题
给定两个字符串s1和s2，要求判定s2能否被s1做循环移位得到的字符串包含。例如：s1 = AABCD , s2 = CDAA，返回true. 给定s1 = ABCD 和 s2 = ACBD，返回false.
解法1：模拟字符串移位的过程，判断是否包含子串
解法2：判断s2是否为s1s1的子串即可。
解法3：不申请空间，模拟判断s2是否为s1s1子串的过程。
思路：字符串可以抽象成向量来考虑。
3.2电话号码对应英语单词
类似于求幂集问题
解法1：迭代，用while循环模拟
解法2：递归
3.3计算字符串相似度
递归求解
int calStrDis(char[] strA, int pABegin, int pAEnd,
char[] strB, int pBBegin, int pBEnd) {
if (pABegin > pAEnd) {
if (pBBegin > pBEnd) {
return 0;
} else {
return pBEnd - pBBegin + 1;
}
}
if (pBBegin > pBEnd) {
if (pABegin > pAEnd) {
return 0;
} else {
return pAEnd - pABegin + 1;
}
}
if (strA[pABegin] == strB[pBBegin]) {
return calStrDis(strA, pABegin + 1, pAEnd, strB,
pBBegin + 1, pBEnd);
} else {
int t1 = calStrDis(strA, pABegin, pAEnd, strB, pBBegin + 1,
pBEnd);
int t2 = calStrDis(strA, pABegin + 1, pAEnd, strB, pBBegin ,
pBEnd);
int t3 = calStrDis(strA, pABegin + 1, pAEnd, strB, pBBegin + 1 ,
pBEnd);
return min(t1, t2, t3) + 1;
}
}
递归优化，如何存储子问题的解？
3.4从无头链表中删除节点
这个问题很无耻
3.5最短摘要生成
有空再看
3.6编程判断两个链表是否相交
转化成链表是否有环的问题
3.7队列中取最大值操作
可分解为两个子问题
子问题1：设计一个堆栈，使入栈，出栈，取最大值的时间复杂度都是O(1)。
思路：用空间换时间，加一个数组link2NextMaxItem[]，link2NextMaxItem[i]存储的是前i个元素中最大值的下标。
子问题2：用上述特性的两个堆栈实现一个队列
堆栈A负责入队，堆栈B负责出队。当堆栈B空的时候，将堆栈A中的数据全部弹出并压入堆栈B
3.8 求二叉树结点之间的最大距离
动态规划实现，还是不太懂。
3.9重建二叉树
递归求解
3.10分层遍历二叉树
队列遍历二叉树+变量标记层次
3.11程序改错
编写正确的二分搜索程序
C代码：
int BinSearch(SeqList * R， int n , KeyType K )
{ //在有序表R[0..n-1]中进行二分查找，成功时返回结点的位置，失败时返回-1
int low=0，high=n-1，mid； //置当前查找区间上、下界的初值
if(R[low].key==K)
{
return 0 ;
}
while(low<=high){ //当前查找区间R[low..high]非空
mid=low+((high-low)/2)；//使用 (low + high) / 2 会有整数溢出的问题
if(R[mid].key==K)
{
return mid； //查找成功返回
}
if(R[mid].key>K)
high=mid-1; //继续在R[low..mid-1]中查找
else
low=mid+1； //继续在R[mid+1..high]中查找
}
return -1； //当low>high时表示查找区间为空，查找失败
} //BinSeareh
Java代码：
public static int binarySearch(int[] srcArray, int des)
{
int low = 0;
int high = srcArray.length-1;
while(low <= high) {
int middle = (low + high)/2;
if(des == srcArray[middle]) {
return middle;
}else if(des <srcArray[middle]) {
high = middle - 1;
}else {
low = middle + 1;
}
}
return -1;
}
4.8三角形测试用例
测试用例的三种类型：
正常输入 覆盖功能点
非法输入 值域错误 类型错误
边界值输入 0 1 MAX MIN