# LeetCode **Repository Path**: Person1024/leet-code ## Basic Information - **Project Name**: LeetCode - **Description**: No description available - **Primary Language**: Unknown - **License**: Not specified - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 1 - **Forks**: 0 - **Created**: 2021-06-18 - **Last Updated**: 2021-07-04 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # 刷题记录 ## 10、 正则匹配<动态规划> ### 题目要求 给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。 >'.' 匹配任意单个字符 '*' 匹配零个或多个前面的那一个元素 所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。 示例 1： >输入：s = "aa" p = "a" 输出：false 解释："a" 无法匹配 "aa" 整个字符串。 示例 2: >输入：s = "aa" p = "a\*" 输出：true 解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。 示例 3： >输入：s = "ab" p = ".\*" 输出：true 解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。 示例 4： >输入：s = "aab" p = "c\*a\*b" 输出：true 解释：因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。 示例 5： >输入：s = "mississippi" p = "mis\*is\*p*." 输出：false 提示： 0 <= s.length <= 20 0 <= p.length <= 30 s 可能为空，且只包含从 a-z 的小写字母。 p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。 保证每次出现字符 * 时，前面都匹配到有效的字符 ### 题意分析 1. 首先判断一下，是否含有通配符 2. 如果没有的话，就直接判断两个字符串是否相等 3. 如果有的话，就需要考虑通配符的匹配规则\ 1. 通配符有两种:".","*" 2. ".":匹配单个任意字符 3. "*":匹配0个或者多个\*前面的字符 4. 那么从头开始匹配，然后，当发生不匹配的情况的时候，就返回false > 自己的题解，结果遇到了一个让人头疼的问题： > > 输入： > > ​ aaa > > ​ a*a > > 结果： > > ​ false > > 预期结果： > > ​ true ### 题解 #### 1、自己的 ~~~C++ // 判断是否含有通配符，可以使用string模块中的find方法 if (s.find('.') == string::npos && s.find('*') == string::npos){ // 如果两中通配符都不含的话，就直接判断两个字符串是否相等 if(strcmp(s,p) == 0) // 0的话，就代表两个字符串相等 return true; else return false; } // 下面在开始处理含有通配符的情况 // 处理含有通配符的情况，是什么思路呢？ int i = 0; // s的游标 int j = 0; // p的游标 bool flag = true; // 这里减一，是因为size返回的是字符串的长度，而i，j都是下标 while(i 大神的题解：使用迭代的方法，非常的妙 > > C++版本 ~~~C++ class Solution { public: bool isMatch(string s, string p) { if (p.empty()) return s.empty(); auto first_match = !s.empty() && (s[0] == p[0] || p[0] == '.'); // 三迭代，主要判断感觉是当前的下一个是不是* if (p.length() >= 2 && p[1] == '*') { // 如果当前的下一个是*的话，就先去判断当前的下一个的下一个和s的第一个开始比较 // 也就是说，遇到*的先不要判断，去判断后面的 // 判断完后面的，如果后面的匹配上了（长度，还有字符都匹配上了，这里前面才会返回true）,那么这里就直接返回出去了 // 这是因为*可以匹配前面的字符0次或者多次 // 如果后面的没有完全匹配上，那么，就会进入||后面的那一部分，如果第一个字符都没有匹配上的话，就直接返回出去 // 如果第一个字符匹配上了，那么就接着用s后面的字符，和p模式进行匹配，这是因为*可以匹配前面字符的0次或者多次 // 所以，如果第一个字符匹配上了，那么，就可以继续拿着这个p模式的整体和下面去比较了 return isMatch(s, p.substr(2)) || (first_match && isMatch(s.substr(1), p)); } // 这一路的分支，感觉就是用来判断之后的字符串的。 else { // 首先判断一下，当前字符有没有匹配上，然后，再去判断下一个字符有没有匹配上 // 如果当前字符串的下一个字符串，不是*， // 那么，首先要做的就是判断当前字符有没有匹配上, // 如果匹配上了，那么，就在看下面的字符串有没有匹配上， // 但是这里需要注意了，因为这个字符不是*所以，在p中就会有一个字符被消耗掉， // 再次比较的时候，就需要p向下移动一个在进行比较 return first_match && isMatch(s.substr(1), p.substr(1)); } } }; ~~~ 运行时间：200ms 消耗内存：13.2MB 整体的递归逻辑： 这里面最最精华的就是在判断*这一个通配符上面， > 1. 上面发现最通配符“ * ”之后，之所以没有看当前字符的匹配与否（first_match）而是直接去比较，*后面的那些字符串，是考虑到了 * 的匹配0个字符的特性！因为如果p中*后面的字符和s的所有字符匹配的话，即使第一个字符不匹配，那么一样可以利用 * 匹配0个的特性，将整个字符从p中消除掉，这是这个算法最智能的地方之一。 > 2. 同时，如果p中 * 后面的字符没有和s的全部字符匹配并且当前字符是匹配的话，那么就会使用s的下一个字符到最后一个字符和模式p进行比较。这样做，可能是考虑到，可能是因为s字符串中当前字符之后的字符子串中有连续的 * 前面的字符，所以再次使用模式p中的 * 去消除掉这些一样的字符。同时每消除一个，就会自动的判断一下，不用这个 * 通配符剩下的模式p的字符，能不能将s字符串中的所有字符都匹配上。这样做是这个算法中第二个智能的地方，因为它可以一边匹配，一边寻找最适合的消除字符的数量。 > 3. 最后的那一个if递归出口，其实就是一个没有通配符 * 的情况，这种情况下，模式p中的每一个字符，都只能代表一个字符，就不需要考虑通配符匹配的长度问题了。 --- C语言版本 >C++中的string是对C语言中的char* 进行了封装，许多操作，都是间接地操控底层的c_str字符串，然后，如果直接使用C语言中的字符串指针操控底层的话，就会快上很多。 ~~~C++ class Solution { public: bool isMatch(string s, string p) { return isMatch(s.c_str(), p.c_str()); } // 还是C语言快啊，C++中的string进行了一次封装就是慢了好多 bool isMatch(const char* s, const char* p) { if(*p == 0) return *s == 0; auto first_match = *s && (*s == *p || *p == '.'); if(*(p+1) == '*'){ return isMatch(s, p+2) || (first_match && isMatch(++s, p)); } else{ return first_match && isMatch(++s, ++p); } } }; ~~~ 运行时间：20ms 消耗内存：6.3MB ## 12、 整数转罗马数字 ### 题目要求 罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。 字符 数值 I 1 V 5 X 10 L 50 C 100 D 500 M 1000 例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。 通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况： I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。 X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。 给你一个整数，将其转为罗马数字。 > 示例 1: > > 输入: num = 3 > 输出: "III" > > --- > > 示例 2: > > 输入: num = 4 > 输出: "IV" > > --- > > 示例 3: > > 输入: num = 9 > 输出: "IX" > > --- > > 示例 4: > > 输入: num = 58 > 输出: "LVIII" > 解释: L = 50, V = 5, III = 3. > > --- > > 示例 5: > > 输入: num = 1994 > 输出: "MCMXCIV" > 解释: M = 1000, CM = 900, XC = 90, IV = 4. 提示： 1 <= num <= 3999 ### 题目分析 > 仔细研究罗马数字，可以发现，其实罗马数字的本质可以分成**基础数字**和**基础组合数字**，其他数字都是这两种数字的组合， > > 基本数字：I V X L C D M > > 基础组合数字：IV IX XL XC CD CM > > 将所有的数字按照从小到大的顺序进行排列：I IV V IX X XL L XC C CD D CM M > > 将阿拉伯整数先转换成罗马数字的 **基础数字和基础组合数字**，将这些基础组合数字对应的字符串进行叠加，就能得到最后的字符串 ### 题解 #### 1、自己的 ```cpp #include #include using namespace std; class Solution { public: string intToRoman(int num) { // 罗马数字对应的基础数字和基础组合数字 // I IV V IX X XL L XC C CD D CM M int roMan[] = {1,4,5,9,10,40,50,90,100,400,500,900,1000}; string roManStr[sizeof(roMan)/sizeof(int)] = {"I","IV" ,"V" ,"IX" ,"X" ,"XL" ,"L" ,"XC" ,"C" ,"CD" ,"D" ,"CM" ,"M"}; // 首先，对最大的数字进行取余 int numInt[sizeof(roMan) / sizeof(int)]; string result = ""; for(int i = sizeof(roMan)/sizeof(int) - 1;i>=0;i--){ // 求商 numInt[i] = num/roMan[i]; // 取余数 num = num%roMan[i]; // 构造返回结果 for(int j = 0;j valueSymbols[] = { {1000, "M"}, {900, "CM"}, {500, "D"}, {400, "CD"}, {100, "C"}, {90, "XC"}, {50, "L"}, {40, "XL"}, {10, "X"}, {9, "IX"}, {5, "V"}, {4, "IV"}, {1, "I"}, }; class Solution { public: string intToRoman(int num) { string roman; for (const auto &[value, symbol] : valueSymbols) { // 这个方法主要就是看看这个数字中含有几个value,value对应的符号就加几次 // 和我的在循环的层数上，一样都是两层循环，但是在执行步骤上就要精简很多了 while (num >= value) { num -= value; roman += symbol; } if (num == 0) { break; } } return roman; } }; ``` ## 13、 罗马数字转整数 ### 题目要求 罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。 > 字符 数值 > I 1 > V 5 > X 10 > L 50 > C 100 > D 500 > M 1000 例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。 通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况： I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。 X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。 给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。 > 示例 1: > > 输入: "III" > 输出: 3 > 示例 2: > > 输入: "IV" > 输出: 4 > 示例 3: > > 输入: "IX" > 输出: 9 > 示例 4: > > 输入: "LVIII" > 输出: 58 > 解释: L = 50, V= 5, III = 3. > 示例 5: > > 输入: "MCMXCIV" > 输出: 1994 > 解释: M = 1000, CM = 900, XC = 90, IV = 4. 提示： 1 <= s.length <= 15 s 仅含字符 ('I', 'V', 'X', 'L', 'C', 'D', 'M') 题目数据保证 s 是一个有效的罗马数字，且表示整数在范围 [1, 3999] 内 题目所给测试用例皆符合罗马数字书写规则，不会出现跨位等情况。 IL 和 IM 这样的例子并不符合题目要求，49 应该写作 XLIX，999 应该写作 CMXCIX 。 关于罗马数字的详尽书写规则，可以参考 罗马数字 - Mathematics 。 ### 题目分析 其实这一题和上面的第十二题差不多，但是由于不太了解罗马数字的规则，导致这一题耗费的时间太多了，这个和上面的都可以通过建立hash表解决， 这道题，有减法，就是当罗马数字左边的数字比右边的数字小的时候，那么就应该把左边的数字减掉，就是因为没看清楚这一点，还想用上面的那种，组合数字的方法，导致耗费了大量的时间还没有做出来，后来看了看题解明白了，这个规则瞬间就变得好做多了。 ### 题解 #### 1、自己的 ```cpp map symbolValue = { {'M',1000}, {'D',500}, {'C',100}, {'L',50}, {'X',10}, {'V',5}, {'I',1} }; class Solution { public: int romanToInt(string s) { int result = 0; if(s.length() == 1){ return symbolValue.find(s.at(0))->second; } for(int i = 0;isecond; break; } auto leftPtr = symbolValue.find(s.at(i)); auto rightPtr = symbolValue.find(s.at(i+1)); if(leftPtr->second < rightPtr->second){ // 反常情况 // 如果当前的这个在左边的罗马数字比在它右边的罗马数字还要小的话 ] // 就要减去这个罗马数字 result -= leftPtr->second; } else{ // 正常情况 result += leftPtr->second; } } return result; } }; ``` #### 2、大神的 > 有点不明白：unordered_map容器和map容器的区别 ```cpp class Solution { private: unordered_map symbolValues = { {'I', 1}, {'V', 5}, {'X', 10}, {'L', 50}, {'C', 100}, {'D', 500}, {'M', 1000}, }; public: int romanToInt(string s) { int ans = 0; int n = s.length(); for (int i = 0; i < n; ++i) { int value = symbolValues[s[i]]; if (i < n - 1 && value < symbolValues[s[i + 1]]) { ans -= value; } else { ans += value; } } return ans; } }; ``` #### 3、map和unordered_map的区别 [map和unordered_map的差别和使用](https://blog.csdn.net/BillCYJ/article/details/78985895) 简单来说， - map有序，内部实现了一颗红黑树，空间占用率高，适用于对顺序有要求的问题 - unordered_map无序，内部实现了一个hash表，查找的时间复杂度$O(1)$，适用于对顺序没有要求，但是数据量非常大的情况。 #### 4、map和unordered_map的使用 unordered_map的用法和map是一样的，提供了 insert，size，count等操作，并且里面的元素也是以pair类型来存贮的。其底层实现是完全不同的，上方已经解释了，但是就外部使用来说却是一致的。 > 更多具体的还是要看那个博客，上面说的很清楚，而且，要想真正的搞明白这两个容器，最好还是自己实现一下，hash表和红黑树（我还没实现过） ## 14、 最长公共前缀 ### 题目要求 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀，返回空字符串 ""。 > 示例 1： > > 输入：strs = ["flower","flow","flight"] > 输出："fl" > 示例 2： > > 输入：strs = ["dog","racecar","car"] > 输出："" > 解释：输入不存在公共前缀。 提示： 0 <= strs.length <= 200 0 <= strs[i].length <= 200 strs[i] 仅由小写英文字母组成 ### 题目分析 1. 纵向查找（自己想出来的） 1. 给定的strs中的每一个元素之间是相互独立的。 2. 想要找出公共前缀，必须每一个元素都要参与比较。 3. 先找出最短的那个字符串，拿着最短字符串的每一个字符和其他字符串分别进行比较， 4. 如果这个最短的字符串的字符和其他的字符串的对应位置的字符都匹配上了， 5. 再比较这个字符后面的字符串，直到发生不匹配的为止 2. 横向查找（这种方法，感觉比纵向查找要快上很多，但是时间复杂度是相同的都是$O(mn)$） 1. 先找出第一个和第二个的最长公共前缀， 2. 再用这个最长公共前缀去和第三个字符串比较，得到第二个最长公共前缀 3. 重复步骤1，2，直到得到最长公共前缀，或者最长公共前缀变成空串 3. 分治查找 1. ### 题解 #### 1、自己的（纵向查找） ```cpp #include #include #include using namespace std; class Solution { public: string longestCommonPrefix(vector &strs) { string shortestStr = findShortestStr(strs); // 得到最短的字符串 string longest_common_prefix = ""; bool flag = true; int curIndex = 0; for (; curIndex < shortestStr.length() && flag; curIndex++) { for (auto iter = strs.begin(); iter != strs.end(); iter++) { if (iter->at(curIndex) != shortestStr[curIndex]) { flag = false; break; } } if(flag){ // 将当前的加进去 longest_common_prefix.push_back(shortestStr.at(curIndex)); } } return longest_common_prefix; } string findShortestStr(vector &strs) const { int shortestIndex = 0; int shortestLength = strs.at(0).length(); for (int i = 0; i < strs.size(); i++) { if (shortestLength > strs.at(i).length()) { shortestLength = strs.at(i).length(); shortestIndex = i; } } return strs.at(shortestIndex); } }; int main(int argc,char* argv[]){ Solution s; string tmp; vector strs; while (cin>>tmp) { if(tmp == "#") break; strs.push_back(tmp); tmp.clear(); } string temp = s.longestCommonPrefix(strs); cout<执行用时：**8 ms**, 在所有 C++ 提交中击败了36.91% 的用户 ​ 内存消耗：**9 MB**, 在所有 C++ 提交中击败了31.23% 的用户 不得不说，第一想法永远是最low的。 #### 2、自己的（改进之后） 第一种方法的时间复杂度，按照计算的话，应该也是$O(mn)$,但是如果仔细计算所有的执行步骤的话，就会执行m+m+min（n）步，从时间复杂度上来看的话，这个改进之后的算法和之前的算法没有区别但是最终的结果，就是这个改进的方法，最终执行所需要的时间是第一种方法所需要时间的一半。 ```cpp #include #include #include using namespace std; // 时间复杂度：O(m*m*min) // 最坏的情况下：mmn // 如果直接进行比较的话，最坏的情况下：mn // 差，不如直接进行比较 // 预处理的那一部分可能就是导致这个算法差的原因 class Solution { public: // 改进一下,纵向比较 string longestCommonPrefix_2(vector &strs) { if (!strs.size()) { return ""; } // 当前是第几个字符 int curIndex = 0; // 最长公共前缀 string longestComStr(""); int length = strs[0].length(); for (; curIndex < length; curIndex++) { for (int i = 0; i < strs.size(); i++) { // 如果当前的比较的下标，超过了字符串的长度。或者当前的字符串的这个比较字符和之前的比较字符不一样 if (curIndex == strs[i].length() || strs[i].at(curIndex) != strs[0].at(curIndex)) { return longestComStr.substr(0, curIndex); // 切片操作 } } longestComStr.push_back(strs[0].at(curIndex)); } // 将他返回出去 return longestComStr; } string longestCommonPrefix(vector &strs) { string shortestStr = findShortestStr(strs); // 得到最短的字符串 string longest_common_prefix = ""; bool flag = true; int curIndex = 0; for (; curIndex < shortestStr.length() && flag; curIndex++) { for (auto iter = strs.begin(); iter != strs.end(); iter++) { if (iter->at(curIndex) != shortestStr[curIndex]) { flag = false; break; } } if (flag) { // 将当前的加进去 longest_common_prefix.push_back(shortestStr.at(curIndex)); } } return longest_common_prefix; } string findShortestStr(vector &strs) const { int shortestIndex = 0; int shortestLength = strs.at(0).length(); // 自己的这种算法，在最坏的情况下，时间复杂度：m*m*n for (int i = 0; i < strs.size(); i++) { if (shortestLength > strs.at(i).length()) { shortestLength = strs.at(i).length(); shortestIndex = i; } } return strs.at(shortestIndex); } }; int main(int argc, char *argv[]) { Solution s; string tmp; vector strs; while (cin >> tmp) { if (tmp == "#") break; strs.push_back(tmp); tmp.clear(); } string temp = s.longestCommonPrefix_2(strs); cout << temp << endl; return 0; } ``` ##### 结果 执行用时：**4 ms**, 在所有 C++ 提交中击败了88.71% 的用户 内存消耗：**9 MB**, 在所有 C++ 提交中击败了40.13% 的用户 #### 3、大神的（横向查找） ```cpp class Solution { public: string longestCommonPrefix(vector& strs) { if (!strs.size()) { return ""; } string prefix = strs[0]; int count = strs.size(); for (int i = 1; i < count; ++i) { prefix = longestCommonPrefix(prefix, strs[i]); if (!prefix.size()) { break; } } return prefix; } string longestCommonPrefix(const string& str1, const string& str2) { int length = min(str1.size(), str2.size()); int index = 0; while (index < length && str1[index] == str2[index]) { ++index; } return str1.substr(0, index); } }; ``` ##### 结果 执行用时：**4 ms**, 在所有 C++ 提交中击败了88.68% 的用户 内存消耗：**8.9 MB**, 在所有 C++ 提交中击败了80.56% 的用户 [官方题解](https://leetcode-cn.com/problems/longest-common-prefix/solution/zui-chang-gong-gong-qian-zhui-by-leetcode-solution/) ## 15、 三数之和 ### 题目要求 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。 注意：答案中不可以包含重复的三元组。 > 示例 1： > > 输入：nums = [-1,0,1,2,-1,-4] > 输出：[[-1,-1,2],[-1,0,1]] > 示例 2： > > 输入：nums = [] > 输出：[] > 示例 3： > > 输入：nums = [0] > 输出：[] 提示： 0 <= nums.length <= 3000 -105 <= nums[i] <= 105 ### 题目分析 1. 自己的暴力方法，时间复杂度：$O(N^3)$ 1. 长度小于3的直接返回`[]` 2. 找出三个数，相加为0， 1. 两两相加之后， 2. 再从所给数组中查找第三那个让他们相加为0的数字。 3. 通过0-前两数之和，查找第三个数字，使用vector容器的find方法？ 时间复杂度$O(C_n^2n) = O((n!)^2)$,时间复杂度太可怕了吧 4. 时间复杂度之所以这么恐怖的原因不在于第二步，而在于第1步，第一步的两两相加，所需要的运算次数实在是太恐怖了。 5. 想要降低时间复杂度，就需要从第1步上面减少 6. 但是问题是：怎么减少？ 7. 或者不再使用这种想法，全部打破再重新开始。 1. 参考第一题的那个两数之和，可以发现只要是两个数进行比较大小，最后得到的时间复杂度其实就是$O(n)$，可以根据这个入手。 2. 可以让0先分别减每一个数字，得到一个数组，在用这个数组中的每一个数字分别去减每一个数字，得到另一个数组，那后查找这个数字是否在所给的数组中，如果在这个数组中就将这个数字和之前两次减的数字一起返回出去 3. 时间复杂度$O(n^2)$,但是最中还是需要建立hash表 8. 上面的方法，应该还不是最好的，因为上面的方法，会认为：[0,1,-1] 和 [0 , -1 , 1]是两个数组，这样还是会发生重复 9. 题目是要求不发生重复的。所以上面的方法，还需要进行解决重复的问题，将上面的每一个数组进行排序，然后在放到hash表中，最后应该就能得到最终的结果了 2. 官方的题目分析（排序+双指针） 题目中要求找到所有「不重复」且和为 000 的三元组，这个「不重复」的要求使得我们无法简单地使用三重循环枚举所有的三元组。这是因为在最坏的情况下，数组中的元素全部为 000，即 [0, 0, 0, 0, 0, ..., 0, 0, 0] 任意一个三元组的和都为 0。如果我们直接使用三重循环枚举三元组，会得到$O(N^3)$ 个满足题目要求的三元组（其中 N 是数组的长度）时间复杂度至少为$O(N^3)$。在这之后，我们还需要使用哈希表进行去重操作，得到不包含重复三元组的最终答案，又消耗了大量的空间。这个做法的时间复杂度和空间复杂度都很高，因此我们要换一种思路来考虑这个问题。 「不重复」的本质是什么？我们保持三重循环的大框架不变，只需要保证： ``` 第二重循环枚举到的元素不小于当前第一重循环枚举到的元素； 第三重循环枚举到的元素不小于当前第二重循环枚举到的元素。 ``` 也就是说，我们枚举的三元组 (a,b,c)满足 a≤b≤c，保证了只有 (a,b,c) 这个顺序会被枚举到，而 (b,a,c)(b, a, c)(b,a,c)等等这些不会，这样就减少了重复。要实现这一点，我们可以将数组中的元素从小到大进行排序，随后使用普通的三重循环就可以满足上面的要求。 同时，对于每一重循环而言，相邻两次枚举的元素不能相同，否则也会造成重复。举个例子，如果排完序的数组为 [0, 1, 2, 2, 2, 3] ^ ^ ^ 我们使用三重循环枚举到的第一个三元组为 (0,1,2)，如果第三重循环继续枚举下一个元素，那么仍然是三元组 (0,1,2)，产生了重复。因此我们需要将第三重循环「跳到」下一个不相同的元素，即数组中的最后一个元素 3，枚举三元组 (0,1,3)。 下面给出了改进的方法的伪代码实现： ```cpp nums.sort() for first = 0 .. n-1 // 只有和上一次枚举的元素不相同，我们才会进行枚举 if first == 0 or nums[first] != nums[first-1] then for second = first+1 .. n-1 if second == first+1 or nums[second] != nums[second-1] then for third = second+1 .. n-1 if third == second+1 or nums[third] != nums[third-1] then // 判断是否有 a+b+c==0 check(first, second, third) ``` 这种方法的时间复杂度仍然为 $O(N^3)$，毕竟我们还是没有跳出三重循环的大框架。然而它是很容易继续优化的，可以发现，如果我们固定了前两重循环枚举到的元素 a 和 b，那么只有唯一的c 满足 a+b+c=0。当第二重循环往后枚举一个元素 b′ 时，由于 b′>b，那么满足 a+b′+c′=0 的c′ 一定有 c′ 0 third = third-1 // 判断是否有 a+b+c==0 check(first, second, third) ``` 这个方法就是我们常说的「双指针」，当我们需要枚举数组中的两个元素时，如果我们发现随着第一个元素的递增，第二个元素是递减的，那么就可以使用双指针的方法，将枚举的时间复杂度从 $O(N^2)$ 减少至 $O(N)$。为什么是 $O(N)$ 呢？这是因为在枚举的过程每一步中，「左指针」会向右移动一个位置（也就是题目中的 b），而「右指针」会向左移动若干个位置，这个与数组的元素有关，但我们知道它一共会移动的位置数为 $O(N)$，均摊下来，每次也向左移动一个位置，因此时间复杂度为 $O(N)$。 注意到我们的伪代码中还有第一重循环，时间复杂度为 $O(N)$，因此枚举的总时间复杂度为 $O(N^2)$。由于排序的时间复杂度为 $O(Nlog⁡N)$，在渐进意义下小于前者，因此算法的总时间复杂度为 $O(N2)$。 ### 题解 #### 1、自己的（对应题目分析中的1） ```cpp class Solution { public: vector> threeSum(vector &nums) { set> result_; if(nums.size()<3){ return {}; } vector> result; // 结果数组 unordered_map nums_m; // 构建hash表 for (int i = nums.size() - 1; i >= 0; i--) { nums_m.insert(pair(nums[i], i)); } vector second_nums; for (int i = 0; i < nums.size(); i++) { // 生成第二个数组 second_nums.push_back(0 - nums.at(i)); } vector third_nums; for (int i = 0; i < nums.size() ; i++) { int target = second_nums.at(i); // 两数相加之后的值 for (int j = 0; j < nums.size()&& i!=j; j++) { int temp = target - nums[j]; auto it = nums_m.find(target - nums[j]); // 之所以产生了重复的现象，是因为nums[j]和target-nums[j]这里的数是同一个数 if (it != nums_m.end() ) { // 三个数字都是0，显然不行 // 如果it->first = i = j的话，就说明，同一个数字用到了两次 // 这三个数字必须不是同一个数字 // 上面已经判断了一次，保证i！=j这里只需要判断一次second ！= i就可以了 if(it->second==i||it->second==j) continue; vector temp_v ={-target, it->first, nums[j]}; sort(temp_v.begin(),temp_v.end()); result_.insert(temp_v); } } } for(auto it =result_.begin();it!=result_.end();it++){ result.push_back(*it); } return result; } }; ``` ##### 结果 可以运行出来，但是超出时间限制 #### 2、官方的题解 ```cpp class Solution{ public: // 排序加双指针。官方题解 vector> threeSum(vector &nums) { vector> result; sort(nums.begin(), nums.end()); // sort方法默认是升序排列！！！ for (int i = 0; i < nums.size(); i++) { if (i != 0 && nums[i] == nums[i - 1]) continue; int r = nums.size() - 1; // 右指针 /* 这里将右指针放到最外层循环中，有点道道， 把右指针放到最外层循环中，并且不会有漏掉的情况， 就是因为，我们已经对这个数组进行排序了！！！ r+1加上l-1已经大于0了，那么nums[r+1] + nums[l]必定大于0， 所以下一次循环的时候，在r右边的根本不需要比较了 */ for (int l = i + 1; l < nums.size(); l++) { if (l != i + 1 && nums[l] == nums[l - 1]) continue; if (l >= r) break; // 保证这三个数字不是同一个数字 if (i == l || i == r) { continue; } while (l 0) { r--; // 如果一直大于0的话，就将右指针一直向左移动 } // 正好的话 if (nums[i] + nums[l] + nums[r] == 0) { result.push_back({nums[i], nums[l], nums[r]}); } // 下一次左指针向左移动，相加之后，和再次变大，变得大于0，然后在开始计算 } } } }; ``` 结果： ​ 执行用时：**104 ms,** 在所有 C++ 提交中击败了52.80% 的用户 ​ 内存消耗：**19.5 MB,** 在所有 C++ 提交中击败了62.38% 的用户 可以看出来，即使是这种双指针加排序的方法，极端情况下耗费的时间还是很长的 ## 16、 最接近的三数之和 ### 题目要求 给定一个包括 *n* 个整数的数组 `nums` 和 一个目标值 `target`。找出 `nums` 中的三个整数，使得它们的和与 `target` 最接近。返回这三个数的和。假定每组输入只存在唯一答案。 **示例：** ``` 输入：nums = [-1,2,1,-4], target = 1 输出：2 解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。 ``` **提示：** - `3 <= nums.length <= 10^3` - `-10^3 <= nums[i] <= 10^3` - `-10^4 <= target <= 10^4` ### 题目分析 1. 这一题和上面的题目有点类似 2. 首先，根据题目知道了，只存在唯一答案。 3. 接下来，就是要计算三数之和， 4. 如果直接采用暴力求解法的话，时间复杂度$O(N^3)$ ，这样提交上去肯定超时 5. 再次采用双指针+排序的方法。 1. 首先，将nums进行排序，然后确定最层循环， 2. 在确定左指针和右指针。使用algrothm库中的sort方法（升序）， 3. 判断首先判断最右边的右指针和左指针还有最层循环的数字相加，是否要大于目标值， 1. 如果大于目标值，那么就将右指针一直向左移动，直到右指针指向的数字，加上左指针指向的数字，再加上最外层循环的数字，小于目标值的时候，判断是大于目标值的最后一个数字最接近目标值，还是小于目标值的第一个数字最接近目标值。最后将这个确定的最接近目标值的数值和上一次循环的时候，记录下来的最接近目标值的数字作比较，判断这次的数字是不是更加的接近目标值，如果更加的接近目标值就将记录的数字改成这个数字，否则开始下一次循环。 2. 如果，刚开始右指针还在最右边的时候，就已经小于目标值了，那么就直接判断当前的这个值，是否比上一次循环得到的数值，更加的接近，目标值，如果更加接近目标值，就将这个数值设置成目标值，否则的话，就开始下一次循环 3. 最后再注意一点，右指针，是在最外层循环的时候，复位一次，在左指针向右移动的时候，右指针不需要重新复位 4. 最后当外层循环结束的时候，直接将最终的结果返回出来。 5. 细节处理，如果排序之后，有一样的，那么就将跳过这个。因为，如果有一样的话，那么下一次循环就会出现重复的。 6. 上面的双指针的时间复杂度好像还是在$O(N^3)$上，因为上面的代码实现还是用到了三个循环。第三层循环一直在控制着右指针的偏移，第二层循环控制着左指针的偏移，第一层循环，控制着最主要的偏移。下面在上面的基础上改进一下，将第二层循环和第三层循环改成并列的关系（上面第二层循环和第三层循环是嵌套关系）。 1. 思路可以这样想， 2. 当三个数的值大于等于target是，右指针向左移动，直到右指针小于等于左指针，或者三个数小于target的时候，退出循环。 1. 当循环退出的原因是r=l的时候，说明直到最后一组三个数相加还是大于target，所以判断最后三个数字和closet谁更加接近target， 2. 如果退出循环的原因是三个数的值小于target的话，判断是当前的三数之和更接近target还是右指针这次偏移之前的数值更加的接近target， 3. 将得到的更加接近target的三数之和closet作比较，判断那一个更加的接近target， 3. 如果三个数值小于等于target的时候，左指针向右移动，直到左指针大于等于右指针，或者三数之和大于等于target的时候，退出循环 1. 如果退出循环的原因是r=l，说明直到最后一组数据中三数之和还是小于等于target，那么就取最大的一组数据，判断这组数据和closet谁更加接近target 2. 如果退出循环的原因是三数值和大于target的话，判断当前的三个数据之和，与上一组三个数据之和，那一个更加接近target 3. 将得到的更加接近target的三数之和，与closet判断得到更加接近targte的数字 4. 注意，每次循环的时候步骤2和步骤3中只能执行一个。 7. 特殊情况：closet = target的时候，就可以直接将closet返回，不再需要看下面的操作了，加上这个特殊情况的判断的话，消耗的时间，直接就从20～40ms下降到了8ms～12ms!!! ### 题解 #### 1、自己初步的 ```cpp int threeSumClosest(vector& nums, int target) { sort(nums.begin(),nums.end()); // 排序 int length = nums.size(); int closet = nums[0]+nums[1]+nums[2]; // 先假设上 for (int i = 0; i < length; i++) { if(closet == target) return closet; int r = length-1; // 如果出现if语句中的情况说明上一次已经计算过了，那么就直接跳过，节省时间 if(i!=0&&nums.at(i) == nums.at(i-1)){ continue; } for (int l = i+1; l < length && ltarget){ // 在右指针偏移之前，将上一次计算的数值保存下来 prvNum = nums.at(i)+nums.at(l)+nums.at(r); --r; if(r<=l){ // 右指针偏移之后，如果就已经不大于左指针了，那么就直接结束这个循环，否则的话，就会出现同一个数字再一次计算中使用了两次的情况 break; } // 右指针，偏移之后的数值 curNum = nums.at(i)+nums.at(l)+nums.at(r); } // 判断是当前的数字更加接近target还是前面的数字更加接近target，并且将结果和上一次的结果再次进行判断 // closet = abs(((target - curNum)<(target - preNum) ? curNum :preNum)-target) < abs(closet-target)?((target - curNum)<(target - preNum) ? curNum:preNum):closet; // 临时的判断 int tempCloest; if(prvNum - target < target - curNum){ tempCloest = prvNum; } else{ tempCloest = curNum; } if(abs(target - closet)>abs(target - tempCloest)){ closet = tempCloest; } } } return closet; } ``` 这种算法的时间复杂度感觉还是在$O(N^3)$虽然使用了双指针，之所以这么说，是因为这个算法中还是存在三个循环（两个for，一个while）并且这三个循环，还是层层嵌套的关系，所以感觉还是$O(N^3)$,感觉这样的做法不太妥当，下面是最优的执行结果（这里是加上特殊情况判断之后的，如果没加上特殊清况判断的话，大约在20～40ms上，加上特殊情况判断之后，消耗时间明显下降，保持在了8ms~16ms之间。） 执行用时：**8 ms**, 在所有 C++ 提交中击败了89.14% 的用户 内存消耗：**9.6 MB**, 在所有 C++ 提交中击败了71.95% 的用户 #### 2、参考评论区大神的想法 自己看了评论区大神的，将第二层循环和第三册循环的关系从嵌套关系优化成了并列关系之后， ```cpp int threeSumClosest(vector&nums,int target){ sort(nums.begin(),nums.end()); //排序操作 int closet = nums[0]+nums[1]+nums[2]; for (size_t i = 0; i < nums.size(); i++) { if(closet == target) return closet; if(i!=0&&nums[i] == nums[i-1])continue; // 重复，直接跳过这次循环 int l = i+1; int r = nums.size() - 1; bool flag = false; while (l=target){ flag = true; --r; } // 如果最终循环结果到了l=r的地步就说明，所有的数字全部都大于等于target，直接判断最小的那个数字和closet谁更加接近target if(flag&&nums[i]+nums[l]+nums[r]>=target){ if(abs(nums[i]+nums[l]+nums[r+1] - target)abs(target - nums[i]-nums[l]-nums[r])) closet = nums[i]+nums[l]+nums[r]; } else{ if(abs(target - closet)>abs(target - nums[i]-nums[l]-nums[r+1])) closet = nums[i]+nums[l]+nums[r+1]; } // 这里必须要保证，进入了上面的循环就无法进入下面的循环了，所以这里的if和elseif中都要有continue continue; } // 小于0 while (l target){ if(abs(target - nums[i] - nums[l-1] - nums[r]) 执行用时：**0 ms**, 在所有 C++ 提交中击败了100.00% 的用户 内存消耗：**9.6 MB**, 在所有 C++ 提交中击败了58.81% 的用户 ## 17、 电话号码的字母组合 ### 题目要求 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。 > 示例 1： > > 输入：digits = "23" > 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"] > 示例 2： > > 输入：digits = "" > 输出：[] > 示例 3： > > 输入：digits = "2" > 输出：["a","b","c"] 提示： 0 <= digits.length <= 4 digits[i] 是范围 ['2', '9'] 的一个数字。 ### 题目分析 1. 暴力求解法 1. 通过数字和字母之间建立关系， 2. 然后再按照穷举法，将所有的组合都算出来， 3. 最后将结果返回出去，但是经过计算在输入的数字字符串的长度达到最长的时候（8位）会产生11,664个结果,这根据经验有很大的概率会超时。 2. 使用回溯的方法 1. 具体来说和上面的暴力求解法感觉差不多，就是使用到了递归的方法， 2. 使用分而治之的方法， 3. 先将整个电话号码分成两个部分（一般是从中间分开，这样好分）， 4. 然后将分开的两个部分，看看每个部分是否可以再次分成两个部分， 5. 直到分的不能再分了的时候，将这个数字对应的字符串拆分成一个一个的字符， 6. 然后保存在一个vector\之中,将这个vector返回出去， 7. 然后在调用递归的地方，将返回得到的两个vector（前一部分和后一部分）进行组合。 8. 这样在最后返回的时候，就已经将所有的组合都已经生成了。 ### 题解 #### 自己的 这次没有看官方题解，自己写的，感觉还行，就是内存空间占用有点多 ```cpp #include #include #include #include #include using namespace std; class Solution { private: // 建立映射关系 unordered_map digitsSymbol={ pair('2',"abc"), pair('3',"def"), pair('4',"ghi"), pair('5',"jkl"), pair('6',"mno"), pair('7',"pqrs"), pair('8',"tuv"), pair('9',"wxyz"), }; public: vector letterCombinations(string digits) { if(digits.empty()) return {}; // 下面是递归函数的调用 else{ char * digits_cstr = &digits.at(0); return getResultPerfect(digits_cstr,digits.length()); } } // 就想当初小甲鱼说的那样，每一个递归要有一个最高指导原则！ // 我的这个递归的最高指导原则是什么？ // 最高指导原则：将所有的字符分开，然后组合 vector getResult(string digits){ // 如果电话号码的长度仍然大于等于2，就还需要向下调用 if(digits.length()>=2){ vector prvGroup; // 前一半的电话号码字符组合 vector nextGroup; // 后一半的电话号码字符组合 vector totalGroup; // 所有的组合 // 前一半 prvGroup = getResult(digits.substr(0,digits.length()/2)); // 后一半,这里注意substr方法，这个方法的参数：pos，n，代表起始位置，然后就是切割字符串的个数， // 这个和python上面不一样，不再是所谓的“包前不包后了”！！！ // 如果n大于pos后面所剩字符的长度，那么将会发生截断，将后面所有的字符都传递进去 nextGroup = getResult(digits.substr(digits.length()/2,digits.length())); // 将这两部分进行组合，将后一部分的所有元素都添加到前一部分所有元素的后面 for(size_t i = 0;i result; for (size_t i = 0; i < symbol.length(); i++){ result.push_back(symbol.substr(i,1)); } return result; } else{ return {}; } } }; int main(int argc,char* argv[]){ Solution s; vector result = s.letterCombinations("23"); for (int i = 0; i < result.size(); i++){ cout< digitsSymbol={ pair('2',"abc"), pair('3',"def"), pair('4',"ghi"), pair('5',"jkl"), pair('6',"mno"), pair('7',"pqrs"), pair('8',"tuv"), pair('9',"wxyz"), }; public: vector letterCombinations(string digits) { if(digits.empty()) return {}; // 下面是递归函数的调用 else{ char * digits_cstr = &digits.at(0); return getResultPerfect(digits_cstr,digits.length()); } } vector getResultPerfect(char* digits,int len){ if(len>=2){ vector prv; vector next; vector total; prv = getResultPerfect(digits,len/2); next = getResultPerfect(digits+len/2,len - len/2); for(size_t i = 0;i result; for(int i = 0;i> digitsSymbol={ pair>('2',{"a","b","c"}), pair>('3',{"d","e","f"}), pair>('4',{"g","h","i"}), pair>('5',{"j","k","l"}), pair>('6',{"m","n","o"}), pair>('7',{"p","q","r","s"}), pair>('8',{"t","u","v"}), pair>('9',{"w","x","y","z"}), }; public: vector letterCombinations(string digits) { if(digits.empty()) return {}; // 下面是递归函数的调用 else{ char * digits_cstr = &digits.at(0); return getResultPerfect(digits_cstr,digits.length()); } } vector getResultPerfect(char* digits,int len){ if(len>=2){ vector prv; vector next; vector total; prv = getResultPerfect(digits,len/2); next = getResultPerfect(digits+len/2,len - len/2); for(size_t i = 0;i 示例 1： > > 输入：nums = [1,0,-1,0,-2,2], target = 0 > 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]] > 示例 2： > > 输入：nums = [], target = 0 > 输出：[] 提示： 0 <= nums.length <= 200 -109 <= nums[i] <= 109 -109 <= target <= 109 ### 解题思路 1. 排序加双指针（其实本质还是） 1. 通过前面的学习，我掌握了双指针这一个算法 2. 使用暴力求解法的话，会时间复杂度会变成$O(N^4)$（四个嵌套循环摆在那里）,但是使用双指针的话，能将后面的两个循环从嵌套形式转换成并列形式，这样会将时间复杂度从$O(N^4)$下降到$O(N^3)$ 3. 就算时间复杂度为$O(N^3)$但是这种算法，有点low，还有没有更加优化的算法？ 4. > 在使用双指针这个方法的时候，一定要搞清楚左指针l和右指针r的偏移量，需要控制好l指针和r指针什么时候进行复位操作，以及l指针和r指针的偏移操作要保证偏移之后四个数字相加不再等于target,只有这样才能保证不重复出现同一个答案 2. 官方解答一样是使用了双指针算法，我还以为官方题解会多么高端呢，害，just so so。。。 1. 虽然，解题思路一样，但是还是没忍住又去看了一边官方的代码， 2. 确实，官方就是官方，官方题解考虑到了特殊情况，“细”啊， 3. 就是排序之后，当最小的四个数字相加都大于target的话，那么就可以直接跳出循环了， 4. 如果当前的i j r r-1四个索引指向的数字相加，结果还是小于target的话，那么就说明j该向下移动一次了，所以就直接跳过本次循环， 5. 经过这些特殊情况的改进之后，消耗的时间瞬间缩小了十倍左右，真的真的太恐怖了，（但其实代码中就加了两个if语句进行判断） 6. 总结出一个规律：考虑特殊情况非常重要 #### 1、自己的 ```cpp #include #include #include using namespace std; class Solution { public: vector> fourSum(vector& nums, int target) { if (nums.size()<4){ return {}; } sort(nums.begin(),nums.end()); // 排序操作 int r,l; // 定义左右指针 vector> result; // 保存结果的变量 for (size_t i = 0; i < nums.size(); i++){ // 重复跳过 if(i!=0&&nums[i]==nums[i-1]){ continue; } for(size_t j = i+1;j{nums[i],nums[j],nums[l],nums[r]}); // 注意完成这一步之后，有可能l target的话，就会无法进入，导致了忽略了一些答案 // 所以这里如果是相等的话，那么就需要让左指针向右再偏移一次， /* 这里需要特殊考虑一步，真的让左指针向右偏移一次就能保证curNum > target了吗？ 如果nums[l+1] == nums[l]成立的话呢？ 所以这里可能不只要偏移一次，可能要偏移很多次 下面的右指针向左偏移也是一样的道理 */ // 这样，在l target // 当然，如果l++之后，已经不小于r了的话，下面的循环就不会进入， // 直接让j++，开始下一次循环 l++; while (l target){ r--; curNum = nums[i]+nums[j]+nums[l]+nums[r]; } if(l>=r) break; else if(l{nums[i],nums[j],nums[l],nums[r]}); // 此时已经满足了curNum == target的条件了，并且ll的情况下，第三层while循环仍然会继续进行， // 当r--的时候，就会出现curNum < target的情况，再次开始重新的判断 r--; while (l nums = {-3,-2,-1,0,0,1,2,3}; vector> result; Solution s; result = s.fourSum(nums,0); for (size_t i = 0; i < result.size(); i++){ for (size_t j = 0; j < result.at(i).size(); j++){ cout<> fourSum(vector& nums, int target) { if (nums.size()<4){ return {}; } sort(nums.begin(),nums.end()); // 排序操作 int r,l; // 定义左右指针 vector> result; // 保存结果的变量 r = nums.size()-1; for (size_t i = 0; i < nums.size() - 3; i++){ // 重复跳过 if(i!=0&&nums[i]==nums[i-1]){ continue; } for(size_t j = i+1;jtarget){ break; } else if(nums[j]+nums[i] + nums[r - 1] + nums[r] {nums[i],nums[j],nums[l],nums[r]}); // 注意完成这一步之后，有可能l target的话，就会无法进入，导致了忽略了一些答案 // 所以这里如果是相等的话，那么就需要让左指针向右再偏移一次， /* 这里需要特殊考虑一步，真的让左指针向右偏移一次就能保证curNum > target了吗？ 如果nums[l+1] == nums[l]成立的话呢？ 所以这里可能不只要偏移一次，可能要偏移很多次 下面的右指针向左偏移也是一样的道理 */ // 这样，在l target // 当然，如果l++之后，已经不小于r了的话，下面的循环就不会进入， // 直接让j++，开始下一次循环 l++; while (l target){ r--; curNum = nums[i]+nums[j]+nums[l]+nums[r]; } if(l>=r) break; else if(l{nums[i],nums[j],nums[l],nums[r]}); // 此时已经满足了curNum == target的条件了，并且ll的情况下，第三层while循环仍然会继续进行， // 当r--的时候，就会出现curNum < target的情况，再次开始重新的判断 r--; while (l > 示例 1： > > 输入：head = [1,2,3,4,5], n = 2 > 输出：[1,2,3,5] > 示例 2： > > 输入：head = [1], n = 1 > 输出：[] > 示例 3： > > 输入：head = [1,2], n = 1 > 输出：[1] 提示： 链表中结点的数目为 sz 1 <= sz <= 30 0 <= Node.val <= 100 1 <= n <= sz ### 解题思路 1. 通过递归，进行删除第n个节点 1. 写了八九道题，我也感觉出来递归的特点了，递归，递归——递推归纳 2. 就是说，递归就好像是一个来回一样，递归可以向下走，但是肯定不能一直向下走，当到达了递归的终点（递归出口，或者叫做递归返回条件）之后，这个递归函数就会“原路返回”，利用这个特点，我们就可以将第n个节点删除 3. 首先，关于链表，我喜欢使用头节点是哑节点的链表（就是哑节点就是节点的数据域不存放数据），因为这种链表可以不用特殊考虑“头删”的问题。 4. 然后，我们给这个递归函数传递进去一个char类型的变量num的引用，用来记录从递归的底部已经返回了几步（变量num的意义就是倒数第几个）。 5. 然后判断当num == n的时候，使用一个静态变量ListNode* nextPtr 将当前的这个节点记录下来， 6. 当这个递归函数继续返回一步，让当前节点的next指针指向nextPtr->next指向的节点，同时将nextPtr指向的节点删除掉，再让nextPtr变量指向nullptr，防止空指针的出现 2. 快慢指针（感觉这个算法比较好，因为一边遍历就能将这个节点删除） 1. 这个是官方给的题解，大体思路就是通过两个指针，一个指针超前另一个指针n个节点，那么这两个节点之间就存在n-1个节点 2. 当快的那个指针遍历到链表尾部的时候，慢的那个指针恰好遍历到倒数第n个节点， 3. 但是这里是单链表，所以这里我们要让快的那个指针超前慢的那个指针n+1个节点而不是n个节点，也就是说当快指针遍历到最后一个节点的时候，慢的那个指针就已经到了倒数第n+1个节点了。 4. 这也就是我们要删除的节点的直接前驱节点，然后让这个前驱节点的next指针赋值为前前驱节点的next->next 5. 最后，将前驱节点的next指向的节点删除 3. 栈思想 1. 利用栈『先入后出』的想法，将这个链表倒序之后，将前n个节点出栈，那么当前的栈顶元素就是倒数第n+1个节点了，也就是我们要删除的节点的直接前驱节点， 2. 之后的逻辑就和一般删除节点的想法一样了 4. 循环遍历 1. 先获取到整条链表的长度length，然后再遍历到length - n - 1的位置， 2. 当前位置，就是要删除节点的直接前驱节点 3. 之后就是删除节点 ### 题解 #### 1、自己的（递归） ```cpp /* @File : removeNthFromEnd.cpp @Time : 2021/06/28 10:45:39 @Author : 1024Person @Version : 1.0 @Contact : 822713663@q.com @Desc : leetCode第19题删除倒数第n个节点 */ struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {} }; class Solution { public: /* * 用递归的最高指导方针：只要没有到最后一个指针，就一直向下偏移 * 当，到了最后一个节点的时候，开始返回， * 同时将num++， * 一直判断到num == n的时候，将当前的这个节点保存到nextPtr中 * 到了num == n+1的时候，将当前的这个节点的next指针指向nextPtr节点的next指针指向的节点 */ ListNode *removeNthFromEnd(ListNode *head, int n,char &num){ static ListNode *nextPtr = nullptr; if (!head){ return head; } else{ removeNthFromEnd(head->next, n,num); num++; // 从后往前，记录当前回溯到了那一步 if (num == n){ nextPtr = head; } else if (n + 1 == num){ head->next = nextPtr->next; delete nextPtr; nextPtr = nullptr; } } return head; } ListNode *removeNthFromEnd(ListNode *head, int n){ char num = 0; ListNode * dumy = new ListNode(0,head); removeNthFromEnd(dumy,n,num); head = dumy; delete dumy; dumy = nullptr; return head; } }; ``` ##### 结果 **执行用时**：**4 ms**, 在所有 C++ 提交中击败了**82.90%** 的用户 **内存消耗**：**10.4 MB**, 在所有 C++ 提交中击败了**29.73%** 的用户 这个结果在时间消耗上算是挺短的了，但是在内存消耗上，我是真的不知道，那些人是怎么做到的，把内存消耗降的那么底 时间复杂度：$O(L)$ 空间复杂度：$O(1)$ #### 2、快慢指针 ```cpp ListNode* doublePtr(ListNode* head,int n){ ListNode* first,*second; first = head; auto dumy = new ListNode(0,head); second = dumy; for (int i = 0; i < n; i++){ first = first->next; } while (first){ first = first->next; second = second->next; } auto temp = second->next; second->next = temp->next; delete temp; temp = dumy->next; delete dumy; return temp; } ``` ##### 结果 **执行用时**：**0 ms**, 在所有 C++ 提交中击败了**100.00%** 的用户 **内存消耗**：**10.3 MB**, 在所有 C++ 提交中击败了**94.31%** 的用户 **时间复杂度**：$O(L)$ **空间复杂度**：$O(1)$ 虽然快慢指针的时间复杂度，和空间复杂度和递归算法的一样，但是要注意一点：时间复杂度和空间复杂度都是在循环次数或者递归次数趋向于无穷大的时候，起作用的，这显然`1 Example 1: > > Input: s = "()" > Output: true > Example 2: > > Input: s = "()[]{}" > Output: true > Example 3: > > Input: s = "(]" > Output: false > Example 4: > > Input: s = "([)]" > Output: false > Example 5: > > Input: s = "{[]}" > Output: true ### 题目分析 1. 1. 这题，没有啥思路，感觉根据官网要求自己先看看吧 2. 首先在题目要求中有这样的两句话： >- Open brackets must be closed by the same type of brackets. > >- Open brackets must be closed in the correct order. >- brackets:括号 3. 这提供了解题的思路，首先就是括号必须使用相同的类型进行闭合， 4. 其次括号闭合的顺序，必须正确。 5. 关于第四条，怎样的闭合顺序才算是正确的呢？ 6. 按照数学上来说的话，中括号里面不能有大括号，小括号里面不能有中括号 7. 也就是说，在中括号闭合之前，不能遇到大括号， 8. 在小括号闭合之前不能遇到中括号 9. 我们规定每个符号的优先级，然后将括号闭合的顺序改成优先级的排列顺序 10. 小括号：5 -5,中括号：3 -3，大括号：1 -1 11. 所有优先级相加，和必须是0， 12. 判断结果得到的在括号没有闭合之前，所有的数字，必须是从达到小排列的！ 13. 根据以上思路我们开始编程 2. 靠!!!!被耍了,leetcode上面竟说:"([])"这种是合理的,也就是说根本不管数学上的那一套!!! 3. 通过“2”其实就可以发现了，我们上面的问题分析，并不好，这样需要对各种情况分别进行分析，但是我们自己又怎么可能 想到所有的情况呢？而且这样并不是一个算法题目该有的思路 4. 下面开始正确的解题思路 1. 首先，我们指导每一个中括号都需要进行闭合，并且还是需要正确的类型进行闭合， 2. **我们知道了一种规律：后遇到的左括号先闭合！** 3. 利用栈结构，每次将遇到的左括号放到栈顶，然后当遇到右括号的时候和栈顶元素进行比较，看看是否能够匹配 4. 如果不能匹配，或者栈是空栈，那么字符串s不符合要求，直接返回false， 5. 如果匹配的话，就将这个栈顶元素出栈 6. 遍历结束之后，如果栈中没有左括号，就是说栈是一个空栈那么返回true 5. 一种比较奇妙的解题思路（当然这种算法对于C++来说可能并不简单） 1. 我们知道，一个字符串中虽然可能会存在嵌套的情况，但是在最里面的永远是闭合的括号， 2. 那么，如果是一个合格的字符串的话，那么我们将最里层的括号替换成""之后，那么次里层的那个括号还是应该是闭合的。 3. 依次类推，将次里层的括号变成""之后，再往外一层还是闭合的括号， 4. 最后，将所有的括号都替换成了""之后，那么这个字符串将会是空， 5. 如果不是一个合法的字符串的话，最后，这个字符串，不是空， [unordered_map中find和count函数的区别](https://blog.csdn.net/qq_44879626/article/details/116192494) [C++ unordered_map count()用法及代码示例](https://vimsky.com/examples/usage/unordered_map-count-in-c.html) ### 题解 ### 1、栈+map解法 ```cpp class Solution { public: bool isValid(string s) { if(s.size()%2){ // 如果是奇数就直接返回 return false; } // 对应关系 unordered_map pairs = { {')','('}, {']','['}, {'}','{'}, }; stack stk; // 左括号栈元素 for (char ch:s){ // C++的新用法 // 右括号 if(pairs.count(ch)){ // 不匹配 if(stk.empty() || stk.top() != pairs.find(ch)->second){ return false; } // 匹配 else{ stk.pop(); // 出栈 } } // 左括号 else{ stk.push(ch); // 如栈 } } return stk.empty(); } }; ``` 这种栈加map的方法，耗时非常的短，但是因为使用到了一个栈和一个map所以占用的内存有点多，下面是改进方法，只是用栈而不使用map #### 结果 **执行用时**：**0 ms**, 在所有 C++ 提交中击败了**100.00%** 的用户 **内存消耗**：6.3 MB, 在所有 C++ 提交中击败了**10.64%** 的用户 ### 2、栈解法 ```cpp class Solution { public: bool isValid(string s) { if(s.size()%2){ // 如果是奇数就直接返回 return false; } stack stk; // 左括号栈元素 for (char ch:s){ // C++的新用法 // 左括号 if(ch == '('){ stk.push(')'); } else if (ch == '['){ stk.push(']'); } else if(ch == '{'){ stk.push('}'); } // 右括号，不匹配 else if(stk.empty()||ch != stk.top()){ return false; } // 匹配 else{ stk.pop(); } } return stk.empty(); } }; ``` #### 结果 执行用时：**0 ms,** 在所有 C++ 提交中击败了**100.00%** 的用户 内存消耗：**6.1 MB**, 在所有 C++ 提交中击败了**90.18%** 的用户 ### 3、替换解法 ```cpp bool isValid(string s){ if(s.size()%2){ return false; } int length = s.length(); for (size_t i = 0; i < length / 2 && !s.empty();i++){ int idx = s.find("()"); // 查找（）的位置 if(idx!=s.npos){ s.replace(idx,2,"");// 将小括号替换成"" } idx = s.find("[]"); if(idx!=s.npos){ s.replace(idx,2,""); } idx = s.find("{}"); if(idx!=s.npos){ s.replace(idx,2,""); } } return s.empty(); } ``` #### 结果 **执行用时**：72 ms, 在所有 C++ 提交中击败了**38.45%** 的用户 **内存消耗**：6 MB, 在所有 C++ 提交中击败了**99.39%** 的用户 从结果上来看的话，消耗内存确确实实减小了，但是这时间消耗增长的也太大了吧！ ## [21、Merge Two Sorted Lists](https://leetcode-cn.com/problems/merge-two-sorted-lists/) ### Subject Requirements Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists. > Example 1: > > Input: l1 = [1,2,4], l2 = [1,3,4] > Output: [1,1,2,3,4,4] > Example 2: > > Input: l1 = [], l2 = [] > Output: [] > Example 3: > > Input: l1 = [], l2 = [0] > Output: [0] Constraints: The number of nodes in both lists is in the range [0, 50]. -100 <= Node.val <= 100 Both l1 and l2 are sorted in non-decreasing order. ### Topic analysis 1. 迭代 1. 合并两条有序链表，首先就是要注意这两条链表已经是拍好序的， 2. 最暴力的解法，就是使用两个下标指针， 3. 然后，通过两个指针的不断偏移，比较指针指向的节点的val的大小 4. 将短的链表中的数据插入到长的链表当中去 5. 这里还是需要注意一下链表操作的一些细节的地方 2. 递归 1. $$ \begin{cases} list1[0] + merge(list1[1:],list2) & \text{list1[0] < list2[0]}\\ list2[0] + merger(list1,list2[1:])&\text{otherwise} \end{cases} $$ 2. 使用递归需要提前建模！！ 3. 就是小甲鱼之前说的最高指导方针 ### Solution #### 1、迭代，自己的 ```cpp class Solution { public: ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) { // 两条空链表 if (!l1 && !l2) { return nullptr; } else if(!l1 && l2){ return l2; } else if(!l2 && l1){ return l1; } ListNode *cur1 = l1; // l1的游标指针 ListNode *cur2 = l2; // l2的游标指针 ListNode *dnmy1 = new ListNode(0, l1); ListNode *dnmy2 = new ListNode(0, l2); ListNode* prev1 = dnmy1; ListNode* prev2 = dnmy2; // 开始比较 // 将l2中的数据向l1中插入 while (cur1 && cur2) { if (cur2->val < cur1->val) { /* 将l2的链表中的数据插入到l1的链表中， * 在插入之前要先将l2链表处理好， * 不能让l2这个链表断了！ * 从l2中删除这个节点 * 将这个节点插入到l1中 */ // 从l2中安全的将cur2这个节点摘下来 prev2->next = cur2->next; // 将cur2这个节点，安装到l1上面 prev1->next = cur2; cur2->next = cur1; prev1 = cur2; // 当l1中插入数据之后，要保证prev1紧紧跟在cur1的前面，否则就会出错 // 这里的复位操作，可以再仔细考虑考虑，链表有序这个特点 /* 首先，链表是有序的，越来越大的，那么当前要比较的数据肯定比上一个数据要大 那么，当前数据，就不再需要和之前的数据进行比较了， 因为：如果ac，那么b>c 对应在代码方面表示就是，将cur1指针不需要再进行复位操作了，只需要将cur2进行复位操作 */ cur2 = dnmy2->next; prev2 = dnmy2; } else { // 如果l2的数据还是大于l1中的数据，那么就继续向后移动l2的游标指针 // 并且，保持l1的指针不要动 prev1 = cur1; cur1 = cur1->next; } } // cur1最大的那个数据都比cur2当前的数据还要小了，那么就直接将cur2剩下的部分接在cur1后面，就好了 if(cur1 == nullptr && cur2!=nullptr){ prev1->next = cur2; } /* 如果cur2 = nullptr且cur1！=nullptr的话， 就说明将l2中的所有数据都进行比较完了，cur2走到了终点，但是cur1没有走到终点 那么cur1剩下的部分，没有参与比较，但是cur1本身就是有序的，所以整个l1，保持有序 至于最后一种情况：cur1 == nullptr & cur2 == nullptr应该是不会发生了， 因为在代码中我们已经规定了，每次循环能够移动的指针只有一个，当这次其中一个指针到达了nullptr， 那么循环就会退出，而上一次循环能够进入的条件，就是两个指针都不是nullptr， 那么这次有一个指针是nullptr了，循环会接着退出，那么另一个指针也就无法再进行偏移了， 最后就会导致两个指针无法同时到达nullptr */ l1 = dnmy1->next; l2 = dnmy2->next; delete dnmy2; delete dnmy1; return l1; } }; ``` 题目中给的链表还是头节点存着数据的链表，我不是很喜欢使用这种链表，自己添加了两个哑节点，重新连接到了两个头节点上了。这样也就导致了空间占用比较大，但是理解上比较容易理解。 ##### Result **执行用时：4 ms,** 在所有 C++ 提交中击败了**97.73%** 的用户 **内存消耗：14.5 MB,** 在所有 C++ 提交中击败了**12.06%** 的用户 这个算法的时间复杂度是$O(n+m)$因为我这里的第一个链表的游标指针没有复位操作！！之所以没有复位操作，在代码中给予了数学上的证明，证明代码的可行性 #### 2、迭代，官方题解 ```cpp class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode* preHead = new ListNode(-1); ListNode* prev = preHead; while (l1 != nullptr && l2 != nullptr) { if (l1->val < l2->val) { prev->next = l1; l1 = l1->next; } else { prev->next = l2; l2 = l2->next; } prev = prev->next; } // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可 prev->next = l1 == nullptr ? l2 : l1; return preHead->next; } }; ``` 不得不说，官方的题解，就是精妙，这里就使用一个指针，就将两个链表合起来了，妙啊妙啊。 这里首先构建一个哑节点PreHead，然后prev就好像是preHead节点的手下，然后通过l1和l2进行比较，然后将小的那个数字放到prev中，再将l1，l2进行偏移，然后，将l1和l2都比较完了之后，l1和l2两个链表中一定是一个到了nullptr另一个没有到nullptr（这个在上面我自己的代码中我已经证明过了，这里同理），所以将没有比较完的那个链表接到prev的next上，再将preHead->next返回出去。 确实比我写的代码量少多了。！！而且也没有那么多出bug的地方 ##### Result 执行用时：4 ms, 在所有 C++ 提交中击败了97.73% 的用户 内存消耗：14.3 MB, 在所有 C++ 提交中击败了95.01% 的用户 #### 3、递归递归，官方题解 ```cpp class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if (l1 == nullptr) { return l2; } else if (l2 == nullptr) { return l1; } else if (l1->val < l2->val) { l1->next = mergeTwoLists(l1->next, l2); return l1; } else { l2->next = mergeTwoLists(l1, l2->next); return l2; } } }; ``` ##### Result 用递归更简单，代码量少的可怜，但是时间复杂度和迭代是完全一样的，只不过空间复杂度比迭代大，在调用函数的时候需要消耗栈空间，消耗空间的大小取决于递归深度。 ## [22. Generate Parentheses](https://leetcode-cn.com/problems/generate-parentheses/) ### Subject Requirements Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. > Example 1: > > Input: n = 3 > Output: ["((()))","(()())","(())()","()(())","()()()"] > Example 2: > > Input: n = 1 > Output: ["()"] ### Topic analysis 1. 没有思路， 1. 首先，输入一个正整数n，然后生成由n对括号组成的合理的字符串。 2. 看了评论区大神的思路：**（最高指导思想）左括号的使用个数不能小于右括号的使用个数** 1. 可以根据这个思路来实现递归。 2. 递归的细节：每一个分支在满足上面的最高直到方针的同时不断的向更深度递归，当到达底部的时候，将当前分支上的字符串添加到result数组中去 ### Solution ```cpp class Solution { public: vector generateParenthesis(int n){ vector result; string current; genAllParent(current,result,n,n); return result; } // ln左括号的剩余数量，rn右括号的剩余数量 void genAllParent(string& current,vector& result,int ln,int rn){ // 到达底部 if (ln==0&&rn == 0){ result.push_back(current); return; } // 左括号的剩余数量比右括号的多，不满足 else if(ln>rn ){ return; } // 符合条件的左右括号 else if (ln<=rn && ln!=0 && rn!=0){ string lstring = current; lstring += "("; genAllParent(lstring,result,ln-1,rn); string rstring = current; rstring+=")"; genAllParent(rstring,result,ln,rn-1); } // 左括号已经没有了，只剩下了右括号 else if(ln 0){ current += ")"; genAllParent(current,result,ln,rn-1); } return; } }; ``` #### 结果 **执行用时：4 ms,** 在所有 C++ 提交中击败了**73.97%** 的用户 **内存消耗：13.3 MB,** 在所有 C++ 提交中击败了**48.43%** 的用户 在题解中看到了很多看不懂的算法，但是对号入座之后，发现自己写的这个算法是深度优先遍历算法，这种算法在树的遍历中经常的用到。这种方法还叫做回溯法，有点不懂， 在题解中还看到了一个种方法：[剪枝法](https://leetcode-cn.com/problems/generate-parentheses/solution/hui-su-suan-fa-by-liweiwei1419/) ## [23.Merge k Sorted Lists](https://leetcode-cn.com/problems/merge-k-sorted-lists/) ### Subjecct Requirements You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it. > Example 1: > > Input: lists = [[1,4,5],[1,3,4],[2,6]] > Output: [1,1,2,3,4,4,5,6] > Explanation: The linked-lists are: > [ > 1->4->5, > 1->3->4, > 2->6 > ] > merging them into one sorted list: > 1->1->2->3->4->4->5->6 > Example 2: > > Input: lists = [] > Output: [] > Example 3: > > Input: lists = [[]] > Output: [] Constraints: k == lists.length 0 <= k <= 10^4 0 <= lists[i].length <= 500 -10^4 <= lists[i][j] <= 10^4 lists[i] is sorted in ascending order. The sum of lists[i].length won't exceed 10^4. ### Topic analysis 1. 可以使用递归 1. 递推公式： $$ sort(k,sort(k-1,sort(k-2,sort(\cdots sort(2,1))))) $$ 2. 根据上面的递推公式，排序的时候两条两条的排序，按照深度优先递归，将最低下的两条链表排序出来，然后将排序完成的在和上一条进行排序，以此类推，当到了最上面的那一条链表排序完成之后就会直接返回出来了