leetcode解题思路分析（一百三十九）1190 - 1196 题

1190. 反转每对括号间的子串
      给出一个字符串 s（仅含有小写英文字母和括号）。请你按照从括号内到外的顺序，逐层反转每对匹配括号中的字符串，并返回最终的结果。注意，您的结果中 不应 包含任何括号。

可以简单的用栈保存当前层级，然后遇到下一个右括号的时候进行当前字符的反转拼接从而递归的完成。但是更巧妙的是，先获取到每个括号的索引，然后访问到左括号则跳转至对应右括号继续读数据，直到再次遇到同括号则继续跳转。

class Solution {
public:string reverseParentheses(string s) {int n = s.length();vector<int> pair(n);stack<int> stk;for (int i = 0; i < n; i++) {if (s[i] == '(') {stk.push(i);} else if (s[i] == ')') {int j = stk.top();stk.pop();pair[i] = j, pair[j] = i;}}string ret;int index = 0, step = 1;while (index < n) {if (s[index] == '(' || s[index] == ')') {index = pair[index];step = -step;} else {ret.push_back(s[index]);}index += step;}return ret;}
};

1191. K 次串联后最大子数组之和
      给定一个整数数组 arr 和一个整数 k ，通过重复 k 次来修改数组。例如，如果 arr = [1, 2] ， k = 3 ，那么修改后的数组将是 [1, 2, 1, 2, 1, 2] 。返回修改后的数组中的最大的子数组之和。注意，子数组长度可以是 0，在这种情况下它的总和也是 0。由于 结果可能会很大，需要返回的 109 + 7 的 模 。

分析最大子数组和可能的情况
最大子数组存在于单个数组内，此时最大和即为单个数组内的最大子数组和
最大子数组横跨两个数组，此时最大和即为单个数组内的最大前缀和加上最大后缀和
最大子数组横跨多个数组，此时要求单个数组总和大于0，此时最大和即为k-2个数组和加上最大前缀和加上最大后缀和

class Solution {
public:int kConcatenationMaxSum(vector<int>& arr, int k) {int base = 1000000007;// arr的累计和long arrSum = 0;// k=1情况下的最大和long maxSum = 0;// 临时累计最大值long curr = 0;int n = arr.size();for (int i = 0; i < n; ++i){arrSum += arr[i];curr = max(curr + arr[i], (long)arr[i]);maxSum = max(maxSum, curr);}if (k == 1){return maxSum % base;}// cout << maxSum << " " << curr << endl;// k=2情况下的最大和，至少不比maxSum小long maxSum2 = maxSum;for (int i = 0; i < n; ++i){curr = max((curr + arr[i]), (long)arr[i]);maxSum2 = max(maxSum2, curr);  }if (k==2){return maxSum2 % base;}// cout << maxSum << " " << maxSum2 << endl;return arrSum > 0 ? (maxSum2 + ((k-2)*arrSum)%base)%base : maxSum2;}
};

1192. 查找集群内的关键连接
      力扣数据中心有 n 台服务器，分别按从 0 到 n-1 的方式进行了编号。它们之间以 服务器到服务器 的形式相互连接组成了一个内部集群，连接是无向的。用 connections 表示集群网络，connections[i] = [a, b] 表示服务器 a 和 b 之间形成连接。任何服务器都可以直接或者间接地通过网络到达任何其他服务器。关键连接 是在该集群中的重要连接，假如我们将它移除，便会导致某些服务器无法访问其他服务器。请你以任意顺序返回该集群内的所有 关键连接 。

** Tarjan 算法模板题**

class Solution {
public:vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {vector<vector<int>> graph(n);for (auto& conn : connections) {graph[conn[0]].push_back(conn[1]);graph[conn[1]].push_back(conn[0]);}vector<int> rank(n, -2);vector<vector<int>> res;dfs(graph, rank, 0, -1, 0, res, n);return res;}int dfs(vector<vector<int>>& graph, vector<int>& rank, int curr, int prev, int depth, vector<vector<int>>& res, int n) {rank[curr] = depth;int min_back_depth = depth;for (int next : graph[curr]) {if (next == prev) continue;if (rank[next] == -2) {int back_depth = dfs(graph, rank, next, curr, depth + 1, res, n);min_back_depth = min(min_back_depth, back_depth);if (back_depth > depth) {res.push_back({curr, next});}} else {min_back_depth = min(min_back_depth, rank[next]);}}rank[curr] = n;return min_back_depth;}
};

1193. 每月交易 I
      编写一个 sql 查询来查找每个月和每个国家/地区的事务数及其总金额、已批准的事务数及其总金额。以 任意顺序 返回结果表。

DATE_FORMAT(date, format) ：用于以不同的格式显示日期/时间数据。date 参数是合法的日期，format 规定日期/时间的输出格式

# Write your MySQL query statement below
SELECT DATE_FORMAT(trans_date, '%Y-%m') AS month,country,COUNT(*) AS trans_count,COUNT(IF(state = 'approved', 1, NULL)) AS approved_count,SUM(amount) AS trans_total_amount,SUM(IF(state = 'approved', amount, 0)) AS approved_total_amount
FROM Transactions
GROUP BY month, country

1195. 交替打印字符串
      请你实现一个有四个线程的多线程版 FizzBuzz， 同一个 FizzBuzz 实例会被如下四个线程使用：
      线程A将调用 fizz() 来判断是否能被 3 整除，如果可以，则输出 fizz。
      线程B将调用 buzz() 来判断是否能被 5 整除，如果可以，则输出 buzz。
      线程C将调用 fizzbuzz() 来判断是否同时能被 3 和 5 整除，如果可以，则输出 fizzbuzz。
      线程D将调用 number() 来实现输出既不能被 3 整除也不能被 5 整除的数字。

使用原子atomic，然后对每个函数定好条件循环执行。

class FizzBuzz {int n_;atomic<int> num_=1;
public:FizzBuzz(int n) {n_ = n;}void fizz(function<void()> pa) {while(1){while(!(num_>n_||num_%3==0&&num_%5!=0))this_thread::yield();if(num_>n_)break;pa();num_++;if(num_>n_)break;}}void buzz(function<void()> pb) {while(1){while(!(num_>n_||num_%3!=0&&num_%5==0))this_thread::yield();if(num_>n_)break;pb();num_++;if(num_>n_)break;}}void fizzbuzz(function<void()> pc) {while(1){while(!(num_>n_||num_%3==0&&num_%5==0))this_thread::yield();if(num_>n_)break;pc();num_++;if(num_>n_)break;}}void number(function<void(int)> pd) {while(1){while(!(num_>n_||num_%3!=0&&num_%5!=0))this_thread::yield();if(num_>n_)break;pd(num_);num_++;if(num_>n_)break;}}
};

1200. 最小绝对差
      给你个整数数组 arr，其中每个元素都 不相同。
      请你找到所有具有最小绝对差的元素对，并且按升序的顺序返回。
      每对元素对 [a,b] 如下：
      a , b 均为数组 arr 中的元素
      a < b
      b - a 等于 arr 中任意两个元素的最小绝对差

升序排列，然后遍历判断即可

class Solution {
public:vector<vector<int>> minimumAbsDifference(vector<int>& arr) {int n = arr.size();sort(arr.begin(), arr.end());int best = INT_MAX;vector<vector<int>> ans;for (int i = 0; i < n - 1; ++i) {if (int delta = arr[i + 1] - arr[i]; delta < best) {best = delta;ans = {{arr[i], arr[i + 1]}};}else if (delta == best) {ans.emplace_back(initializer_list<int>{arr[i], arr[i + 1]});}}return ans;}
};