贪心算法——字典序最小问题

问题主题：字典序最小

问题描述：

给定长度为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 &lt;= end) {
	for(int i = 0; start + i &lt; end; i ++)
	{
		if(chs[start + i] &lt; chs[end - i]) 
		{
			isLeft = true;
			break;
		}
			
		else if(chs[start + i] &gt; 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&lt;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 &lt;= end) {
	boolean isLeft = false;
	for(int i=0; i &lt;= end - start; i++) {
		if(chs[start + i] &lt; chs[end - i]) {
			isLeft = true;
			break;
		} else if(chs[start + i] &gt; 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)