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();
}
}
}
分享到:
相关推荐
DNA Sorting Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 34868 Accepted: 13480 Description One measure of ``unsortedness'' in a sequence is the number of pairs of entries that are ...
北大POJ1007-DNA Sorting 解题报告+AC代码
poj dna sorting 问题,研究的ac coderrrrrrr
poj1007 AC代码 0MS过题写法 不过是个水题 哈哈哈哈
poj1007题代码,DNA问题,C++语言,map
北大POJ1094-Sorting It All Out 解题报告+AC代码
ACM是很好的,多在OJ上练习,你会有惊喜的。很能增加您的技能。
这是East Central North America 1998的测试数据,包括POJ的1007DNA Sorting等问提,利于大家思考。
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
简单的字符串操作和求逆序对数,是程设poj习题
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
* 较为复杂的动态规划:例如 poj1191、poj1054、poj3280、poj2029、poj2948、poj1925、poj3034。 数学 1. 组合数学: * 加法原理和乘法原理。 * 排列组合。 * 递推关系:例如 poj3252、poj1850、poj1019、poj...
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友