LeetCode刷题笔记-数据结构-day9

LeetCode刷题笔记-数据结构-day9

文章目录

LeetCode刷题笔记-数据结构-day9

187.重复的DNA序列

1.题目描述2.解题思路3.代码 5.最长回文子串

1.题目描述2.解题思路3.代码

LeetCode刷题笔记-数据结构-day9 187.重复的DNA序列 1.题目描述

原题链接：87. 重复的DNA序列

2.解题思路

算法：哈希表

题目的意思就是要我们找出出现次数大于1的且长度为10的字符串。而且最终答案不能重复。

因此我们可以用哈希表存储每个长度为10字符串的出现的次数，只有当对应次数为2时才加入最终答案。

3.代码

class Solution {
public:
    vector findRepeatedDnaSequences(string s) {
        unordered_map hash;
        vector res;

        for(int i=0;i+10<=s.size();i++){
            string t=s.substr(i,10);
            hash[t]++;
            if(hash[t]==2) res.push_back(t);
        }
        return res;
    }
};

5.最长回文子串 1.题目描述

原题链接：5. 最长回文子串

2.解题思路

题目没有额外的要求，根据数据范围，我们可以直接暴力枚举，枚举回文串的中心，然后向两边扩展，直到不符合条件为止

这里需要分两种情况：

如果回文串为奇数，初始化两边为l=i,r=i;如果回文串为偶数，初始化两边为l=i,r=i+1;

如果遇到不同字符，则我们就找到了以 i为中心的回文串边界。

3.代码

class Solution {
public:
    string longestPalindrome(string s) {
        string res;
        int n=s.size();
        for(int i=0;i=0&&rres.size()) res=s.substr(l+1,r-l-1);

            l=i,r=i;
            while(l>=0&&rres.size()) res=s.substr(l+1,r-l-1);
        }
        return res;
    }
};