POJ 1007 DNA Sorting（待改善）

POJ 1007 DNA Sorting

这道题做的不舒服，明白题目的意思后就想到一种最笨的解题思路——双重 for 循环来计算 DNA 序列的数值（左边字母大于右边字母的总个数）。但我始终觉得这不是好的算法，隐约觉得应该用“动态规划”。可惜学艺不精，一直没明白动态规划的原理。标记出来，期望改善之。

 

双重 for 循环的做法很快就实现了，开始使用 TreeMap 来存储数据，期望使用它的排序功能。结果忽略了值相等的情况，老是报 WA。所以改成将值拼凑入 DNA 序列开头的做法，并自定义 compare 方法进行比较。

代码如下：

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Comparator;
import java.util.Collections;

public class Main {
	private List<String> dnaList;

	public int countValue(String dna) {
		int value = 0;
		char[] c = dna.toCharArray();
		for (int i = 0; i < c.length; i++) {
			for (int j = i + 1; j < c.length; j++) {
				if (c[i] > c[j]) {
					value++;
				}
			}
		}
		return value;
	}

	public void run() throws Exception {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt(); // string length
		int m = scan.nextInt(); // lines limit

		dnaList = new ArrayList<String>(m);

		scan.nextLine();
		for (int i = 0; i < m; i++) {
			String dna = scan.nextLine();
			int count = countValue(dna);
			dnaList.add((char)count + dna);
		}

		// sort
		Collections.sort(dnaList, new Comparator<String>() {
			public int compare(String o1, String o2) {
				return o1.charAt(0) - o2.charAt(0);
			}
		});

		// output
		Iterator<String> iter = dnaList.iterator();
		while (iter.hasNext()) {
			String dna = iter.next();
			System.out.println(dna.substring(1, dna.length()));
		}
	}

	public static void main(String[] args) {
		Main m = new Main();
		try {
			m.run();
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}