首页 > 代码库 > poj 4086:DNA排序

poj 4086:DNA排序

2024-07-30 05:32:10   221人阅读

poj 4086:DNA排序


题目

描述
现在有一些长度相等的DNA串（只由ACGT四个字母组成），请将它们按照逆序对的数量多少排序。
逆序对指的是字符串A中的两个字符A[i]、A[j]，具有i < j 且 A[i] > A[j] 的性质。如字符串”ATCG“中，T和C是一个逆序对，T和G是另一个逆序对，这个字符串的逆序对数为2。
输入
第1行：两个整数n和m，n(0<n<=50)表示字符串长度，m(0<m<=100)表示字符串数量
第2至m+1行：每行是一个长度为n的字符串
输出
按逆序对数从少到多输出字符串，逆序对数一样多的字符串按照输入的顺序输出。
样例输入
10 6
AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCAT
样例输出
CCCGGGGGGA
AACATGAAGG
GATCAGATTT
ATCGATGCAT
TTTTGGCCAA
TTTGGCCAAA

解题思路
我们主要解决的问题是找出一个字符串的逆序对
针对此我设计一下数据结构


dna hashtable 每一元素记录对应map中value-key中key出现的次数，此表是不断更新中的

好了我的算法思路用代码呈现吧

#include <iostream>
#include <map>
#include <fstream>
#include <algorithm>
#include <string>
using namespace std;

class Elem
{
public:
	int num;
	int order;
	string dna;
};



bool compare(Elem  a,Elem  b) 
{
	if(a.num < b.num)
		return true;
	else if( a.num == b.num && a.order < b.order )
		return true;
	else return false;
}


map<char,int> dnamap;
const int dna_length = 4;

void main_solution();
void read_data(string* & data,int &m);
int inversion( string & dna );
void initialize_map(map<char,int> &dnamap);



int main( )
{
	main_solution();
	system( "pause" );
	return 0;
}

void initialize_map(map<char,int> &dnamap)
{
	dnamap.insert( make_pair('A',0) );
	dnamap.insert( make_pair('C',1) );
	dnamap.insert( make_pair('G',2) );
	dnamap.insert( make_pair('T',3) );
}


// 求出dna字符串的逆序对
int inversion( string & dna )
{
	int num = 0;
	int now;
	int * dnahash = new int[ dna_length ];
	for(int i=0;i<dna_length;i++)
	{
		dnahash[i] = 0;
	}

	for( int i=0;i<dna.length();i++ )
	{
		now = dnamap.find( dna[i] )->second;
		dnahash[ now ] ++;
		for( int j = now+1; j<dna_length; j++ )
		{
			num += dnahash[j];
		}
	}
	return num ;
}

void read_data(string* & data,int &m)
{
	ifstream reader;
	reader.open("data.txt");
	reader>>m;
	reader>>m;
	data = http://www.mamicode.com/new string[m];>


poj 4086:DNA排序


联系
我们