< cnt - n - 1; i++) p = p->next;p->next = p->next->next;return dummy->next;}};
20. 有效的括号
思想
分析题目首先想到这个和栈数据结构非常相似 ， 如果是左括号的一种情况那么就选择放入栈中 ， 如果是右括号中的一种情况 ， 就去分析能否和栈顶的元素配对 ， 能配对就弹出原来的栈顶元素 ， 不能配对就说明不满足条件 false
class Solution {public:bool isValid(string s) {//可以先通过奇偶判断int n = s.size();if(n % 2 == 1) return false;unordered_map k = {{')', '('},{']', '['},{'}', '{'}};stack stack;for(auto str: s) {//判断是左括号还是右括号；左括号考虑加入栈 ， 右括号考虑是否配对if(k.count(str)) {if(stack.empty() || stack.top() != k[str]) return false;else stack.pop();} else {stack.push(str);}}return stack.empty();}};
y总的简化代码
class Solution {public:bool isValid(string s) {stack stack;for(auto ca: s) {if(ca == '(' || ca == '[' || ca == '{') stack.push(ca);else {//通过ascaii表发现配对的括号差小于2if(!stack.empty() && abs(stack.top() - ca) <= 2) stack.pop();else return false;}}return stack.empty();}};
21. 合并两个有序链表
思想
这道题目就是归并排序中的核心思想 ， 只不过是在链表的背景之下 。同时 ， 这里再次重申一下题目的小技巧 ， 凡是涉及到头节点需要特判或者头节点会变化的情况 ， 我们就创建一个虚拟头节点 。
/*** 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 Solution {public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {//创建一个虚拟头节点dummy ， 同时为了方便我们更新下一个结点 ， 使用tail节点auto dummy = new ListNode(-1), tail = dummy;//等价于 ListNode* dummy = new ListNode(-1);//ListNode* tail = dummy;//l1 和 l2 都不为空的时候判断大小while(list1 && list2) {if(list1->val < list2->val) {//tail和list1都需要更新tail = tail->next = list1;list1 = list1->next;} else {tail = tail->next = list2;list2 = list2->next;}}//当一个指针到达末尾时 ， 只需要把tail下一个节点接到不为空的那个链表后面if(list1) tail->next = list1;if(list2) tail->next = list2;return dummy->next;}};
22. 括号生成
思想
对于括号配对问题需要了解两个常用到的结论（前提是只有一种类型括号）：
左括号的数量小于等于右括号的数量时 ， 才能配对最终左右括号数量相等
对于这个问题需要给出所有的排列方式的题目 ， 我们应该条件反射的想到dfs来解决 。
代码中并没有显式的写出回溯的过程 ， 起始回溯隐藏在了if判断中 ， if的本质含义起始就是可以实现的几种方案 ， 当一种方案可行并且结束以后 ， 返回到if判断 ， 就会考虑下一个if；即通过多个if考虑了所有可能的情况
class Solution {public:vector> res;vector> generateParenthesis(int n) {dfs(n, 0, 0, "");return res;}void dfs(int& n, int ln, int rn, string path) {//当左括号数目和右括号数目都等于n的时候这条搜索路径结束if(ln == n && rn == n) res.push_back(path);else {//if含义 ， 就是dfs时当前可能走的分支情况 ， 本题就只有两种情况if(ln