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

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

 

问题主题:字典序最小

问题描述:

给定长度为N的字符串S,要构造一个长度为N字符串TT是一个空串,反复执行下列任意操作:

S的头部删除一个字符,加到T的尾部;

S的尾部删除一个字符,加到T的尾部;

目标是要构造字典序尽可能小的字符串T

限制条件:

1<=N<=2000

字符串都在大写字符

样例:

输入

N=8

ADHCACBD

输出

ADBCACDH

 

 

解题分析:

看到这个问题,首先你肯定不难想到:每次都从S的头部或尾部选择最小的字符放到T的尾部

对,这已经很接近真实了,但是还没考虑首部和尾部相同的情况,那么首部和尾部相同的情况下该取首部还是尾部呢?

其实思路还是一样的,如果首部A和尾部B相同,就取首部的下一个字符(也就是第2个字符,设为A)和尾部的前一个字符(也就量倒数第2个字符,设为B)比较,如果A<B,则取首部;否则取尾部。如果AB还相同,再比较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)

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

上一篇:用 C# 编写 USB 存储设备使用痕迹检测和删除工具


下一篇:驱动第七天