面试题（68）
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的字符串
按逆序对数从少到多输出字符串，逆序对数一样多的字符串按照输入的顺序输出。
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&
class Elem
bool compare(Elem
if(a.num & b.num)
else if( a.num == b.num && a.order & b.order )
map&char,int&
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& );
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 * dnahash = new int[ dna_length ];
for(int i=0;i&dna_i++)
dnahash[i] = 0;
for( int i=0;i&dna.length();i++ )
now = dnamap.find( dna[i] )-&
dnahash[ now ] ++;
for( int j = now+1; j&dna_ j++ )
num += dnahash[j];
void read_data(string* & data,int &m)
reader.open(&data.txt&);
reader&&m;
reader&&m;
data = new string[m];
for( int i =0; i&m; i++ )
reader&&data[i];
reader.close();
void main_solution()
read_data(data,m);
initialize_map(dnamap);
Elem * myset = new Elem[m];
for(int i=0;i&m;i++)
myset[i].dna = data[i];
myset[i].order =
myset[i].num = inversion(data[i]);
sort(myset,myset+m,compare);
for(int i=0;i&m;i++)
cout&&myset[i].dna&&
&&相关文章推荐
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：171041次
积分：3663
积分：3663
排名：第8135名
原创：195篇
转载：26篇
评论：47条
阅读：3149
文章：35篇
阅读：29497
文章：60篇
阅读：58427
文章：36篇
阅读：32640
(1)(2)(2)(6)(3)(1)(1)(6)(11)(3)(3)(4)(5)(15)(8)(4)(2)(6)(16)(18)(18)(12)(5)(21)(41)(6)枚举（29）
快排（14）
题2、DNA排序
逆序对的定义如下:
有一个数列{an}，对于任意的ai
st:array[0..20000] of string;
nu,a:array[0..20000] of
c:array['A'..'Z'] of
procedure qsort(l,r:longint);
if l&=r then exit;
i:=l;j:=r;
k:=a[(l+r) div 2];
k1:=nu[(l+r) div 2];
while (a[i]&k) or ((a[i]=k) and (nu[i]&k1)) do inc(i);
while (a[j]&k) or ((a[j]=k) and (nu[j]&k1)) do dec(j);
if i&=j then
a[0]:=a[i];a[i]:=a[j];a[j]:=a[0];
st[0]:=st[i];st[i]:=st[j];st[j]:=st[0];
nu[0]:=nu[i];nu[i]:=nu[j];nu[j]:=nu[0];
inc(i);dec(j);
until i&j;
qsort(l,j);qsort(i,r);
assign(input,'dna.in');reset(input);
assign(output,'dna.out');rewrite(output);
readln(l,n);
for i:=1 to n do
readln(st[i]);
for i:=1 to n do
fillchar(c,sizeof(c),0);
for j:=2 to l do
inc(c[s[j]]);
for j:=1 to l do
if j&1 then dec(c[s[j]]);
case s[j] of
inc(a[i],c['A']);
inc(a[i],c['C']);
inc(a[i],c['G']);
inc(a[i],c['A']);
inc(a[i],c['C']);
'C':inc(a[i],c['A']);
qsort(1,n);
for i:=1 to n do
writeln(st[i]);
close(input);close(output);
&&相关文章推荐
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：6218次
积分：1863
积分：1863
排名：第19688名
原创：184篇
(36)(40)(27)(22)(33)(27)(1)早起一水（136）
终于可以说：没有那么水了（虽然还是很水）。。。。。。
关于逆序数的题目，开始用塑料的冒泡排序一直WA，后来自己写一个，终于过了，要求是稳定的！！！！！！！
AC的代码：
#include &stdio.h&
#include &string.h&
char DNA[105][55];
//输入原DNA序列
int visit[105];
int Inversion(int nTh,int len)
int i,j,count=0;
for(i=0;i&i++)
for(j=i;j&j++)
if(DNA[nTh][i]&DNA[nTh][j])
count++;
int main()
//1A，2B, 3C, 4D, 5E, 6F, 7G, 8H, 9I, 10J, 11K, 12L, 13M, 14N, 15O, 16P, 17Q, 18R, 19S, 20T, 21U, 22V, 23W, 24X, 25Y, 26Z
int inverNum[102];
//对应每个数列的逆序数
scanf(&%d%d&,&n,&m);
for(i=0;i&m;i++)
scanf(&%s&,DNA[i]);
inverNum[i]=Inversion(i,n);
//传入排位第i个的DNA序列，和序列长度
//printf(&逆序数为：%d\n&,inverNum[i]);
//每次都找到inverNum最小的序列打印，一定是稳定的
for(i=0;i&m;i++)
min=1000; //开始放min为一个很大的数
for(j=0;j&m;j++)
if(visit[j]==0 && min&inverNum[j])
min=inverNum[j];
visit[pos]=1; //标记被访问过了
printf(&%s\n&,DNA[pos]);
WA 2次的代码：
#include &stdio.h&
#include &string.h&
char DNA[105][55];
//输入原DNA序列
int Inversion(int nTh,int len)
int i,j,count=0;
for(i=0;i&i++)
for(j=i;j&j++)
if(DNA[nTh][i]&DNA[nTh][j])
count++;
int main()
//1A，2B, 3C, 4D, 5E, 6F, 7G, 8H, 9I, 10J, 11K, 12L, 13M, 14N, 15O, 16P, 17Q, 18R, 19S, 20T, 21U, 22V, 23W, 24X, 25Y, 26Z
int inverNum[102];
//对应每个数列的逆序数
scanf(&%d%d&,&n,&m);
for(i=0;i&m;i++)
scanf(&%s&,DNA[i]);
inverNum[i]=Inversion(i,n);
//传入排位第i个的DNA序列，和序列长度
//printf(&逆序数为：%d\n&,inverNum[i]);
//直接用冒泡排序（稳定的）
char tmpN,temp[55];
for(i=0;i&m;i++)
for(j=i;j&m;j++)
if(inverNum[i]&=inverNum[j])
//交换逆序数
tmpN=inverNum[j];
inverNum[j]=inverNum[i];
inverNum[i]=tmpN;
//交换DNA序列
strcpy(temp,DNA[j]);
strcpy(DNA[j],DNA[i]);
strcpy(DNA[i],temp);
for(i=0;i&m;i++)
printf(&%s\n&,DNA[i]);
中文题目：
题目大意：
&&&&&序列“未排序程度”的一个计算方式是元素乱序的元素对个数。例如：在单词序列“DAABEC'”中，因为D大于右边四个单词，E大于C，所以计算结果为5。这种计算方法称为序列的逆序数。序列“AACEDGG”逆序数为1（E与D）——近似排序，而序列``ZWQM''&逆序数为6（它是已排序序列的反序）。
&&&&&你的任务是分类DNA字符串（只有ACGT四个字符）。但是你分类它们的方法不是字典序，而是逆序数，排序程度从好到差。所有字符串长度相同。
第一行包含两个数：一个正整数n（0&n&=50）表示字符串长度，一个正整数m（0&m&=100）表示字符串个数。接下来m行，每行一个长度为n的字符串。
输出输入字符串列表，按排序程度从好到差。如果逆序数相同，就原来顺序输出。
样例输入：
AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCAT
CCCGGGGGGA
AACATGAAGG
GATCAGATTT
ATCGATGCAT
TTTTGGCCAA
TTTGGCCAAA
大致题意：
输入m个长度为n的DNA序列，把他们按照逆序数从小到大稳定排序输出。
PS:“稳定排序”就是当序列中出现A1==A2时，排序前后A1与A2的相对位置不发生改变。
&&相关文章推荐
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：584139次
积分：10734
积分：10734
排名：第1387名
原创：379篇
转载：346篇
评论：183条
文章：20篇
阅读：25664
(8)(10)(15)(8)(5)(11)(7)(6)(1)(172)(26)(3)(18)(59)(3)(11)(2)(4)(14)(12)(45)(4)(12)(8)(1)(1)(1)(4)(15)(89)(45)(1)(4)(7)(14)(58)(3)(1)(13)(11)(3)这是个机器人猖狂的时代，请输一下验证码，证明咱是正常人~}