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

最后更新于：2022-04-01 20:19:53

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

问题主题：字典序最小

问题描述：

给定长度为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’

#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)
';