链接https://www.lintcode.com/problem/1900/description题解https://www.lintcode.com/problem/1900/solution/34926class Solution { public: /** * param gene1: a string * param gene2: a string * return: return the similarity of two gene fragments */ string geneSimilarity(string gene1, string gene2) { // write your code here std::pairvectorint, vectorchar s1 split(gene1); std::pairvectorint, vectorchar s2 split(gene2); int i 0; int j 0; int m s1.first.size(); int n s2.first.size(); int sum sum_count(s1.first); int same_count 0; while (i m j n) { //cout s1.second[i] s2.second[j] endl; //cout s1.first[i] s2.first[j] endl; if (s1.second[i] s2.second[j]) { same_count min(s1.first[i], s2.first[j]); } if (s1.first[i] s2.first[j]) { s1.first[i] - s2.first[j]; j; } else if (s1.first[i] s2.first[j]) { s2.first[j] - s1.first[i]; i; } else { i; j; } } return to_string(same_count) / to_string(sum); } std::pairvectorint, vectorchar split(const std::string gene) { vectorint count; vectorchar str; for (int i 0; i gene.size();) { int sum 0; while (i gene.size()) { if (!(0 gene[i] gene[i] 9)) { break; } sum sum * 10 (gene[i]-0); //cout sum endl; i; } count.push_back(sum); str.push_back(gene[i]); i; } return pairvectorint, vectorchar(count, str); } int sum_count(vectorint nums) { int sum 0; for (auto num : nums) { sum num; } return sum; } };
