输入m个长度均为n的DNA序列,求一个DNA序列,到所有序列的总Hamming距离尽量小。两个等长字符串的Hamming距离等于字符不同的位置个数,例如,ACGT和GCGA的Hamming距离为2(左数第1, 4个字符不同)。
输入整数m和n(4≤m≤50,4≤n≤1000),以及m个长度为n的DNA序列(只包含字母A,C,G,T),输出到m个序列的Hamming距离和最小的DNA序列和对应的距离。如有多解,要求为字典序最小的解。例如,对于下面5个DNA序列,最优解为TAAGATAC。
TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT文章来源:https://www.toymoban.com/news/detail-724410.html
解法文章来源地址https://www.toymoban.com/news/detail-724410.html
use std::{collections::HashMap, io};
fn main() {
let mut grid: Vec<Vec<char>> = vec![];
let mut buf = String::new();
io::stdin().read_line(&mut buf).unwrap();
let mut iter = buf.split_whitespace();
let m: usize = iter.next().unwrap().parse().unwrap();
let n: usize = iter.next().unwrap().parse().unwrap();
for _i in 0..m {
let mut buf = String::new();
io::stdin().read_line(&mut buf).unwrap();
let cs = buf.trim().chars().collect();
grid.push(cs);
}
/*for s in &grid {
let s: String = s.iter().collect();
println!("{:?}", s);
}*/
let mut ans = String::new();
for i in 0..n {
let mut kv = HashMap::new();
for j in 0..m {
kv.entry(grid[j][i])
.and_modify(|num| *num += 1)
.or_insert(1);
}
let mut mc = (' ', 0);
let mut cs: Vec<_> = kv.keys().collect();
cs.sort();
for k in cs {
if kv.get(k).unwrap() > &mc.1 {
mc = (*k, *kv.get(k).unwrap());
}
}
ans.push(mc.0);
}
println!("{}", ans);
}
到了这里,关于DNA序列(DNA Consensus String, ACM/ICPC Seoul 2006, UVa1368) rust解法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!