贪心算法——字典序最小问题
问题主题:字典序最小 |
问题描述: 给定长度为N的字符串S,要构造一个长度为N字符串T。T是一个空串,反复执行下列任意操作: l 从S的头部删除一个字符,加到T的尾部; l 从S的尾部删除一个字符,加到T的尾部; 目标是要构造字典序尽可能小的字符串T。 限制条件: 1<=N<=2000 字符串都在大写字符 |
样例: 输入 N=8 ADHCACBD 输出 ADBCACDH |
解题分析:
看到这个问题,首先你肯定不难想到:每次都从S的头部或尾部选择最小的字符放到T的尾部
对,这已经很接近真实了,但是还没考虑首部和尾部相同的情况,那么首部和尾部相同的情况下该取首部还是尾部呢?
其实思路还是一样的,如果首部A和尾部B相同,就取首部的下一个字符(也就是第2个字符,设为A’)和尾部的前一个字符(也就量倒数第2个字符,设为B’)比较,如果A’<B’,则取首部;否则取尾部。如果A’和B’还相同,再比较A’的后一个字符A’’和B’的前一个字符B’’,以此类推直到S字符串为空。基于这个思路可以写出以下程序:
程序实现:
C++
#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; } |
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")); } } |
算法复杂度:
时间复杂度O(n(1+n)/2) = O(n2)