leetCode进阶算法题+解析（八十四）
黑板异或游戏
题目：黑板上写着一个非负整数数组 nums[i] 。Alice 和 Bob 轮流从黑板上擦掉一个数字，Alice 先手。如果擦除一个数字后，剩余的所有数字按位异或运算得出的结果等于 0 的话，当前玩家游戏失败。 (另外，如果只剩一个数字，按位异或运算得到它本身；如果无数字剩余，按位异或运算结果为 0。）并且，轮到某个玩家时，如果当前黑板上所有数字按位异或运算结果等于 0，这个玩家获胜。假设两个玩家每步都使用最优解，当且仅当 Alice 获胜时返回 true。
示例：
输入: nums = [1, 1, 2]
输出: false
解释:
Alice 有两个选择: 擦掉数字 1 或 2。
如果擦掉 1, 数组变成 [1, 2]。剩余数字按位异或得到 1 XOR 2 = 3。那么 Bob 可以擦掉任意数字，因为 Alice 会成为擦掉最后一个数字的人，她总是会输。
如果 Alice 擦掉 2，那么数组变成[1, 1]。剩余数字按位异或得到 1 XOR 1 = 0。Alice 仍然会输掉游戏。
提示：
1 <= N <= 1000
0 <= nums[i] <= 2^16
思路：这个题是2021/5/22的每日一题。5月果然是异或月。不过这个题是困难的。因为N是大于0的。所以我们可以这么说，一个数组异或和不为0且元素数大于1的话，肯定是可以找出一个数删除，并且结果不为0.这个题目的标签是数学，我觉得大概率是个找规律的题。我去慢慢寻思寻思。
没寻思明白，看了题解，直接上代码：
class Solution {
public boolean xorGame(int[] nums) {
if (nums.length % 2 == 0) {
return true;
}
int xor = 0;
for (int num : nums) {
xor ^= num;
}
return xor == 0;
}
}
主要是没找好规律。这个题果然是数学题。首先因为两个人是一个一个的拿。所以可以得出如此结论：如果A拿的时候是偶数，则每次A拿都是偶数。而如果是偶数的话，异或非0，每个元素都大于0.所以擦掉一个元素不可能会出现0.也就是说A处于不败的。
于是数组如果是偶数个A肯定获胜，直接true。
而如果是奇数的话，除非一上来A就获胜了，也就是全部元素异或为0了。否则就是B陷入不败之地。所以结果如上。
感觉这个题目看了题解很容易明白，但是自己想反正我是怎么也没想出来。这个题过了，下一题。
数组中元素的最大异或值
题目：给你一个由非负整数组成的数组 nums 。另有一个查询数组 queries ，其中 queries[i] = [xi, mi] 。第 i 个查询的答案是 xi 和任何 nums 数组中不超过 mi 的元素按位异或（XOR）得到的最大值。换句话说，答案是 max(nums[j] XOR xi) ，其中所有 j 均满足 nums[j] <= mi 。如果 nums 中的所有元素都大于 mi，最终答案就是 -1 。返回一个整数数组 answer 作为查询的答案，其中 answer.length == queries.length 且 answer[i] 是第 i 个查询的答案。
示例 1：
输入：nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]]
输出：[3,3,7]
解释：
- 0 和 1 是仅有的两个不超过 1 的整数。0 XOR 3 = 3 而 1 XOR 3 = 2 。二者中的更大值是 3 。
- 1 XOR 2 = 3.
- 5 XOR 2 = 7.
示例 2：
输入：nums = [5,2,4,6,6,3], queries = [[12,4],[8,1],[6,3]]
输出：[15,-1,5]
提示：
1 <= nums.length, queries.length <= 10^5
queries[i].length == 2
0 <= nums[j], xi, mi <= 10^9
*思路：2021/5/23的每日一题，说异或月就异或月。简单来说数据范围挺大，所以暴力法肯定会超时，我就不寻思了。其次因为数值的范围是10的九次方。所以说数组代替下标排序这个想法也不现实。我暂时的想法是用前缀树。因为其实这个异或最大其实是有规律的。比如当前100110.异或最大的实现是尽量让每一位都为0，如果无法实现也应该是尽可能让前面的位数为1.我们去查看两个数的位数。然后从第一位是1开始往下尽量找后面也是1的。如果没选择0也行。差不多就是这个思路，我去实现试试。
附上第一版代码:
class Solution {
public int[] maximizeXor(int[] nums, int[][] queries) {
int[] ans = new int[queries.length];
Tree tree = new Tree();
for(int i:nums) tree.insert(i);
for(int i = 0;i<queries.length;i++) ans[i] = tree.getMax(queries[i][0], queries[i][1]);
return ans;
}
}
class Tree {
int len = 30;
Tree[] children = new Tree[2];//一个1，一个0
int min = Integer.MAX_VALUE;
public void insert(int val) {
Tree cur = this;
cur.min = Math.min(cur.min, val);
for(int i = len-1;i>=0;i--) {
int temp = (val>>i)&1;
if(cur.children[temp] == null) {
cur.children[temp] = new Tree();
}
cur = cur.children[temp];
cur.min = Math.min(cur.min, val);
}
}
public int getMax(int val,int limit) {
Tree cur = this;
if(cur.min>limit) return -1;//说明没有比limit更小的，所以直接-1
int ans = 0;
for(int i = len-1;i>=0;i--) {
int temp = (val>>i)&1;
//如果val当前位是0则要找当前位是1的。而且还要比limit小，
//当然了如果val当前为是1则找当前为是0的。
if(cur.children[temp^1] != null && cur.children[temp^1].min<=limit) {
ans |= 1<<i;
temp ^= 1;
}
cur = cur.children[temp];
}
return ans;
}
}
上面的代码是呕心沥血写出来的。各种细节，各种位运算用到什么查什么。。。本来如果没有limit是很简单的一个题目。难点主要是在limit上。所以这里引用了一个每个树的根树上是有当前子树的最小值的。如果最小值还大于limit，说明这个分支根本不能走。然后如果当前元素没有对应元素，则只能当前元素勉强为0继续往下判断。
然后这个题对我来说难点最大的就是位运算了，像是我说的一点点去百度的。还有中间ans的或运算。我本来想直接拼接二进制的。后来发现太麻烦了就继续找位运算的实现。
然后上面代码的性能不咋地，我去看看性能第一的代码吧：
class Solution {
static final int INF = 1 << 30;
public static int[] maximizeXor(int[] nums, int[][] queries) {
// sort & de-dup
Arrays.sort(nums);
int len = 0;
for (int i = 0, prev = -1; i < nums.length; i++) {
if (nums[i] != prev) {
prev = nums[len++] = nums[i];
}
}
// for loop
final int querySize = queries.length;
int[] ans = new int[querySize];
for (int i = 0; i < querySize; i++) {
int threshold = queries[i][1];
int r = binarySearch(nums, 0, len, threshold) - 1;
if (r < 0) {
ans[i] = -1;
continue;
}
int mod = INF;
while (mod > 1 && 0 == (mod & threshold)) mod >>>= 1;
ans[i] = query(nums, 0, r, mod, queries[i][0]);
}
return ans;
}
private static int query(int[] nums, int l, int r, int threshold, int x) {
for (; threshold != 0 && l < r; threshold >>>= 1) {
if ((threshold & nums[l]) == (threshold & nums[r])) {
continue;
}
int mid = binarySearch(nums, l, r + 1, nums[l] | (threshold - 1));
if (0 == (x & threshold)) {
l = mid;
} else {
r = mid - 1;
}
}
return nums[l] ^ x;
}
private static int binarySearch(int[] arr, int l, int r, int target) {
return Math.abs(Arrays.binarySearch(arr, l, r, target) + 1);
}
}
心态崩了，这个代码没太看懂。简单理一下：因为存在重复元素，所以这个题手动把不同的元素排序，队列变成了长度为len的升序了。
然后就用了一种二分法搜索了什么，到这就已经看不懂了，所以这个就这样吧，起码用我的笨方法也能对付实现，下一题了。
奇怪的打印机
题目：有台奇怪的打印机有以下两个特殊要求：打印机每次只能打印由 同一个字符 组成的序列。每次可以在任意起始和结束位置打印新字符，并且会覆盖掉原来已有的字符。给你一个字符串 s ，你的任务是计算这个打印机打印它需要的最少打印次数。
示例 1：
输入：s = "aaabbb"
输出：2
解释：首先打印 "aaa" 然后打印 "bbb"。
示例 2：
输入：s = "aba"
输出：2
解释：首先打印 "aaa" 然后在第二个位置打印 "b" 覆盖掉原来的字符 'a'。
提示：
1 <= s.length <= 100
s 由小写英文字母组成
思路：2021/5/24的每日一题，说真的，这个打印机真是太奇怪了，换一个就解决问题了。然后继续说这道题，我的想法是第一步打底：也就是看从头到尾是哪个元素出现的次数多，则头到尾是这个字母。然后在这个字母的基础上来覆盖。而每一层覆盖都可以看成是一次遍历。这个题目的标签是深搜和动态规划。感觉可以变成递归子问题。目前为止大概思路就是这样，我去代码实现试试。
第一版代码思路有点问题。本来我是每一次找到出现次数最多的元素统一打印。然后再去拆分中间的具体次数的。结果发现遇到回文的那种abcdadcba这样的就会出错。但是就因为这样又恰好符合了dp的思路：因为abcda其实和abcd本质上应该是一样的次数。最后一个a完全可以在第一个a的时候顺便打印。也就是递推公式的一部分：s[i]==s[j],那么打印次数：i到j应该和i到j-1一样。
问题是当s[i]!=s[j]的时候，哪怕i和j-1中间出现了s[j]，我们也不能保证j-1填充的时候可以填到最后。所以这个时候要分情况判断了。到底是之前的+1还是可以直接上一次填充s[j]的时候待着这个元素。。总而言之思路是这样的，我去实现试试。
第一版代码：
class Solution {
public int strangePrinter(String s) {
char[] c = s.toCharArray();
int len = 0;
for(int i = 1;i<c.length;i++) {
if(c[i] != c[i-1]) c[++len] = c[i];
}
//所有的排序。其实aaa和a是没区别的。都是一次。
char[] cur = Arrays.copyOfRange(c, 0, len+1);
int[][] dp = new int[len+1][len+1];
for(int i = len;i>=0;i--) {
dp[i][i] = 1;
for(int j = i+1;j<=len;j++) {
if(cur[i] == cur[j]) {
dp[i][j] = dp[i][j-1];
}else {//这个时候要看是+1还是不加了。
int min = Integer.MAX_VALUE;
for(int k = i;k<j;k++) {
//重点是这步：因为之前的dp[i][i]填充了1，所以最大的值也不过是dp[i][j-1]+1
//问题是最小值的可能：有没有一个节点，让当前元素能混进去
//如果有其实结果应该就是dp[i][j-1]
min = Math.min(min, dp[i][k]+dp[k+1][j]);
}
dp[i][j] = min;
}
}
}
return dp[0][len];
}
}
这个重点就还是这个+1不加1的问题。而且单一某个元素一定要印刷一次，所以dp[i][i] = 1.
然后顺着二维数组往上推：最终推到第一行。差不多如下图所示：
dp往右上角逼近
大概思路就这样，果然有dp标签dp是跑不了的。我一开始就不应该沉迷深搜无法自拔。。我这个代码性能超过百分之八十九，我再去看看性能第一的代码。
class Solution {
public int strangePrinter(String s) {
char[] chs = s.toCharArray();
int len = chs.length;
if (len <= 1) {
return len;
}
int[] cur = new int[26];
int[] next = new int[len];
Arrays.fill(next, -1);
Arrays.fill(cur, -1);
cur[chs[0] - 'a'] = 0;
int size = 1;
for (int i = 1; i < len; i++) {
if (chs[i - 1] == chs[i]) continue;
int idx = chs[i] - 'a';
if (cur[idx] != -1) {
next[cur[idx]] = size;
}
cur[idx] = size++;
}
// 将 chs[] 中的信息压缩至 next[] 中
int[][] dp = new int[size][size];
for (int l = size - 1; l >= 0; l--) {
Arrays.fill(dp[l], Integer.MAX_VALUE);
for (int m = l; m < size; m++) {
if (m == l) {
dp[l][m] = 1;
} else {
dp[l][m] = Math.min(dp[l][m], dp[l][m - 1] + 1);
}
for (int r = next[m]; r != -1; r = next[r]) {
dp[l][r] = Math.min(dp[l][r], dp[l][m] + dp[m + 1][r - 1]);
}
}
}
return dp[0][size - 1];
}
}
但凡每次我觉得我行了，力扣总能轻蔑的告诉我，我不行。
这个代码是我想象中的样子，但是我自己没写出来。
之前我就说了，断点一定是从和s[j]相等的元素中开始的。但是我自己觉得真的实现起来太麻烦了，就暴力遍历了一遍，可是人家把这个思路用代码实现了。用一种套接下标的形式，可以追根溯源。。总而言之大写的服。
然后别的就没啥了，整体递推公式的一样的思路。下一题。
所有可能的满二叉树
题目：满二叉树是一类二叉树，其中每个结点恰好有 0 或 2 个子结点。返回包含 N 个结点的所有可能满二叉树的列表。 答案的每个元素都是一个可能树的根结点。答案中每个树的每个结点都必须有 node.val=0。你可以按任何顺序返回树的最终列表。
题目截图
思路：首先这个题的数据范围n小于等于20.而且其实这里有个概念：n是偶数的时候，是不可能有结果的。因为必然有一个根节点是单独的。每个子节点都要0/2个子节点，所以偶数个节点是组不成完美二叉树的。所以只要判断奇数情况。N的范围其实1,3,5。。。19.又缩小了一半。。我有个大胆的想法，不知道每种情况枚举下来行不行。。。嘿嘿嘿。算了，正经一点;题目标签是递归，所以我觉得首先根节点一定要有的。其次如果还有多余的元素则左右节点必有。这个时候把左右单独递归。节点数的分法肯定是奇数分。比如说n=15.那么初始根节点用一个。左右分别1-13。3-11，5-9，7-7，9-5，11-3，13-1.这样。然後其实本质上我觉得肯定是左右可以对称的。然後再依次往下去遍历。大概思路是这样，我去代码实现下。
第一版代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<TreeNode> allPossibleFBT(int n) {
List<TreeNode> list = new ArrayList<TreeNode>();
if(n%2 != 0) {//如果n是偶数不用算了
if(n == 1) {
list.add(new TreeNode(0));
}else {
for(int i = 1 ; i<n ; i+=2) {
//i是左子树可能的节点和，right是右子树的。因为根节点占了一个，所以n-1-i
int right = n-1-i;
for(TreeNode l:allPossibleFBT(i)) {
for(TreeNode r:allPossibleFBT(right)) {
TreeNode temp = new TreeNode(0);
temp.left = l;
temp.right = r;
list.add(temp);
}
}
}
}
}
return list;
}
}
这个题的重点就是左右子树的每一种可能都要去计算。虽然这个代码ac了，但是我觉得可优化的点应该是记忆化：比如说子树元素是3,5,7的这些其实只要计算一次就行了，但是如上我的写法是计算了好几次。我去试试优化下。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
Map<Integer, List<TreeNode>> d = new HashMap<Integer, List<TreeNode>>();
public List<TreeNode> allPossibleFBT(int n) {
if(!d.containsKey(n)) {
List<TreeNode> list = new ArrayList<TreeNode>();
if(n%2 != 0) {//如果n是偶数不用算了
if(n == 1) {
list.add(new TreeNode(0));
}else {
for(int i = 1 ; i<n ; i+=2) {
//i是左子树可能的节点和，right是右子树的。因为根节点占了一个，所以n-1-i
int right = n-1-i;
for(TreeNode l:allPossibleFBT(i)) {
for(TreeNode r:allPossibleFBT(right)) {
TreeNode temp = new TreeNode(0);
temp.left = l;
temp.right = r;
list.add(temp);
}
}
}
}
}
d.put(n, list);
}
return d.get(n);
}
}
这个代码1ms，是这个题的最快速度了。和第一版本相比就做了一个改变:将固定元素数的数字对应的所有树保存起来。然后重复运算的时候可以直接取值。剩下的没啥区别了。这个题因为已经性能最好了，所以我就不看性能第一的代码了，下一题。
使所有区间的异或结果为0
题目：给你一个整数数组 nums 和一个整数 k 。区间 [left, right]（left <= right）的 异或结果 是对下标位于 left 和 right（包括 left 和 right ）之间所有元素进行 XOR 运算的结果：nums[left] XOR nums[left+1] XOR ... XOR nums[right] 。返回数组中 要更改的最小元素数 ，以使所有长度为 k 的区间异或结果等于零。
示例 1：
输入：nums = [1,2,0,3,0], k = 1
输出：3
解释：将数组 [1,2,0,3,0] 修改为 [0,0,0,0,0]
示例 2：
输入：nums = [3,4,5,2,1,7,3,4,7], k = 3
输出：3
解释：将数组 [3,4,5,2,1,7,3,4,7] 修改为 [3,4,7,3,4,7,3,4,7]
示例 3：
输入：nums = [1,2,4,1,2,5,1,2,6], k = 3
输出：3
解释：将数组[1,2,4,1,2,5,1,2,6] 修改为 [1,2,3,1,2,3,1,2,3]
提示：
1 <= k <= nums.length <= 2000
0 <= nums[i] < 2 ^10
思路：2021/5/25的每日一题。又叒叕是困难的，力扣这个四连困难有点东西啊，感觉是在劝退像我这样的fw，哎，回归到这个题目吧。首先异或结果等于0，其实任何组合最多改变一个数就可以归0 ，当然了最少的也是最好的是不需要改变直接归0.而且通过给的两个例子我们可以看出来如果想做到满足要求的结果，必然是以k为单位的循环。而说到了以k为单位的循环，我觉得这个题的思路差不多就来了，然后2的10次方，刚刚算了一下发现才1024，所以数据量也不是很大。初步的想法是每一组K个元素。然后分成总数/k向上取整组。然后按位对比。一样的多的不该。不一样的多的改。最终要实现以k长为子串的循环。思路大概是这样，我去代码实现下。
自己没做出来，看了题解，贴一下正确代码：
public int minChanges(int[] nums, int k) {
int n = nums.length;
int max = 1024;
int[][] f = new int[k][max];
int[] g = new int[k];
for (int i = 0; i < k; i++) {
Arrays.fill(f[i], 0x3f3f3f3f);
g[i] = 0x3f3f3f3f;
}
for (int i = 0, cnt = 0; i < k; i++, cnt = 0) {
// 使用 map 和 cnt 分别统计当前列的「每个数的出现次数」和「有多少个数」
Map<Integer, Integer> map = new HashMap<>();
for (int j = i; j < n; j += k) {
map.put(nums[j], map.getOrDefault(nums[j], 0) + 1);
cnt++;
}
if (i == 0) { // 第 0 列：只需要考虑如何将该列变为 xor 即可
for (int xor = 0; xor < max; xor++) {
f[0][xor] = Math.min(f[0][xor], cnt - map.getOrDefault(xor, 0));
g[0] = Math.min(g[0], f[0][xor]);
}
} else { // 其他列：考虑与前面列的关系
for (int xor = 0; xor < max; xor++) {
f[i][xor] = g[i - 1] + cnt; // 整列替换
for (int cur : map.keySet()) { // 部分替换
System.out.println(f[i][xor]);
System.out.println(xor ^ cur);
System.out.println(f[i - 1][xor ^ cur] + cnt - map.get(cur));
f[i][xor] = Math.min(f[i][xor], f[i - 1][xor ^ cur] + cnt - map.get(cur));
}
g[i] = Math.min(g[i], f[i][xor]);
}
}
}
return f[k - 1][0];
}
这个主要是实现上面说过了，但是怎么落实到代码中很难。但是有一个重点：我们不知道一组k长度的元素的循环体是什么样子的。反正这个题可以演变成：
因此我们将这个一维的输入看成二维，从而将问题转化为：全部元素K个分一列。使得最终每列相等，同时「首行」的异或值为 0的最小修改次数。因为最后一列可能不是完整的，所以没说每列都异或为0.上面的代码看似是一个一维数组，但是本质上是二维数组的压缩，因为下一行只和上一行状态有关，所以这里用了两个一维数组来交替存储状态。这是个很常见的技巧。
继续说这个题的递推公式：其实第一列需要考虑的情况比较简单， 只要所有的元素一样就行了。所以计数也简单，只要存储这列非当前元素的个数就行了（因为如果想要这列变成当前元素，那么目前不是的都要改，所以计住要改多少）。
然后第二列开始既然是奇数第二列的元素和出现次数。但是这里计算就是1,2列的元素的异或结果。想要这一行异或结果为0那么要前面的列的异或结果等于最后一列的值，这里我是反复看debug的数据变化的。对于某一列来讲，最坏的结果就是整列替换，所以保底就是列的个数。
比如1,2,3,1,3,4,1,2,5,1，2，k=3.这样的结果第一个遍历应该如下（下标从0开始）：
4,0，4,4...（因为分成四组，所以如果想要第一列都为0则要变四次。想要第一列都为1不用变了，想要第一列都为2变4次，依次类推）
第二次遍历的结果如下：
4,4,3,1,4,4,,,,（这里这里的3,和1出现的原因：因为第一列是1，当前列三个2一个3.1异或2的结果是3，所以如果想要第三列是3的话，需要改动一个元素，也就是第二列那一个三。同理如果想要第三列是2的话，需要改动三个元素，也就是第二列的三个2.4就不用解释了，整列更改）
第三个遍历的结果：
3,4,4,4...（这个和第二遍是类似的，想要当前排异或结果为0则需要改变3个元素。因为本质上最后一列是3,4,5这三个元素。而前两列的异或结果是2有一次。3有三次。而想要当前总异或结果为0.3本身就可以用了，所以只需要改变4,5这两个就行了。但是因为第二排变成都是3就要改变一次。所以到当前变成都是0就是2+1也就是三次。）
因为k=3.所以到此就计算结束。而答案就是最后一排的下标为0的结果。
最后一排下标为0说明的就是到了最后一列，保持整行异或为0的最小次数。
如是，这题完事了。
看着题解跑了两个多小时才看明白，自己做是废了，这个题就这样吧，下一题。
反转每对括号间的子串
题目：给出一个字符串 s（仅含有小写英文字母和括号）。请你按照从括号内到外的顺序，逐层反转每对匹配括号中的字符串，并返回最终的结果。注意，您的结果中 不应 包含任何括号。
示例 1：
输入：s = "(abcd)"
输出："dcba"
示例 2：
输入：s = "(u(love)i)"
输出："iloveu"
示例 3：
输入：s = "(ed(et(oc))el)"
输出："leetcode"
示例 4：
输入：s = "a(bcdefghijkl(mno)p)q"
输出："apmnolkjihgfedcbq"
提示：
0 <= s.length <= 2000
s 中只有小写英文字母和括号
我们确保所有括号都是成对出现的
思路：连续四天困难后终于见到春天了。这个题比较简单。递归肯定可以实现。一层一层解析呗。我去代码实现了。
第一版代码：
class Solution {
public String reverseParentheses(String s) {
StringBuilder sb = new StringBuilder();
char[] arr = s.toCharArray();
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < arr.length; i++) {
if (arr[i] == '(')
stack.push(i);
if (arr[i] == ')')
reverse(arr, stack.pop() + 1, i - 1);
}
for (int i = 0; i < arr.length; i++)
if (arr[i] != ')' && arr[i] != '(')
sb.append(arr[i]);
return sb.toString();
}
public void reverse(char[] arr, int left, int right) {
while (right > left) {
char tmp = arr[left];
arr[left] = arr[right];
arr[right] = tmp;
right--;
left++;
}
}
}
这个题比较简单，本来想递归，后来发现其实用栈就行了。毕竟递归也就是隐式栈而已。重点就是找出一对一对的括号。所以栈push和pop可以保证遇到的每一个）pop出来的都是对应的左括号的位置。然后剩下的就没啥了，一层一层的翻转就可以了。当然了我这里有个问题就是反复翻转。比如（ab(cd)ef）。我这个代码会先翻转内层括号，变成（ab（dc）ef）然后再翻转外层变成（fe(cd)ba）.然后再统一去括号。理论上这个题绝对可以O(n)时间复杂度的，有点懒得想了，我去贴一下性能第一的代码：
class Solution {
int index;
public String reverseParentheses(String s) {
index = 0;
String res = reverse(s.toCharArray());
return new StringBuilder(res).reverse().toString();
}
String reverse(char[] ch) {
StringBuilder res = new StringBuilder();
while(index<ch.length) {
if(ch[index] == '(') {
index++;
res.append(reverse(ch));
} else if(ch[index]==')'){
index++;
break;
} else {
res.append(ch[index]);
index++;
}
}
return res.reverse().toString();
}
}
怎么说呢，这个代码我想到了。但是实现的时候发现还挺麻烦，就换了思路，不难想，这个题没啥好说的。直接过了。
本篇笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注。也祝大家工作顺顺利利，生活健健康康！最近很喜欢的一句话：路漫漫兮其修远，吾将上下而求索。对于算法来讲，有时候觉得真的是门都没入，愿我们在求索的路上一往无前！
