POJ 1007 DNA Sorting(待改进)
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(); } } }