2.1求8位二進(jìn)制數(shù)中1的個(gè)數(shù)
解法1：直觀法，每次除以2，計(jì)算余數(shù)為1的個(gè)數(shù) O(log2v)
解法2：簡(jiǎn)單位操作，每次與0x01做與運(yùn)算，再右移一位。O(log2v)
解法3：使用位操作v & (v-1) , 每次可減少二進(jìn)制數(shù)字中的一個(gè)1。（若v & (v-1) == 0, 則v為2的方冪）
解法4：空間換時(shí)間，利用題目中字長(zhǎng)8位的破綻，建立一個(gè)窮舉數(shù)組。O(1)
知識(shí)點(diǎn)：位運(yùn)算的性質(zhì)
附：數(shù)組有2n+1個(gè)數(shù)，其中n個(gè)數(shù)成對(duì)出現(xiàn)，找出非成對(duì)出現(xiàn)的那個(gè)數(shù)。
數(shù)組所有元素做異或操作。
2.2
1.N!的末尾有多少個(gè)零
2.N!二進(jìn)制表示中最低位1的位置
1.解法：質(zhì)因數(shù)分解可知，0只有2*5可得，所以0的個(gè)數(shù)就是質(zhì)因數(shù)分解中2的個(gè)數(shù)與5的個(gè)數(shù)的最小值，實(shí)際上就是
求5的個(gè)數(shù)Z。
Z= [N/5] + [N/5^2] +［N/5^3］+ ……
[N/5]表示不大于N的數(shù)中5的倍數(shù)貢獻(xiàn)一個(gè)5
[N/5^2]表示不大于N的數(shù)中5^2再貢獻(xiàn)一個(gè)5/。
2.解法：因?yàn)橘|(zhì)因數(shù)分解中只有2是偶數(shù)，所以Z = [N/2] + [N/2^2] + [N/2^3] + …… +
2.3尋找多數(shù)元素問(wèn)題
解法：減治：每次刪除兩個(gè)不同的ID,水王ID出現(xiàn)的次數(shù)仍舊會(huì)超過(guò)總數(shù)的一半。
2.4從1到N的所有數(shù)中“1”出現(xiàn)的個(gè)數(shù)
解法：尋找1出現(xiàn)的規(guī)律，比較復(fù)雜。
2.5尋找N個(gè)整數(shù)中最大的K個(gè)數(shù)
解法1：選擇排序，選出最大的K個(gè)數(shù)。 O(n*k)
一點(diǎn)改進(jìn)：部分堆排序，先建堆，再排出最大的k個(gè)數(shù)即可。O(n)+O(logn*k)
解法2：分治，利用快速排序的劃分思路。O(n*log2k)
解法3：二分搜索（與《編程珠璣》第二章問(wèn)題A思路類似），有兩種劃分方式：
1.設(shè)已知N個(gè)數(shù)中最小值Vmin，最大值Vmax，對(duì)區(qū)間[Vmin, Vmax]做二分即可。
2.設(shè)N個(gè)整數(shù)是M位長(zhǎng)的。從最高位開始，按bi位0、1二分。
此解法適用于大數(shù)據(jù)量的處理，不過(guò)要多次讀寫若干個(gè)臨時(shí)文件。
解法4：建一個(gè)最小堆存儲(chǔ)K個(gè)數(shù)，堆頂為堆中最小值。
對(duì)第k到N個(gè)數(shù)，若A[i]大于堆頂H[0]，令H[0]=A[i]，再調(diào)用shift-down過(guò)程調(diào)整堆。
此解法非常適合于N值很大的情況，復(fù)雜度為O(n * log2k)
解法5：空間換時(shí)間，用count[Vmax]計(jì)算每個(gè)數(shù)字出現(xiàn)的次數(shù)。
如果Vmax很大，將[0, Vmax]分成m個(gè)小塊，再分別討論即可。
2.7最大公約數(shù)問(wèn)題
用位運(yùn)算求解
位運(yùn)算問(wèn)題：
1.求一個(gè)整數(shù)的二進(jìn)制表示中1的個(gè)數(shù)
2.逆轉(zhuǎn)一個(gè)整數(shù)的二進(jìn)制表示問(wèn)題
2.9斐波那契數(shù)列
·遞歸 效率最低
·迭代 O(n)
·矩陣分治法
2.14子數(shù)組之和的最大值
分治
動(dòng)態(tài)規(guī)劃
2.15子矩陣之和的最大值
固定一維，另一維轉(zhuǎn)化為子數(shù)組之和的最大值問(wèn)題
2.16求數(shù)組中最長(zhǎng)遞增字符列的長(zhǎng)度
解法1：動(dòng)態(tài)規(guī)劃
假設(shè)array[]的前i個(gè)元素中，最長(zhǎng)遞增子序列的長(zhǎng)度為L(zhǎng)IS[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)的時(shí)間復(fù)雜度
解法2：
MLIS[i]定義為前i個(gè)元素中，以array[i]為最大元素的最長(zhǎng)遞增子序列的長(zhǎng)度。
可以證明，MLIS[i]的最大值也是最終的結(jié)果。
MaxV[i]保存長(zhǎng)度為i的遞增子序列最大元素的最小值。
解法2的程序更新MaxV的部分應(yīng)該是有問(wèn)題的，由此導(dǎo)致時(shí)間復(fù)雜度的分析錯(cuò)誤，并且解法3也是錯(cuò)誤的。
2.17數(shù)組循環(huán)移位
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);
}
數(shù)組問(wèn)題思路：
排序思路
動(dòng)態(tài)規(guī)劃
看成一個(gè)數(shù)列或向量
2.18數(shù)組分割
3.1字符串移位包含的問(wèn)題
給定兩個(gè)字符串s1和s2，要求判定s2能否被s1做循環(huán)移位得到的字符串包含。例如：s1 = AABCD , s2 = CDAA，返回true. 給定s1 = ABCD 和 s2 = ACBD，返回false.
解法1：模擬字符串移位的過(guò)程，判斷是否包含子串
解法2：判斷s2是否為s1s1的子串即可。
解法3：不申請(qǐng)空間，模擬判斷s2是否為s1s1子串的過(guò)程。
思路：字符串可以抽象成向量來(lái)考慮。
3.2電話號(hào)碼對(duì)應(yīng)英語(yǔ)單詞
類似于求冪集問(wèn)題
解法1：迭代，用while循環(huán)模擬
解法2：遞歸
3.3計(jì)算字符串相似度
遞歸求解
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;
}
}
遞歸優(yōu)化，如何存儲(chǔ)子問(wèn)題的解？
3.4從無(wú)頭鏈表中刪除節(jié)點(diǎn)
這個(gè)問(wèn)題很無(wú)恥
3.5最短摘要生成
有空再看
3.6編程判斷兩個(gè)鏈表是否相交
轉(zhuǎn)化成鏈表是否有環(huán)的問(wèn)題
3.7隊(duì)列中取最大值操作
可分解為兩個(gè)子問(wèn)題
子問(wèn)題1：設(shè)計(jì)一個(gè)堆棧，使入棧，出棧，取最大值的時(shí)間復(fù)雜度都是O(1)。
思路：用空間換時(shí)間，加一個(gè)數(shù)組link2NextMaxItem[]，link2NextMaxItem[i]存儲(chǔ)的是前i個(gè)元素中最大值的下標(biāo)。
子問(wèn)題2：用上述特性的兩個(gè)堆棧實(shí)現(xiàn)一個(gè)隊(duì)列
堆棧A負(fù)責(zé)入隊(duì)，堆棧B負(fù)責(zé)出隊(duì)。當(dāng)堆棧B空的時(shí)候，將堆棧A中的數(shù)據(jù)全部彈出并壓入堆棧B
3.8 求二叉樹結(jié)點(diǎn)之間的最大距離
動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)，還是不太懂。
3.9重建二叉樹
遞歸求解
3.10分層遍歷二叉樹
隊(duì)列遍歷二叉樹+變量標(biāo)記層次
3.11程序改錯(cuò)
編寫正確的二分搜索程序
C代碼：
int BinSearch(SeqList * R， int n , KeyType K )
{ //在有序表R[0..n-1]中進(jìn)行二分查找，成功時(shí)返回結(jié)點(diǎn)的位置，失敗時(shí)返回-1
int low=0，high=n-1，mid； //置當(dāng)前查找區(qū)間上、下界的初值
if(R[low].key==K)
{
return 0 ;
}
while(low<=high){ //當(dāng)前查找區(qū)間R[low..high]非空
mid=low+((high-low)/2)；//使用 (low + high) / 2 會(huì)有整數(shù)溢出的問(wèn)題
if(R[mid].key==K)
{
return mid； //查找成功返回
}
if(R[mid].key>K)
high=mid-1; //繼續(xù)在R[low..mid-1]中查找
else
low=mid+1； //繼續(xù)在R[mid+1..high]中查找
}
return -1； //當(dāng)low>high時(shí)表示查找區(qū)間為空，查找失敗
} //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三角形測(cè)試用例
測(cè)試用例的三種類型：
正常輸入 覆蓋功能點(diǎn)
非法輸入 值域錯(cuò)誤 類型錯(cuò)誤
邊界值輸入 0 1 MAX MIN