1. 删除无效的括号
给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
返回所有可能的结果。答案可以按 任意顺序 返回。
示例 1：
输入：s = "()())()"
输出：["(())()","()()()"]
示例 2：
输入：s = "(a)())()"
输出：["(a())()","(a)()()"]
示例 3：
输入：s = ")("
输出：[""]
提示：
1 <= s.length <= 25
s 由小写英文字母以及括号 '(' 和 ')' 组成
s 中至多含 20 个括号
出处：
https://edu.csdn.net/practice/25023636
代码：
#include <bits/stdc++.h> using namespace std; class Solution { public: vector<string> removeInvalidParentheses(string s) { vector<string> ans; rm(move(s), ans, {'(', ')'}, 0, 0); if (ans.empty()) return {""}; return ans; } void rm(string s, vector<string> &ans, vector<char> brackets, int sea_i, int del_i) { int sta = 0; for (int i = sea_i; i < s.size(); i++) { if (s[i] == brackets[0]) sta++; else if (s[i] == brackets[1]) { sta--; if (sta < 0) { for (int j = del_i; j <= i; j++) { if (s[j] == brackets[1] && (j == del_i || s[j - 1] != brackets[1])) { string new_s = s.substr(0, j) + s.substr(j + 1); rm(move(new_s), ans, brackets, i, j); } } return; } } } reverse(s.begin(), s.end()); if (brackets[0] == '(') rm(move(s), ans, {brackets[1], brackets[0]}, 0, 0); else ans.push_back(move(s)); } }; string vectorToString(vector<string> vect) { stringstream ss; ss << "[\""; for (int i = 0; i < vect.size(); i++) { ss << vect[i]; if (i < vect.size() - 1) ss << "\",\""; } ss << "\"]"; return ss.str(); } int main() { Solution sol; string s = "()())()"; cout << vectorToString(sol.removeInvalidParentheses(s)) << endl; s = "(a)())()"; cout << vectorToString(sol.removeInvalidParentheses(s)) << endl; s = ")("; cout << vectorToString(sol.removeInvalidParentheses(s)) << endl; return 0; }
输出：
["(())()","()()()"]
["(a())()","(a)()()"]
[""]
2. 合并K个升序链表
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：[1->4->5, 1->3->4, 2->6]
将它们合并到一个有序链表中得到1->1->2->3->4->4->5->6
示例 2：
输入：lists = []
输出：[]
示例 3：
输入：lists = [[]]
输出：[]
提示：
k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的总和不超过 10^4
以下程序实现了这一功能，请你填补空白处的内容：
usingnamespacestd; structListNode{ intval; ListNode*next; ListNode() : val(0), next(nullptr) {} ListNode(intx) : val(x), next(nullptr) {} ListNode(intx, ListNode*next) : val(x), next(next) {} }; classSolution{ public: ListNode*mergeKLists(vector<ListNode*>&lists) { autocmp= [](structListNode*n1, structListNode*n2) { returnn1->val>n2->val; } priority_queue<structListNode*, vector<structListNode*>, decltype(cmp)>queue(cmp); for (inti=0; i<lists.size(); i++) { if (lists[i] !=nullptr) { queue.push(lists[i]); } } structListNodedummy, *p=&dummy; ; while (!queue.empty()) { _________________; } returndummy.next; } }; ```
出处：
https://edu.csdn.net/practice/25023637
代码：
usingnamespacestd; structListNode{ intval; ListNode*next; ListNode() : val(0), next(nullptr) {} ListNode(intx) : val(x), next(nullptr) {} ListNode(intx, ListNode*next) : val(x), next(next) {} }; classSolution{ public: ListNode*mergeKLists(vector<ListNode*>&lists) { autocmp= [](structListNode*n1, structListNode*n2) { returnn1->val>n2->val; } priority_queue<structListNode*, vector<structListNode*>, decltype(cmp)>queue(cmp); for (inti=0; i<lists.size(); i++) { if (lists[i] !=nullptr) { queue.push(lists[i]); } } structListNodedummy, *p=&dummy; ; while (!queue.empty()) { ListNode*node=queue.top(); queue.pop(); p->next=node; p=node; if (node->next!=nullptr) { queue.push(node->next); } } returndummy.next; } };
输出：
略
3. 四数之和
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：答案中不可以包含重复的四元组。
示例 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
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
以下程序实现了这一功能，请你填补空白处内容：
```c++classSolution{ public: vector<vector<int>>fourSum(vector<int>&nums, inttarget) { longlongl_target=target; sort(nums.begin(), nums.end()); vector<vector<int>>results; intN=nums.size(); for (inti=0; i<N-3; i++) { if (i>0&&nums[i] ==nums[i-1]) continue; for (intj=i+1; j<N-2; j++) { if (j>i+1&&nums[j] ==nums[j-1]) continue; for (intk=j+1, l=N-1; k<l; k++) { if (k>j+1&&nums[k] ==nums[k-1]) continue; _____________________________; if (k>=l) { break; } if ((target-nums[i] -nums[j] -nums[k] -nums[l]) ==0) { results.emplace_back( vector<int>({nums[i], nums[j], nums[k], nums[l]})); } } } } returnresults; } }; ```
出处：
https://edu.csdn.net/practice/25023638
代码：
usingnamespacestd; classSolution{ public: vector<vector<int>>fourSum(vector<int>&nums, inttarget) { longlongl_target=target; sort(nums.begin(), nums.end()); vector<vector<int>>results; intN=nums.size(); for (inti=0; i<N-3; i++) { if (i>0&&nums[i] ==nums[i-1]) continue; for (intj=i+1; j<N-2; j++) { if (j>i+1&&nums[j] ==nums[j-1]) continue; for (intk=j+1, l=N-1; k<l; k++) { if (k>j+1&&nums[k] ==nums[k-1]) continue; while (k<l&& (l_target-nums[i] -nums[j] -nums[k] -nums[l]) >0) { l++; } if (k>=l) { break; } if ((target-nums[i] -nums[j] -nums[k] -nums[l]) ==0) { results.emplace_back( vector<int>({nums[i], nums[j], nums[k], nums[l]})); } } } } returnresults; } }; stringvectorToString(vector<int>vect) { stringstreamss; ss<<"["; for (inti=0; i<vect.size(); i++) { ss<<vect[i]; if (i<vect.size() -1) ss<<","; } ss<<"]"; returnss.str(); } intmain() { Solutions; vector<int>nums= {1,0,-1,0,-2,2}; for (auton: s.fourSum(nums, 0)) cout<<vectorToString(n) <<" "; return0; }
输出：
