贪心算法——字典序最小问题 · 算法程序设计

贪心算法——字典序最小问题 <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)