题目的意思很明显,就是算出每个字符串的逆序数,然后按照它们的逆序数排序,最后输出。因此这里的主要操作可以分两步:
①计算逆序数
注意到这里出现的字符只有4种(ACGT),因此可以将字符串扫描一遍就可以计算出逆序数。方法是,对字符串进行正向扫描,记录扫描时C、G、T出现的次数,如果当前扫描的字符是A,则逆序数要依次加上C、G、T的个数;如果是C,则逆序数加上G、T的个数;如果是G,则逆序数加上T的个数。
②将字符串按照逆序数进行排序
这里要求当逆序数相同时,按照出现顺序排序,即排序结果要稳定。所以如果要使用快速排序的化,不能直接按照逆序数来当做比较标准,但可以变通,比如当逆序数相同时,把字符串的出现的顺序作为比较标准。
在Java中对于对象数组的排序是稳定的(具体算法:在JDK7以前使用的是归并排序MergeSort,JDK7中使用的是TimSort。有时间研究一下,希望可以看得懂~~)。
import java.util.*;
import java.io.*;
//1007 DNA Sorting
public class Main
{
public static void main(String[] args) throws Exception {
Scanner in = new Scanner(new BufferedInputStream(System.in));
int countOfCase, lengthOfString;
lengthOfString = in.nextInt();
countOfCase = in.nextInt();
DNA[] DNAs = new DNA[countOfCase];
for(int i = 0; i < countOfCase; i++)
DNAs[i] = new DNA(in.next());
Arrays.sort(DNAs);
for(DNA dna: DNAs)
System.out.println(dna.strOfDNA);
}
}
class DNA implements Comparable<DNA>
{
String strOfDNA;
int countOfInversion;
public DNA(String strOfDNA) {
this.strOfDNA = strOfDNA;
calInversion();
}
private void calInversion() {
countOfInversion = 0;
int C = 0, G = 0, T = 0;
for(int i = 0, n = strOfDNA.length(); i < n; i++) {
switch(strOfDNA.charAt(i)) {
case 'A':
countOfInversion = countOfInversion + C + G + T;
break;
case 'C':
C++;
countOfInversion = countOfInversion + G + T;
break;
case 'G':
G++;
countOfInversion = countOfInversion + T;
break;
case 'T':
T++;
break;
}
}
}
public int compareTo(DNA another) {
return countOfInversion - another.countOfInversion;
}
}
分享到:
相关推荐
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 ...
pku acm 1007 DNA Sorting代码 逆序数 排序 解题报告请访问:http://blog.csdn.net/china8848
北大POJ1007-DNA Sorting 解题报告+AC代码
北大ACM习题 Problem 1007:DNASorting参考答案 可以accept,本人用的环境是codeblocks
poj dna sorting 问题,研究的ac coderrrrrrr
这是East Central North America 1998的测试数据,包括POJ的1007DNA Sorting等问提,利于大家思考。
生成一个可以控制上下界限的随机数列,并使用选择排序selection sorting算法对其排序。
输入DNA序列,程序将把DNA序列翻译成对应的mRNA序列,把DNA序列翻译成对应的蛋白质序列
methods for rearranging information in a computer into a prescribed order (“sorting”); how to solve basic problems that can be modeled in a computer with a mathematical structure called a “graph”...
1007 Numerical Summation of a Series 简单题,还是蛮有意思的 1045 HangOver 简单题 1049 I Think I Need a Houseboat 简单题 1028 Flip and Shift 简单题,可以DP/BFS/……,但是实际上有数学方法可直接判断...
1007 Numerical Summation of a Series 简单题,还是蛮有意思的 1045 HangOver 简单题 1049 I Think I Need a Houseboat 简单题 1028 Flip and Shift 简单题,可以DP/BFS/……,但是实际上有数学方法可直接判断...
Perlgolf History Perlgolf History Edition 2007-01-09 top secret / strictly confidential page 2 of 520 Contents 1. Intro.........................................................................