LeetCode数据结构基础---2021/8/18

今天药忘吃喽~ 2022-09-05 12:58 94阅读 0赞

### 目录 ###

*  字母异位词分组
 *  字符串相乘
 *  重复的DNA序列
 *  最长回文子串

# 字母异位词分组 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70]  
分析：  
  字母异位词排序后相等，因此可以用排序+哈希表处理。  
代码：

class Solution { 
    public:
        vector<vector<string>> groupAnagrams(vector<string>& strs) { 
            vector<vector<string>> res;
            if(strs.size() == 0) { 
                res.push_back({ });
                res[0].push_back("");
                return res;
            }
            //排序+哈希表
            unordered_map<string, vector<string>> mp;
            vector<string> temp;
            for(int i = 0; i < strs.size(); i++) { 
                if(strs[i] == "") { 
                    mp[""].push_back("");
                    continue;
                }
                string s = strs[i];
                sort(s.begin(), s.end());
                mp[s].push_back(strs[i]);
            }
            unordered_map<string, vector<string>>::iterator it = mp.begin();
            for(; it != mp.end(); ++it) { 
                res.push_back(it->second);
            }
            return res;
        }
    };

# 字符串相乘 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 1]  
分析：  
  将字符串相乘变为：某个字符串依次与另一字符串的各位相乘，然后相加。字符串相加可以参考：[字符串相加][Link 1]  
代码：

class Solution { 
    public:
        string multiply(string num1, string num2) { 
            if (num1 == "0" || num2 == "0") { 
                return "0";
            }
            string ans = "0";
            int m = num1.size(), n = num2.size();
            for (int i = n - 1; i >= 0; i--) { 
                string curr;
                int add = 0;
                for (int j = n - 1; j > i; j--) { 
                    curr.push_back(0);
                }
                int y = num2.at(i) - '0';
                for (int j = m - 1; j >= 0; j--) { 
                    int x = num1.at(j) - '0';
                    int product = x * y + add;
                    curr.push_back(product % 10);
                    add = product / 10;
                }
                while (add != 0) { 
                    curr.push_back(add % 10);
                    add /= 10;
                }
                reverse(curr.begin(), curr.end());
                for (auto &c : curr) { 
                    c += '0';
                }
                ans = addStrings(ans, curr);  //相加
            }
            return ans;
        }
    
        string addStrings(string &num1, string &num2) { 
            int i = num1.size() - 1, j = num2.size() - 1, add = 0;
            string ans;
            while (i >= 0 || j >= 0 || add != 0) { 
                int x = i >= 0 ? num1.at(i) - '0' : 0;
                int y = j >= 0 ? num2.at(j) - '0' : 0;
                int result = x + y + add;
                ans.push_back(result % 10);
                add = result / 10;
                i--;
                j--;
            }
            reverse(ans.begin(), ans.end());
            for (auto &c: ans) { 
                c += '0';
            }
            return ans;
        }
    };

# 重复的DNA序列 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 2]  
分析：  
  滑动窗口，每滑动一个位置就判断该子串是否出现过，出现过就输出。  
代码：

class Solution { 
    public:
        vector<string> findRepeatedDnaSequences(string s) { 
            vector<string> res;
            set<string> st;
            int n = s.size();
            for(int i = 0; i < n - 10 + 1; i++) { 
                string temp = s.substr(i, 10);
                if(st.count(temp)) { 
                    res.push_back(temp);
                }
                st.insert(temp);
            }
            //去重
            set<string> t(res.begin(), res.end());
            res.assign(t.begin(), t.end());
            return res;
        }
    };

# 最长回文子串 #

[最长回文子串][Link 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70]: /images/20220829/b4684cb8c760459a8c74ee33897bfa10.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 1]: /images/20220829/57069a5161c74aafa9e92fe19faf39af.png
[Link 1]: https://blog.csdn.net/Cyril_KI/article/details/119730361
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 2]: /images/20220829/9da3afbdf3684138a8ae241a5e7610a9.png
[Link 2]: https://blog.csdn.net/Cyril_KI/article/details/119192253