貪心算法——字典序最小問題 · 算法程序設計

貪心算法——字典序最小問題 <table border="1" style="font-family:Simsun; border-collapse:collapse; width:80%; padding:0pt 5.4pt"><tbody><tr><td width="882" valign="top" style="width:661.75pt; padding:0pt 5.4pt; border:0.5pt solid rgb(0,0,0)">問題主題：字典序最小</td></tr><tr><td width="882" valign="top" style="width:661.75pt; padding:0pt 5.4pt; border-left-width:0.5pt; border-style:none solid solid; border-left-color:rgb(0,0,0); border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)">問題描述：給定長度為N的字符串S，要構造一個長度為N字符串T。T是一個空串，反復執行下列任意操作：l?從S的頭部刪除一個字符，加到T的尾部；l?從S的尾部刪除一個字符，加到T的尾部；目標是要構造字典序盡可能小的字符串T。限制條件：1<=N<=2000字符串都在大寫字符</td></tr><tr><td width="882" valign="top" style="width:661.75pt; padding:0pt 5.4pt; border-left-width:0.5pt; border-style:none solid solid; border-left-color:rgb(0,0,0); border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)">樣例：輸入N=8ADHCACBD輸出ADBCACDH</td></tr></tbody></table> ### 解題分析：看到這個問題，首先你肯定不難想到：**每次都從**S的頭部或尾部選擇最小的字符放到T的尾部** 對，這已經很接近真實了，但是還沒考慮首部和尾部相同的情況，那么首部和尾部相同的情況下該取首部還是尾部呢？其實思路還是一樣的，如果首部A和尾部B相同，就取首部的下一個字符(也就是第2個字符，設為A’)和尾部的前一個字符(也就量倒數第2個字符，設為B’)比較，如果A’<B’，則取首部；否則取尾部。如果A’和B’還相同，再比較A’的后一個字符A’’和B’的前一個字符B’’，以此類推直到S字符串為空。基于這個思路可以寫出以下程序： ### 程序實現: **C++** <table border="1" style="font-family:Simsun; border-collapse:collapse; width:80%; padding:0pt 5.4pt"><tbody><tr><td width="882" valign="top" style="width:661.8pt; padding:0pt 5.4pt; border:0.5pt solid rgb(0,0,0)"><pre code_snippet_id="162962" snippet_file_name="blog_20140119_1_6085865" name="code" class="cpp">#include <stdio.h> #include <tchar.h> #include <queue> #include "iostream" using namespace std; const int N = 8; char chs[N+1] = "ADHCACBD"; char* solve(char chs[]) { int start = 0, end = N - 1; bool isLeft = false; char dest[N]; while(start <= end) { for(int i = 0; start + i < end; i ++) { if(chs[start + i] < chs[end - i]) { isLeft = true; break; } else if(chs[start + i] > chs[end -i]) { isLeft = false; break; } else continue; } if(isLeft) { dest[N-(end - start + 1)] = chs[start ++]; //putchar(chs[start ++]); } else { dest[N-(end - start + 1)] = chs[end --]; //putchar(chs[end --]); } } return dest; } int main() { char *result = solve(chs); for(int i=0; i<N; i++) { putchar(result[i]); } return 0; }</pre> </td></tr></tbody></table> **Java** <table border="1" style="font-family:Simsun; border-collapse:collapse; width:80%; padding:0pt 5.4pt"><tbody><tr><td width="882" valign="top" style="width:661.8pt; padding:0pt 5.4pt; border:0.5pt solid rgb(0,0,0)"><pre code_snippet_id="162962" snippet_file_name="blog_20140119_2_8484653" name="code" class="java">package greed; /** * User: luoweifu * Date: 14-1-20 * Time: 上午9:41 */ public class BestCowLine { public static String cowLine(String s) { char[] chs = new char[s.length()]; char[] dest = new char[s.length()]; s.getChars(0, s.length(), chs, 0); int start = 0, end = s.length() - 1; while(start <= end) { boolean isLeft = false; for(int i=0; i <= end - start; i++) { if(chs[start + i] < chs[end - i]) { isLeft = true; break; } else if(chs[start + i] > chs[end - i]) { isLeft = false; break; } } if(isLeft) { dest[s.length() - (end - start + 1)] = chs[start ++]; } else { dest[s.length() - (end - start + 1)] = chs[end --]; } } return new String(dest); } public static void main(String args[]) { System.out.println(cowLine("ADHCACBD")); } } </pre> </td></tr></tbody></table> **** ### 算法復雜度： ???時間復雜度O(n(1+n)/2)?=?O(n2)