C/C++每日一练(20230408) 删除无效括号、合并K个升序链表、四数之和

#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;
} 

#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;
    }
};

#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;
}