算法刷题计划（八）最长公共前缀、罗马数字转整数、重复的DNA序列

• （1）最长公共前缀
• （2）罗马数字转整数
• （3）重复的DNA序列

题目：
编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 “”。

• 示例 1：

  输入：strs = [“flower”,“flow”,“flight”]
  输出：“fl”

• 示例 2：

  输入：strs = [“dog”,“racecar”,“car”]
  输出：""
  解释：输入不存在公共前缀。

• 解题方法：

class Solution {
public:
    string longestCommonPrefix(vector& strs) {
       if(!strs.size()) return "";
        int length=strs[0].size();//第一个元素长度
        int count = strs.size();//数组长度
        for(int i=0;i 
 
（2）罗马数字转整数 
解题方法：
 
class Solution {
public:
    int romanToInt(string s) {
        if(!s.size())   return -1;
        int n =s.size();
        int value=0;
        for(int i=0;i=m[s[i+1]]){
                    value+=m[s[i]];
                }
                else{
                    value-=m[s[i]];
                }
            }else{
                value+=m[s[i]];
            }
            cout<m={
        {'I',1},
        {'V',5},
        {'X',10},
        {'L',50},
        {'C',100},
        {'D',500},
        {'M',1000}
    };
};
 
 
（3）重复的DNA序列 
题目：
 
所有 DNA 都由一系列缩写为 ‘A’，‘C’，‘G’ 和 ‘T’ 的核苷酸组成，例如：“ACGAATTCCG”。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。编写一个函数来找出所有目标子串，目标子串的长度为 10，且在 DNA 字符串 s 中出现次数超过一次。
 
 
示例 1：
 
输入：s = “AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT”
 输出：[“AAAAACCCCC”,“CCCCCAAAAA”]
 
 
示例 2：
 
输入：s = “AAAAAAAAAAAAA”
 输出：[“AAAAAAAAAA”]
 
 
 
解题方法：
 
class Solution {
public:
    vector findRepeatedDnaSequences(string s) {
        int n=s.size();
        if(n<10)return {};
        vectorres;
        unordered_mapm;
        for(int i=0;i<=n-10;i++){
            string temp=s.substr(i,10);
            m[temp]++;
        }
        for(auto it=m.begin();it!=m.end();it++){
            if(it->second>1)res.push_back(it->first);
        }
        return res;
    }
};