練習(xí)200個基本數(shù)據(jù)機(jī)構(gòu)及算法問題
解答思路：
- 分析問題的解決方案添祸；
- 設(shè)計解決問題的方法及結(jié)構(gòu)艳馒；
- 設(shè)計使用的算法及數(shù)據(jù)結(jié)構(gòu)；
- coding實(shí)現(xiàn)匆浙；
- 考慮算法的邊界及異常；
- 提供測試接口厕妖；
排序
- 快排
hint：以中間值分組, 注意收尾判斷首尼；
void Qsort(int a[], int low, int high)
{
if(low >= high)
{
return;
}
int first = low;
int last = high;
int key = a[first];/*用字表的第一個記錄作為樞軸*/
while(first < last)
{
while(first < last && a[last] >= key)
{
--last;
}
a[first] = a[last];/*將比第一個小的移到低端*/
while(first < last && a[first] <= key)
{
++first;
}
a[last] = a[first];
/*將比第一個大的移到高端*/
}
a[first] = key;/*樞軸記錄到位*/
Qsort(a, low, first-1);
Qsort(a, first+1, high);
}
數(shù)組
- 二分查找
使用while判斷處理更簡潔
while(low<=high)
{
int mid=(low+high)/2;
if(array[mid]>target)
high=mid-1;
else if(array[mid]<target)
low=mid+1;
else
return mid;
}
數(shù)組查詢，判斷
hint: 排序再查找言秸，大數(shù)組查詢會有效率問題软能，異或操作循環(huán)有序數(shù)組查找最小值位置
如（345678012），要求時間復(fù)雜度為log2(n)
hint: 數(shù)組分為兩部分举畸，一定有一部分是有序的查排，遞歸查找最大連續(xù)和
hint: 貪心算法
int maxSubsequSum(int* a) {
assert(a);
int maxSum = 0;
int curSum = 0;
for (int s = 0, e = 0; e < a.length; e++) {
curSum += a[e];
if (curSum < 0) {
s = e + 1;
curSum = 0;
} else if (curSum > maxSum) {
maxSum = curSum;
}
}
}
給一個數(shù)字的列表比如：，0抄沮，1跋核，0，1叛买，4砂代，2，4率挣，畫成柱狀時刻伊，會有凹下去的一部分，凹下去的部分裝水椒功，問能裝多少水捶箱？
hint：木桶裝水，短板效應(yīng)动漾，分為子問題丁屎，一直尋找最小的板并合并；一個有N個數(shù)的數(shù)組谦炬，求數(shù)組里每一個數(shù)轉(zhuǎn)換成2進(jìn)制后的1的個數(shù)
hint：num &=（num -1）位移
一個數(shù)一個數(shù)的算
查表發(fā)悦屏，將數(shù)組轉(zhuǎn)換成char類型，對應(yīng)的每個char的1的個數(shù)累加起來键思；
HAKMEM算法：
int Count(unsigned x)
{
unsigned n;
n = (x >> 1) & 033333333333;
x = x - n;
n = (n >> 1) & 033333333333;
x = x - n;
x = (x + (x >> 3)) & 030707070707;
x = modu(x, 63); return x;
}
參考：http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive
- 一個長度為2N的數(shù)組础爬，前面N個是數(shù)字，后面N個是字母吼鳞，類似123abc,讓轉(zhuǎn)化為1a2b3c
hint: 轉(zhuǎn)換位置看蚜，swap(arr[i], arr[n+i-gap])，轉(zhuǎn)換一次后找規(guī)律
//gap這個有點(diǎn)難理解
void convert(vector<string>& ele,int gap)
{
int len = ele.size();
int n = len / 2;
if(gap < n)
{
for(int i = gap ; i < n; )
{
//gap組進(jìn)行位置轉(zhuǎn)換
for(int j = 0; j < gap; ++j)
{
swap(ele[i + j],ele[n + i + j - gap ]);
}
//偶數(shù)位保持不動
i += 2*gap;
}
convert(ele,2*gap);
}
}
convert(ele, 1);
整數(shù)
大整數(shù)乘積
輸入兩個整數(shù)赔桌，輸出乘積供炎，輸出數(shù)字可能超過計算機(jī)內(nèi)整數(shù)數(shù)據(jù)的存儲范圍渴逻；
hint：m位整數(shù)*n位整數(shù)，乘積結(jié)果為m+n-1或者m+n
參考：http://www.cnblogs.com/jason-yang/archive/2012/04/26/2472755.html數(shù)N內(nèi)所有素數(shù)
hint：非素數(shù)肯定有一個因子是大大于sqrt(n)的音诫，合數(shù)肯定能分解若干個質(zhì)數(shù)惨奕，不能被素數(shù)整除就肯定是素數(shù)；
參考：http://www.tuicool.com/articles/qaaA3i
字符串
- 編輯距離 （Levenshtein距離）
找出字符串的編輯距離竭钝，即把一個字符串s1最少經(jīng)過多少步操作變成編程字符串s2梨撞，操作有三種，添加一個字符香罐，刪除一個字符卧波，修改一個字符
hint：動態(tài)規(guī)劃
大數(shù)據(jù)
- 100w數(shù)據(jù)找最大100個
hint：最大樹，分組求最大合并庇茫；
分組可根據(jù)數(shù)據(jù)特征選取不同分組
分成100個組每個組取出最大的前100個港粱，然后建一個100的最小堆，下一個數(shù)據(jù)如果大于最小值旦签，替換最小值并刷新堆查坪，10000*log100的時間效率；
棧
- 給出一個入棧序列宁炫，再給一個出棧隊列咪惠，看出棧序列是否正確
- 一個數(shù)組實(shí)現(xiàn)二個堆棧
最大限度利用數(shù)組
class stack {
public:
int a[maxSize];
int top1; //從頭開始壓棧
int top2;//從尾開始壓棧
}
void push(stack &A, int x, int Tag);
void pop(stack &A, int Tag);
矩陣
- 填數(shù)
蛇形填數(shù)：
hint：逆序變換，坐標(biāo)變換i-j淋淀，按照斜線寫回 a[i-j][j] = a[i][j], a[i-j][j] = b[i][j-i+n-1]
http://blog.163.com/lvan100@yeah/blog/static/6811721420107176921749/
回轉(zhuǎn)填數(shù)：
https://my.oschina.net/u/1584433/blog/226571
int n, x, y, tot = 0;
scanf("%d", &n);
memset(a, 0, sizeof(a));
a[x = 0][y = n - 1] = tot = 1;
while (tot < n * n) {
while (x + 1 < n && !a[x + 1][y]) a[++x][y] = ++tot;
while (y - 1 >= 0 && !a[x][y - 1]) a[x][--y] = ++tot;
while (x - 1 >= 0 && !a[x - 1][y]) a[--x][y] = ++tot;
while (y + 1 < n && !a[x][y + 1]) a[x][++y] = ++tot;
}
鏈表
- 有序鏈表合并
struct node {
int data;
struct node *next;
}
struct node *sortList(struct node *a, struct node *b)
{
struct node *result = NULL;
if (a == NULL) {
return b;
} else if (b == NULL) {
return a;
}
if (a->data <= b->data) {
{
result = a;
result->next = SortedMerge(a->next, b);
} else {
result = b;
result->next = sortList(a, b->next);
}
return result;
}
- 合并k個有序鏈表
思路：
1）在買一個鏈表中取出第一個值遥昧，然后把他們放在一個大小為K的數(shù)組里，然后把這個數(shù)組當(dāng)成heap朵纷，然后把堆建成最小堆炭臭，此步驟時間復(fù)雜度為O(K);
- 取出堆中的最小值，然后把該最小值所處的鏈表的下一值放在數(shù)組的第一個位置袍辞；如果鏈表中一個已經(jīng)為空鞋仍，改變heap大小（從底往前調(diào)整）搅吁；然后執(zhí)行min-heapify操作威创，此步驟時間復(fù)雜度為O(lgK);
- 不斷重復(fù)步驟2，直到所有鏈表都為空谎懦；
參考：
http://blog.csdn.net/beiyetengqing/article/details/7685593
- 兩個升序合并成一個降序
樹
>> 紅黑樹
平衡二叉樹（AVL-樹）肚豺，左右兩個子樹的高度差絕對值不超過1，并且左右兩個子樹都是一顆平衡二叉樹界拦；
二叉查找樹吸申，任意節(jié)點(diǎn)的左子樹上的值均小于它的根節(jié)點(diǎn)的值，右子樹上的值均大于它的根節(jié)點(diǎn)的值，且左右子樹也分別為二叉查找樹截碴；
紅黑樹是一種平衡二叉查找樹梳侨，每個節(jié)點(diǎn)帶有顏色屬性；
用來構(gòu)造關(guān)聯(lián)數(shù)組和集合日丹；
它再 O(logn)時間內(nèi)做查找走哺，插入和刪除 ；
紅黑樹是每個節(jié)點(diǎn)都帶有顏色屬性的二叉查找樹哲虾，顏色紅色或黑色割坠，其性質(zhì)有：
1）節(jié)點(diǎn)是紅色或黑色；
2）根節(jié)點(diǎn)是黑色妒牙；
3）每個葉節(jié)點(diǎn)（即空節(jié)點(diǎn)）是黑色的；
4）每個紅色節(jié)點(diǎn)的兩個子節(jié)點(diǎn)都是黑色（每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點(diǎn)）对妄；
5）從任一節(jié)點(diǎn)到其某個葉子節(jié)點(diǎn)的所有路徑都包含相同數(shù)據(jù)的黑色節(jié)點(diǎn)湘今；//這樣約束的話，就必須有紅色節(jié)點(diǎn)干預(yù)才能實(shí)現(xiàn)剪菱；
插入操作：插入新節(jié)點(diǎn)總是紅色節(jié)點(diǎn)摩瞎，因?yàn)椴粫茐男再|(zhì)5，然后左右旋維護(hù)其他性質(zhì)孝常；
（這些特質(zhì)能夠保證一顆n個節(jié)點(diǎn)的紅黑樹的高度適中保持在logn
）
參考：http://blog.csdn.net/chenhuajie123/article/details/11951777
>> 堆
堆其實(shí)是一顆完全二叉樹旗们，堆可分為大頂堆與小頂堆，用于查找排序比較方便构灸；
- 最小堆
滿足 Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]稱為小頂堆上渴，即父節(jié)點(diǎn)都比子節(jié)點(diǎn)小喜颁；
最小堆實(shí)現(xiàn)稠氮，插入新元素即調(diào)整元素位置，父節(jié)點(diǎn)是與子節(jié)點(diǎn)對應(yīng)關(guān)系是parentNodePos = (childNodePos - 1) / 2半开，構(gòu)建最小堆的時間復(fù)雜度為log(n)：
void fix_up_min_heap( int arr[], int n, int len, int i )
{
int j = ( i - 1 ) / 2; // parent index
int tmp = arr[i];
while( j >= 0 && tmp < arr[j] )
{
arr[i] = arr[j]; i = j;
if( j > 0 )
j = ( j - 1 ) / 2;
else
break;
}
arr[i] = tmp;
}
void fix_down_min_heap( int arr[], int n, int len, int i ) // n 為數(shù)組容量隔披，len為當(dāng)前長度
{
int j = 2 * i + 1;
int tmp = arr[i];
while( j < len )
{
if( j < len - 1 && arr[j + 1] < arr[j] )
++j;
if( arr[j] < tmp )
{
arr[i] = arr[j];
i = j;
j = 2 * i + 1;
}
else
{
break;
}
}
arr[i] = tmp;
}
int insert_min_heap( int arr[], int n, int * len, int x )
{
if( n == *len ) return -1;
arr[(*len)++] = x;
fix_up_min_heap( arr, n, *len, *len - 1 );
return 1;
}
int top_min_heap( int arr[], int n )
{
return arr[0];
}
void pop_min_heap( int arr[], int n, int * len )
{
// assert( *len > 0 );
arr[0] = arr[--*len];
fix_down_min_heap( arr, n, *len, 0 );
}
- 堆排序（最大堆到有序堆）思想：
先構(gòu)建一個最大堆或者最小堆，然后將最大或最小元素挪到最后位置寂拆，遞歸完成所有元素處理奢米；
1）將待排序序列初始化；
2）將堆頂元素與最后一個元素R[n]交換纠永，此時得到新的無序區(qū)(R1,R2,......Rn-1)和新的有序區(qū)(Rn),且滿足R[1,2...n-1]<=R[n];
- 由于交換后新的堆頂R[1]可能違反堆的性質(zhì)鬓长，因此需要對當(dāng)前無序區(qū)(R1,R2,......Rn-1)調(diào)整為新堆，然后再次將R[1]與無序區(qū)最后一個元素交換尝江，得到新的無序區(qū)(R1,R2....Rn-2)和新的有序區(qū)(Rn-1,Rn)痢士。不斷重復(fù)此過程直到有序區(qū)的元素個數(shù)為n-1，則整個排序過程完成；
參考：http://blog.csdn.net/cdnight/article/details/11650983
樹操作
樹的屬性怠蹂，使得數(shù)據(jù)可以左右分離善延，易于管理控制；
用數(shù)組的位置標(biāo)注完全二叉樹城侧，可以簡化很多操作易遣，因?yàn)橥耆鏄涞臄?shù)父子節(jié)點(diǎn)的對應(yīng)關(guān)系是 j = (i - 1)/2；
最大最小的多少個數(shù)嫌佑，可以輕易的用最大堆最小堆來解決豆茫；
- 深度遍歷樹
父子節(jié)點(diǎn)遍歷，有前序后序中序 - 廣度遍歷樹
一層一層的遍歷 - 多叉樹構(gòu)建
左右節(jié)點(diǎn)遍歷處理屋摇，比較適合遞歸 - 樹的鏡像
hint：自定義數(shù)據(jù)結(jié)構(gòu)
分治法
將大問題分為子問題揩魂，最后合并子問題結(jié)果；
動態(tài)規(guī)劃
每次決策依賴于當(dāng)前狀態(tài)炮温，又隨即引起狀態(tài)的轉(zhuǎn)移火脉，一個決策序列就是在變化的狀態(tài)中產(chǎn)生出來的，所以柒啤，這種多階段最優(yōu)化決策解決問題的過程就稱為動態(tài)規(guī)劃倦挂。
動態(tài)規(guī)劃可以分為子問題解決，但是子問題之間是相互以來的担巩；
