1. 删除无效的括号
给你一个由若干括号和字母组成的字符串s ，删除最小数量的无效括号，使得输入的字符串有效。
返回所有可能的结果。答案可以按 任意顺序 返回。
示例 1：
输入：s = "()())()"
输出：["(())()","()()()"]
示例 2：
输入：s = "(a)())()"
输出：["(a())()","(a)()()"]
示例 3：
输入：s = ")("
输出：[""]
提示：
1 <= s.length <= 25s由小写英文字母以及括号'('和')'组成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.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= lists[i][j] <= 10^4lists[i]按 升序 排列lists[i].length的总和不超过10^4
以下程序实现了这一功能，请你填补空白处的内容：
```c++ #include using namespace std; 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 *mergeKLists(vector &lists) { auto cmp = [](struct ListNode *n1, struct ListNode *n2) { return n1->val > n2->val; } priority_queue, decltype(cmp)> queue(cmp); for (int i = 0; i < lists.size(); i++) { if (lists[i] != nullptr) { queue.push(lists[i]); } } struct ListNode dummy, *p = &dummy; ; while (!queue.empty()) { _________________; } return dummy.next; } }; ```
出处：
https://edu.csdn.net/practice/25023637
代码：
#include <bits/stdc++.h> using namespace std; 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 *mergeKLists(vector<ListNode *> &lists) { auto cmp = [](struct ListNode *n1, struct ListNode *n2) { return n1->val > n2->val; } priority_queue<struct ListNode *, vector<struct ListNode *>, decltype(cmp)> queue(cmp); for (int i = 0; i < lists.size(); i++) { if (lists[i] != nullptr) { queue.push(lists[i]); } } struct ListNode dummy, *p = &dummy; ; while (!queue.empty()) { ListNode *node = queue.top(); queue.pop(); p->next = node; p = node; if (node->next != nullptr) { queue.push(node->next); } } return dummy.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++ class Solution { public: vector> fourSum(vector &nums, int target) { long long l_target = target; sort(nums.begin(), nums.end()); vector> results; int N = nums.size(); for (int i = 0; i < N - 3; i++) { if (i > 0 && nums[i] == nums[i - 1]) continue; for (int j = i + 1; j < N - 2; j++) { if (j > i + 1 && nums[j] == nums[j - 1]) continue; for (int k = 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({nums[i], nums[j], nums[k], nums[l]})); } } } } return results; } }; ```
出处：
https://edu.csdn.net/practice/25023638
代码：
#include <bits/stdc++.h> using namespace std; class Solution { public: vector<vector<int>> fourSum(vector<int> &nums, int target) { long long l_target = target; sort(nums.begin(), nums.end()); vector<vector<int>> results; int N = nums.size(); for (int i = 0; i < N - 3; i++) { if (i > 0 && nums[i] == nums[i - 1]) continue; for (int j = i + 1; j < N - 2; j++) { if (j > i + 1 && nums[j] == nums[j - 1]) continue; for (int k = 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]})); } } } } return results; } }; string vectorToString(vector<int> 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 s; vector<int> nums = {1,0,-1,0,-2,2}; for (auto n: s.fourSum(nums, 0)) cout << vectorToString(n) << " "; return 0; }
输出：
🌟 每日一练刷题专栏 🌟
✨持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！
☸ 主页：https://hannyang.blog.csdn.net/
