勵(lì)志用盡量少的代碼做高效表達(dá)。

---

題目（提交）鏈接→UVa-1368

---

思路：

DNA序列：按列遍歷，記錄每一列出現(xiàn)次數(shù)最多（若同樣多，則字典序最小）的字母，錄入s串累加。
距離：重新遍歷，錄入出現(xiàn)次數(shù)比最多次數(shù)少(若相等，則字典序較大的)的次數(shù)，錄入sum累加

代碼：

#include<bits/stdc++.h> using namespace std; int main() {int n; cin >> n; while(n--) {int m, n; cin >> m >> n;char c[m][n]; for(int i = 0; i < m; i++) //輸入 for(int j = 0; j < n; j++) cin >> c[i][j];int mark; //mark+'0'記錄出現(xiàn)次數(shù)最多且最小的字符 int found = 0; //記錄出現(xiàn)次數(shù)最多的位數(shù) int a[26];string s;int sum = 0;memset(a,0,sizeof(a));for(int i = 0; i < n; i++) { //i代表列for(int j = 0; j < m; j++) //j代表行 ，先遍歷行，將每行出現(xiàn)次數(shù)最多的字符找出，存入s串 a[(c[j][i]-'A')]++;for(int k = 0; k < 26; k++) //求最短漢明序列的字符。 if(a[k] > found) { //出現(xiàn)次數(shù)最多或 一樣多，但較小。 found = a[k]; mark = k;}for(int k = 0; k < 26; k++) //求次數(shù) if((a[k] < found) || ((a[k] == found) && (mark < k))) sum+= a[k];s += (mark+'A'); //將符合要求的字符錄入s串 mark = 0; //置0環(huán)節(jié) found = 0;memset(a,0,sizeof(a));}cout << s << endl << sum << endl;}return 0;}

---

二刷：

回過(guò)頭來(lái)又刷了一遍， 結(jié)合網(wǎng)上的討論成果， 有了些新的感悟。

改進(jìn)：
1. 在一段代碼中同時(shí)求出了DNA序列與hamming距離。
2. 使用map容器對(duì)‘T’‘A’‘G’‘C’與其次數(shù)做映射，求解更方便。
3. 時(shí)間復(fù)雜度由O(52*m*n)降低到了O(4*m*n)。

理論上應(yīng)該可以將時(shí)間復(fù)雜度降低到O(mn)，做法是：在輸入DNA串的同時(shí)，用二維數(shù)組存儲(chǔ)每個(gè)字符出現(xiàn)的次數(shù)， 以Max數(shù)組按列比較 ，并記錄其最大值即可。
但需要同時(shí)維護(hù)一個(gè)二維數(shù)組和一個(gè)一維數(shù)組的空間規(guī)模， 并不劃算。

---

代碼展示

#include<bits/stdc++.h> using namespace std; int main() {int T; cin>>T; while(T--) {int m, n; cin>>m>>n;string input[m];for(int i = 0; i < m; i++) cin>>input[i]; //輸入map<char, int>um; //存儲(chǔ)m個(gè)字符串中相同位置出現(xiàn)的字符及其對(duì)應(yīng)的次數(shù)int Hamming = 0; //存儲(chǔ)Hamming距離和for(int i = 0; i < n; i++) {for(int j = 0; j < m; j++) ++um[input[j][i]];char MAX = 'A';for(auto&j : um) //查找出現(xiàn)次數(shù)最多的字符if(j.second > um[MAX]) MAX=j.first;putchar(MAX); //輸出出現(xiàn)次數(shù)最多的字符Hamming += m-um[MAX];um.clear(); //清空map } cout << '\n' << Hamming << '\n'; } return 0; }

---

日拱一卒，功不唐捐。

總結(jié)

以上是生活随笔為你收集整理的21行代码AC——习题3-7 DNA序列(UVa-1368)_解题报告的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。