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