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

骑猪看日落 2023-10-01 16:28 36阅读 0赞

#### 文章目录 ####

*  LeetCode刷题笔记-数据结构-day9
 *   *  187.重复的DNA序列
     *   *  1.题目描述
         *  2.解题思路
         *  3.代码
     *  5.最长回文子串
     *   *  1.题目描述
         *  2.解题思路
         *  3.代码

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

### 187.重复的DNA序列 ###

#### 1.题目描述 ####

> 原题链接：[87. 重复的DNA序列][87. _DNA]

![image-20220123102311121][]

#### 2.解题思路 ####

算法：哈希表

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

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

#### 3.代码 ####

class Solution {
        
    public:
        vector<string> findRepeatedDnaSequences(string s) {
        
            unordered_map<string,int> hash;
            vector<string> 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. 最长回文子串][5.]

![image-20220123102443388][]

![image-20220123102438379][]

#### 2.解题思路 ####

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

这里需要分两种情况：

1.  如果回文串为`奇数`，初始化两边为`l=i,r=i;`
2.  如果回文串为`偶数`，初始化两边为`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<n;i++){
        
                int l=i,r=i+1;
                while(l>=0&&r<n&&s[l]==s[r]) l--,r++;
                if(r-l-1>res.size()) res=s.substr(l+1,r-l-1);
    
                l=i,r=i;
                while(l>=0&&r<n&&s[l]==s[r]) l--,r++;
                if(r-l-1>res.size()) res=s.substr(l+1,r-l-1);
            }
            return res;
        }
    };

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBATEwuTEVCUk9O_size_20_color_FFFFFF_t_70_g_se_x_16]

[87. _DNA]: https://leetcode-cn.com/problems/repeated-dna-sequences/
[image-20220123102311121]: https://img-blog.csdnimg.cn/img_convert/4a8fa8737c85ebe862653923c30638d3.png
[5.]: https://leetcode-cn.com/problems/longest-palindromic-substring/
[image-20220123102443388]: https://img-blog.csdnimg.cn/img_convert/3061a2a697d96d3fe3c8ef28fc168415.png
[image-20220123102438379]: https://img-blog.csdnimg.cn/img_convert/f988e98607f1272ccc6f2277d90664f6.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBATEwuTEVCUk9O_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/0501e447dfd94f0c8b943ba47a609222.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBATEwuTEVCUk9O,size_20,color_FFFFFF,t_70,g_se,x_16