LeetCode刷题-24.两两交换链表中的节点
题目链接：24.两两交换链表中的节点
¶题解：
链表的指针切换问题！
¶题目简述：
给定一个链表，两两相邻的做一下交换。
¶我的错误题解：
我的代码如下： l指向 2 再指向 1 ，此时2到3已经断了，会发现1和2已经成环了，会形成死循环！
我看了好久，都没发现2到3已经断了，还以为head->next->next为3了，懵逼了！
以此为戒：做链表题一定要画好图，看清哪里断了，哪里没断！
¶错误代码：
1234567891011121314151617181920/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: ListNode* swapPairs(ListNode* head) { auto dummy = new ListNode(-1), l ...
LeetCode刷题-23.合并K个排序链表
题目链接：23.合并K个排序链表
¶题解：
由二路归并变为k路归并，有优化的地方的！
¶题目简述：
k个有序链表，合并生成一个有序链表。
¶题解一：低效率（我的）
嗯，暴力去扫描每个最小值！
具体：
mint：记录当前最小的节点。
minv：记录当前最小节点所在的链表的下标
特判一下当前链表是否为空，是的话直接跳过。
如果能找到最小值，即minv != -1，则更新当前链表即最小值所在链表！
找不到最小值直接退出
时间复杂度：假设链表数组个数为 N，扫描每个最小值都要N次，所有链表元素为M的话，最终时间复杂度为 O(N*M)
欢迎查看题解二：使用堆优化！
¶AC代码一：
123456789101112131415161718192021222324252627282930313233/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; ...
LeetCode刷题-22.括号生成
题目链接：22.括号生成
¶题解：
简单的递归问题，会在题解二给出一个关于括号匹配的结论！非常重要！
¶题目简述：
给定一个n，找到所有n组括号有效可匹配的情况。
¶题解一：低效率（我的）
很明显：直接使用DFS即可！
void dfs(int l, int r, int n, string path)
l：记录左括号使用数
r：记录右括号使用数
n：记录括号组数
path：记录当前情况的括号组合
bool isMatch(string str)：判断当前括号序列是否是有效匹配
这里我使用了dfs(1, 0, n, "(")作为入口，即可以排除)开头的不可能匹配序列！虽然优化了一点点，但是还是请看题解二！
退出条件 ：l == n && r == n，即左右括号都已经使用够了n个。
这样有一个麻烦：由于这样会生成一个全排列，每次都需要判断是否是合法的括号序列，浪费了许多时间。所以请查看题解二解决这个麻烦！
¶AC代码一：
12345678910111213141516171819202122232425class Solution {public: v ...
LeetCode刷题-21.合并两个有序链表
题目链接：21.合并两个有序链表
¶题解：
经典的二路归并算法，温习一下吧！
¶题目简述：
给定两个有序链表，合并为一个有序链表！
¶题解：
二路归并：由于原序列都是有序的，所以每次选取头部的最小值即可将所有节点按从小到大排好。
嗯，不需要做过多解释！
和数组不一样的一点 ：最后某个链表非空时，可以直接指针指向非空链表的头结点即可，数组还需要进行循环去一个一个链接。
¶AC代码：
1234567891011121314151617181920212223/** * Definition for singly-linked list. * 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 S ...
LeetCode刷题-20.有效的括号
题目链接：20.有效的括号
¶题解：
嗯，经典的栈的应用，括号匹配！
¶题目简述：
给定一堆大中小括号，询问是否能完整匹配！
¶题解一：
就是经典括号匹配，具体细节自己想想就明白了！
具体思想：
左括号直接入栈
右括号先判断是不是栈空，栈空则无法匹配返回false，不空则和当前栈顶进行匹配，匹配了直接从栈中弹出，否则直接返回false
最后判断栈是否为空，不为空这说明无法完成匹配，直接返回false，其他情况返回true
¶AC代码一：
1234567891011121314151617class Solution {public: bool isValid(string s) { stack<char> stk; for(int i = 0; i < s.size(); i++){ if(stk.empty() && (s[i] == ')' || s[i] == ']' || s[i] == '}')) return false; if(s[i] == '(' ...
LeetCode刷题-19.删除链表的倒数第N个节点
题目链接：19.删除链表的倒数第N个节点
¶题解：
链表的基本操作！
¶题目简述：
如题，删除链表倒数第n个节点！
¶题解：
题目说，要使用一遍扫描解决？？？我想了想，这是不可能的，最起码都得两遍。。。
或许人家是说O(N)的时间复杂度。。。
具体做法：
同样使用一个虚拟节点 值为-1做头节点，便于操作
先计算节点总数，包括虚拟的节点
然后计算一下应该循环到哪里进行删除（即要找到要删元素的上一个元素进行删除）
如 1->2->3->4->5删除倒数第二个，加了一个虚拟节点，所以现在应该为 -1->1->2->3->4->5，即下标要遍历到总结点数-倒数的数-1，即k - n - 1即可，这时，p指向要删的倒数第n个节点的上一个节点
这时，直接p->next = p->next->next;，删除完毕！
返回dummy->next
¶AC代码：
12345678910111213141516171819202122232425/** * Definition for singly-linked li ...
LeetCode刷题-18.四数之和
题目链接：18.四数之和
¶题解：
又是使用双指针的题，双指针可以将复杂度降低一维！
这道题和LeetCode的第15题完全一样！我的第15题链接
¶题目简述：
给定一个nums数组，需要求出所有相加为target的四元组，并且要求不包含重复四元组！
¶题解：
当然可以使用暴力，嗯，，四重循环，没试过，可能会超时！
使用呢双指针将四维降到三维度，固定前两个数，后两个数使用双指针移动！
题解：参考我写的LeetCode第15题的题解。具体做法，判重，注意事项，完全一样！
时间复杂度： 第一层循环O(N)，第二层O(N)，第三层看似O(N ^ 2)，实则l和r各最多扫描N次，所以最终复杂度为O(N ^ 3)
¶AC代码：
123456789101112131415161718192021class Solution {public: vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>> r ...
LeetCode刷题-17.电话号码的字母组合
题目链接：17.电话号码的字母组合
¶题解：
嗯，，一道经典的递归问题，简单！
¶题目简述：
有一个电话，九键，和手机键盘一样，都有3-4个字母，要求按了几个数字后，要将所有组合全排列输出！
¶题解：
定义函数dfs(string digits, int u, string path)
digits：输入的按键
u：表示当前处理到第几个按键
path：表示当前处理了的按键构成的组合
递归终止条件：u == digits.size()，即每个数字都已经取了一个字母
递归过程：每个u的位置去循环每一个字母，dfs(digits, u + 1, path + c);
这个最简单的递归过程会将全排列都走一遍的！
注意： 需要特判输入为空的情况，应该直接返回，否则会返回一个带有""元素的数组。
¶AC代码：
12345678910111213141516171819class Solution {public: string str[10] = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", ...
LeetCode刷题-16.最接近的三数之和
题目链接：16.最接近的三数之和
¶题解：
嗯，也是双指针，和LeetCode的第15题（也就是我的上一篇文章的题解基本类似）。
¶题目简述：
上一题求三数字和为0， 这一题求三数之和最接近！
¶题解：
和上一题类似，求为0的三元组每次只有一种情况，即nums[i] + nums[j] + nums[k]
但是求最接近则有两种（左和右）：nums[i] + nums[j] + nums[k] - target，nums[i] + nums[j] + nums[k + 1] - target
思路是一样的，同样是双指针！思路见上一篇题解，即第15题 三数之和！
本题此题不需要去重，最终结果也只有一个！
同样需要排序！
不同之处：
nums[i] + nums[j] + nums[k] > target时，就k--，找到最接近的位置
若k + 1没有超界，则计算一下nums[i] + nums[j] + nums[k + 1]的情况（右边）
还有左边的情况（一定不会超界）
使用minv更新与目标值相差最小的差值，即最接近值，若minv发生了更新，则更新res的值为差值较小的 ...
LeetCode刷题-15.三数之和
题目链接：15.三数之和
¶题解：
又是使用双指针的题，双指针可以将复杂度降低一维！
这道题和LeetCode后面的16、18题类似。
¶题目简述：
给定一个nums数组，需要求出所有相加为零的三元组，并且要求不包含重复三元组！
¶题解：
当然可以使用暴力，嗯，，三重循环，没试过，可能会超时！
咱们有好的算法，就不去暴力求解！
使用双指针，固定第一个数，后两个数使用双指针，可以将O(N ^ 3)的复杂度降到O(N ^ 2)，即使用双指针可以将维度降低一维！
使用双指针的前提是序列得有序：
具体做法：
固定第一个数
第二个数 j 从 i + 1开始，k从 nums.size() - 1开始向内走
nums[i] + nums[j] + nums[k] > 0三数之和大于0，k就一直--，直到找到<= 0的位置，或者j与k相邻（即j = k - 1）
此时判断三数之和是不是0，是则push进去！
此时以i和j为第一二个数的情况就找完了，继续第二个数的循环。
Tips： 由于数组有序，所以我们固定第一个数，嗯，第二个数也相当于固定，去滑动第三个数，直到最接近0的位置， ...
LeetCode刷题-14.最长公共前缀
题目链接：14.最长公共前缀
¶题解：
嗯，直接做就行，注意一点细节即可！
¶题目简述：
给定一个字符串数组。求最长公共前缀！
¶题解：
首先：以第一个字符串为基准，和其他字符串一一对应比较，都相同则继续后移，累加res；不同则直接返回之前已累积的公共前缀！
一个注意点： 若其他字符串的长度小于当前第一个字符串的位置，则直接返回即可。
¶AC代码：
1234567891011121314151617class Solution {public: string longestCommonPrefix(vector<string>& strs) { string res = ""; if(strs.empty()) return res; for(int i = 0; i < strs[0].size(); i++){ char c = strs[0][i]; for(int j = 0; j < strs.size(); j++){ ...
LeetCode刷题-13.罗马数字转整数
题目链接：13.罗马数字转整数
¶题解：
和 12.整数转罗马数字类似，就是反过来问的！处理稍有不同！
¶题目简述：
给出罗马数字，转化为普通数字！
例如： “MCMXCIV” ------------> 1994
¶题解：
同样适用哈希表存储，不过与上一道题反着的，存储类型反着换了一下！
首先从左到右搜索每一位罗马字符，能找到对应的字符就给value进行累加。
应该先按两个进行搜索，因为会出现这种情况"MCMXCIV" ，先按照一个字符搜，遇到CM应该处理为900，但是按照一个字母先走，会变成C + M，就变成了 1100。这是不对的。
先按照两个搜索，然后 i += 2，然后按照一个进行搜索i += 1.
¶AC代码：
12345678910111213141516171819202122232425class Solution {public: int romanToInt(string s) { unordered_map<string, int> hash; int value = 0; hash[ ...
