July 快排 動(dòng)態(tài)規(guī)劃 海量數(shù)據(jù)處理

北京算法班?周日班第6

次課July2014-05-25第五次課內(nèi)容快速排序一前一后兩指針同往后掃一頭一尾兩指針往中間掃動(dòng)態(tài)規(guī)劃：兩個(gè)小例子交替字符串最長(zhǎng)連續(xù)乘積子串3個(gè)思考問題海量數(shù)據(jù)處理六種主要方法快速排序快速排序算法實(shí)現(xiàn)一一前一后兩指針同往后掃j指針從第一個(gè)元素掃到倒數(shù)第二個(gè)，遇到比主元小，(i+1)與j所指元素互換PARTITION(A,p,r)1x←A[r]2i←p-13forj←ptor-14doifA[j]≤x5theni←i+16exchangeA[i]<->A[j]7exchangeA[i+1]<->A[r]8returni+1QUICKSORT(A,p,r)1ifp<r2thenq←PARTITION(A,p,r)//關(guān)鍵3QUICKSORT(A,p,q-1)4QUICKSORT(A,q+1,r)快速排序?qū)崿F(xiàn)一1/2intpartition(intdata[],intlo,inthi){intkey=data[hi];//以最后一個(gè)元素，data[hi]為主元inti=lo-1;for(intj=lo;j<hi;j++)///注，j從p指向的是r-1，不是r。{if(data[j]<=key){i=i+1;swap(&data[i],&data[j]);}}swap(&data[i+1],&data[hi]);//不能改為swap(&data[i+1],&key)returni+1;}快速排序?qū)崿F(xiàn)一2/2voidQuickSort(intdata[],intlo,inthi){if(lo<hi){intk=partition(data,lo,hi);QuickSort(data,lo,k-1);QuickSort(data,k+1,hi);}}快速排序?qū)崿F(xiàn)二voidquicksort(table*tab,intleft,intright){inti,j;if(left<right){i=left;j=right;tab->r[0]=tab->r[i];//準(zhǔn)備以本次最左邊的元素值為標(biāo)準(zhǔn)進(jìn)行劃分，先保存其值do{while(tab->r[j].key>tab->r[0].key&&i<j)j--;//從右向左找第1個(gè)小于標(biāo)準(zhǔn)值的位置jif(i<j)//找到了，位置為j{tab->r[i].key=tab->r[j].key;i++;}//將第j個(gè)元素置于左端并重置iwhile(tab->r[i].key<tab->r[0].key&&i<j)i++;//從左向右找第1個(gè)大于標(biāo)準(zhǔn)值的位置iif(i<j)//找到了，位置為i{tab->r[j].key=tab->r[i].key;j--;}//將第i個(gè)元素置于右端并重置j}while(i!=j);tab->r[i]=tab->r[0];//將標(biāo)準(zhǔn)值放入它的最終位置,本次劃分結(jié)束quicksort(tab,left,i-1);//對(duì)標(biāo)準(zhǔn)值左半部遞歸調(diào)用本函數(shù)quicksort(tab,i+1,right);//對(duì)標(biāo)準(zhǔn)值右半部遞歸調(diào)用本函數(shù)}}快速排序的變形回顧：荷蘭國(guó)旗問題題目描述相同的球放到一起，讓你按順序輸出紅白藍(lán)三種顏色的球，可以用012來表示，要求只能掃描一次數(shù)組將亂序的紅白藍(lán)三色小球排列成有序的紅白藍(lán)三色的同顏色在一起的小球組。荷蘭國(guó)旗問題思路類似快排中partition過程，用三個(gè)指針，一前begin，一中current，一后end，current遍歷

整個(gè)數(shù)組序列：current指0，與begin交換，而后current++，begin++；current指1，不做任何交換（即球不動(dòng)），而后current++；current指2，與end交換，而后，current指針不動(dòng)，end--。快排中的partition過程？解決步驟1current指0，與begin交換而后current++，begin++current指1，不做任何交換而后current++current指2，與end交換而后，current不動(dòng)，end--解決步驟2current指0，與begin交換而后current++，begin++current指1，不做任何交換而后current++current指2，與end交換而后current不動(dòng)，end--動(dòng)態(tài)規(guī)劃兩個(gè)簡(jiǎn)單的例子最短路徑：A->B經(jīng)過x1，x2，x3故枚舉所有可能從A到B要經(jīng)過的路徑選擇一條最優(yōu)如何求最優(yōu)比較如何比較？寫DP方程，min之類的如何寫？練.如何練？..比如二維數(shù)組最小路徑和一個(gè)二維矩陣M*N矩陣matrix中，找出一條路徑，只能向右或向下，求路徑經(jīng)過元素之和最小當(dāng)前位置(i,j)上一個(gè)位置只可能是(i-1，j)或(i,j-1)故：path[i][j]=min(path[i][j-1],path[i-1][j])+matrix[i][j]交替字符串輸入三個(gè)字符串s1、s2和s3，判斷第三個(gè)字符串s3是否由前兩個(gè)字符串s1和s2交錯(cuò)而成，即不改變s1和s2中各個(gè)字符原有的相對(duì)順序例如當(dāng)s1=“aabcc”，s2=“dbbca”，s3=“aadbbcbcac”時(shí)，則輸出true，但如果s3=“accabdbbca”，則輸出false。解法令dp[i][j]代表s3[0...i+j-1]是否由s1[0...i-1]和s2[0...j-1]的字符組成如果s1當(dāng)前字符（即s1[i-1]）等于s3當(dāng)前字符（即s3[i+j-1]），而且dp[i-1][j]為真，那么可以取s1當(dāng)前字符而忽略s2的情況，dp[i][j]返回真；如果s2當(dāng)前字符等于s3當(dāng)前字符，并且dp[i][j-1]為真，那么可以取s2而忽略s1的情況，dp[i][j]返回真，其它情況，dp[i][j]返回假最長(zhǎng)連續(xù)乘積子串題目給一個(gè)浮點(diǎn)數(shù)序列，取最大乘積連續(xù)子串的值，例如-2.5，4，0，3，0.5，8，-1，則取出的最大乘積連續(xù)子串為3，0.5，8。也就是說，上述數(shù)組中，30.58這3個(gè)數(shù)的乘積3*0.5*8=12是最大的，而且是連續(xù)的。子串要求連續(xù)，子序列不要求連續(xù)解法一、暴力輪詢doublemax=0;doublestart=0;doubleend=0;for(inti=0;i<num;i++){doublex=arrs[i];for(intj=i+1;j<num;j++){x*=arrs[j];if(x>max){max=x;start=arrs[i];end=arrs[j];}}}解法二數(shù)組中找一個(gè)子序列，使得它的乘積最大；同時(shí)找一個(gè)子序列，使得它的乘積最?。ㄘ?fù)數(shù)的情況）。即不但記錄最大乘積，也要記錄最小乘積。maxCurrent表示當(dāng)前最大乘積的candidate，minCurrent反之，表示當(dāng)前最小乘積的candidate，而maxProduct則記錄到目前為止所有最大乘積candidates的最大值。（以上用candidate這個(gè)詞是因?yàn)橹皇强赡艹蔀樾乱惠喌淖畲?最小乘積）解法三、動(dòng)態(tài)規(guī)劃用Max來表示以a結(jié)尾的最大連續(xù)子串的乘積值，用Min表示以a結(jié)尾的最小的子串的乘積值，那么狀態(tài)轉(zhuǎn)移方程為：Max=max{a,Max[i-1]*a,Min[i-1]*a};Min=min{a,Max[i-1]*a,Min[i-1]*a};初始狀態(tài)為Max[1]=Min[1]=a[1]。思考一、最長(zhǎng)公共子序列有兩條隨機(jī)序列，如13455，and245576，則它們的最長(zhǎng)公共子序列便是：455。解法：窮舉DP思考二最長(zhǎng)遞增子序列給定一個(gè)長(zhǎng)度為N的數(shù)組a0,a1,a2...,an-1，找出一個(gè)最長(zhǎng)的單調(diào)遞增子序列。例如：給定一個(gè)長(zhǎng)度為6的數(shù)組A{5，6，7，1，2，8}，則其最長(zhǎng)的單調(diào)遞增子序列為{5，6，7，8}，長(zhǎng)度為4。解法動(dòng)態(tài)規(guī)劃定義dp[i]為以ai為末尾的最長(zhǎng)遞增子序列的長(zhǎng)度，故以ai結(jié)尾的遞增子序列要么是只包含ai的子序列要么是在滿足j<i并且aj<ai的以ai為結(jié)尾的遞增子序列末尾，追加上ai后得到的子序列dp[i]=(dp[i]>dp[i+1])?dp[i]:dp[i+1];轉(zhuǎn)換為最長(zhǎng)公子序列問題思考三：字符串編輯距離DP狀態(tài)轉(zhuǎn)移方程//f[i,j]表示s[0...i]與t[0...j]的最小編輯距離。f[i,j]=min{f[i-1,j]+1,f[i,j-1]+1,f[i-1,j-1]+(s[i]==t[j]?0:1)}//分別表示：添加1個(gè)，刪除1個(gè)，替換1個(gè)（相同就不用替換）。思考四、格子取數(shù)問題題目有n*n個(gè)格子，每個(gè)格子里有正數(shù)或者0，從最左上角往最右下角走，只能向下和向右，一共走兩次（即從左上角走到右下角走兩趟），把所有經(jīng)過的格子的數(shù)加起來，求最大值SUM，且兩次如果經(jīng)過同一個(gè)格子，則最后總和SUM中該格子的計(jì)數(shù)只加一次。貪心陷阱不顧全局，只看局部，讓第一次和第二次的路徑都是最優(yōu)海量數(shù)據(jù)處理六種密匙分而治之/hash映射分而治之/hash映射

+hash統(tǒng)計(jì)+堆/快速/歸并排序；雙層桶劃分Bloomfilter/Bitmap；Trie樹/數(shù)據(jù)庫(kù)/倒排索引；外排序；分布式處理之Hadoop/Mapreduce。29萬(wàn)丈高樓平地起Reb-Blacktreeset/map（map同時(shí)擁有key和value，set的key就是value）multiset/multimap（允許重復(fù)鍵值）hashtablehashmap/hashset/hash_multiset/hash_multimap（允許重復(fù)鍵值）30海量日志數(shù)據(jù)海量日志數(shù)據(jù)，提取出某日訪問百度次數(shù)最多的那個(gè)IP31分而治之/hash映射+hash統(tǒng)計(jì)+堆/快速/歸并排序海量日志數(shù)據(jù)，提取出某日訪問百度次數(shù)最多的那個(gè)IP分而治之/hash映射，比如模1000，把整個(gè)大文件映射為1000個(gè)小文件hash_map(ip，value)來進(jìn)行頻率統(tǒng)計(jì)（hash_map對(duì)那1000個(gè)文件中的所有IP進(jìn)行頻率統(tǒng)計(jì)，然后