POJ_1007_DNASorting分析
DNA序列由四个字母的组合来表示,四个字母分别是A、C、G、T。每个序列都可以定义一个无序的度,比如GCA的无序度为3,计算方法为:G比后面2字母大,C比后面1个字母大,因此GCA的无序度为3。
输入要求:
第一行输入两个数字,第一个数字表示序列的长度,第二个数字表示序列的个数,如下:
10 6
AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCAT
输出要求:
按DNA序列的无序度由低到高输出,如果DNA无序度相同,则按输入的先后顺序输出。
这道题可分为两个部分,第一,计算DNA序列的无序度;第二,根据DNA序列的无序度进行排序。
计算DNA序列无序度的时候,如果该字母和前一字母相同,那么其无序度也和前一字母的相同,可以直接娶前一个字母的无序度值,减少计算量。
排序的时候由于数据量较小,所以选择什么排序都可以,推荐希尔排序。使用java的同学可以直接调用Arrays中的sort()方法。
Arrays.<String>sort(strArray, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
// TODO Auto-generated method stub
int len = o1.length();
int[] v1 = new int[len];
int[] v2 = new int[len];
char c1 = o1.charAt(0);
char c2 = o2.charAt(0);
for (int i = 1; i < len; i++) {
if (c1 - o1.charAt(i) > 0) v1[0]++;
if (c2 - o2.charAt(i) > 0) v2[0]++;
}
int value1 = v1[0], value2 = v2[0];
for (int i = 1; i < len; i++) {
if (o1.charAt(i) - o1.charAt(i - 1) == 0) {
v1[i] = v1[i - 1];
value1 += v1[i-1];
continue;
}
if (i == len - 1) {
v1[i] = 0;
break;
}
if (o1.charAt(i) == 'A') {
v1[i] = 0;
continue;
}
for (int j = i; j < len; j++) {
if (o1.charAt(i) - o1.charAt(j) > 0) v1[i]++;
}
value1 += v1[i];
}
for (int i = 1; i < len; i++) {
if (o2.charAt(i) - o2.charAt(i - 1) == 0) {
v2[i] = v2[i - 1];
value2 += v2[i - 1];
continue;
}
if (i == len - 1) {
v2[i] = 0;
break;
}
if (o2.charAt(i) == 'A') {
v2[i] = 0;
continue;
}
for (int j = i; j < len; j++) {
if (o2.charAt(i) - o2.charAt(j) > 0) v2[i]++;
}
value2 += v2[i];
}
System.out.printf("%s, length:%d %s, length:%d\n", o1, value1, o2, value2);
if (value1 < value2) {
return -1;
} else if (value1 == value2) {
return 0;
} else {
return 1;
}
}
});
分享到:
相关推荐
北大POJ1007-DNA Sorting 解题报告+AC代码
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 ...
2遍dp poj_3613解题报告 poj_3613解题报告
poj典型题目解题思路详解 包含源代码和解题时应注意的问题及题目陷阱设计分析
poj题目2775文件子目录源代码,递归经典题目,
poj 1699的代码和方法说明,个人原创
C_(POJ_1854)(分治).cpp
poj上第1990题目源码,用到了2个树状数组,这题数据结构是关键,想到了题目就很简单了
D_(POJ_1723)(思维)(sort).cpp
原理为:以数链思想,移动数组中的内容 使数组在没有扩充情况下,达成移动的效果 当然,有更简单的,大牛不要笑哦
D_(POJ_1723)(思维)(第k大数).cpp
POJ 3131 双向BFS解立体八数码问题
O(nlogn)凸包问题 poj2187
poj两道题的c++实现。已经测试过可以通过oj
poj dna sorting 问题,研究的ac coderrrrrrr
POJ题目及算法,包括动态规划、深搜广搜等算法。含相关注释。
这是北大在线测试的第1002题,方便记忆的电话号码的解题例程,题目中有一个列表,记录着许多方便记忆的电话号码。不同的方便记忆的电话号码可能对应相同的标准号码,这个程序的任务就是找到它们
问题:求平面上多个矩形的总面积。 算法:线段树(经典的线段树题目)
poj 3310 的代码和方法说明,个人原创
三道几何题:hdu 1007、hdu 2289、poj 3714