黑板異或游戲
題目：黑板上寫著一個非負(fù)整數(shù)數(shù)組 nums[i] 。Alice 和 Bob 輪流從黑板上擦掉一個數(shù)字，Alice 先手。如果擦除一個數(shù)字后，剩余的所有數(shù)字按位異或運算得出的結(jié)果等于 0 的話，當(dāng)前玩家游戲失敗。 (另外，如果只剩一個數(shù)字，按位異或運算得到它本身；如果無數(shù)字剩余，按位異或運算結(jié)果為 0。）并且，輪到某個玩家時，如果當(dāng)前黑板上所有數(shù)字按位異或運算結(jié)果等于 0，這個玩家獲勝。假設(shè)兩個玩家每步都使用最優(yōu)解，當(dāng)且僅當(dāng) Alice 獲勝時返回 true。
示例：
輸入: nums = [1, 1, 2]
輸出: false
解釋:
Alice 有兩個選擇: 擦掉數(shù)字 1 或 2。
如果擦掉 1, 數(shù)組變成 [1, 2]。剩余數(shù)字按位異或得到 1 XOR 2 = 3。那么 Bob 可以擦掉任意數(shù)字，因為 Alice 會成為擦掉最后一個數(shù)字的人，她總是會輸。
如果 Alice 擦掉 2，那么數(shù)組變成[1, 1]。剩余數(shù)字按位異或得到 1 XOR 1 = 0。Alice 仍然會輸?shù)粲螒颉?br> 提示：
1 <= N <= 1000
0 <= nums[i] <= 2^16
思路：這個題是2021/5/22的每日一題。5月果然是異或月。不過這個題是困難的。因為N是大于0的。所以我們可以這么說，一個數(shù)組異或和不為0且元素數(shù)大于1的話，肯定是可以找出一個數(shù)刪除，并且結(jié)果不為0.這個題目的標(biāo)簽是數(shù)學(xué)，我覺得大概率是個找規(guī)律的題。我去慢慢尋思尋思。
沒尋思明白，看了題解，直接上代碼：
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;
}
}
主要是沒找好規(guī)律。這個題果然是數(shù)學(xué)題。首先因為兩個人是一個一個的拿。所以可以得出如此結(jié)論：如果A拿的時候是偶數(shù)，則每次A拿都是偶數(shù)。而如果是偶數(shù)的話，異或非0，每個元素都大于0.所以擦掉一個元素不可能會出現(xiàn)0.也就是說A處于不敗的。
于是數(shù)組如果是偶數(shù)個A肯定獲勝，直接true。
而如果是奇數(shù)的話，除非一上來A就獲勝了，也就是全部元素異或為0了。否則就是B陷入不敗之地。所以結(jié)果如上。
感覺這個題目看了題解很容易明白，但是自己想反正我是怎么也沒想出來。這個題過了，下一題。
數(shù)組中元素的最大異或值
題目：給你一個由非負(fù)整數(shù)組成的數(shù)組 nums 。另有一個查詢數(shù)組 queries ，其中 queries[i] = [xi, mi] 。第 i 個查詢的答案是 xi 和任何 nums 數(shù)組中不超過 mi 的元素按位異或（XOR）得到的最大值。換句話說，答案是 max(nums[j] XOR xi) ，其中所有 j 均滿足 nums[j] <= mi 。如果 nums 中的所有元素都大于 mi，最終答案就是 -1 。返回一個整數(shù)數(shù)組 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 的整數(shù)。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的每日一題，說異或月就異或月。簡單來說數(shù)據(jù)范圍挺大，所以暴力法肯定會超時，我就不尋思了。其次因為數(shù)值的范圍是10的九次方。所以說數(shù)組代替下標(biāo)排序這個想法也不現(xiàn)實。我暫時的想法是用前綴樹。因為其實這個異或最大其實是有規(guī)律的。比如當(dāng)前100110.異或最大的實現(xiàn)是盡量讓每一位都為0，如果無法實現(xiàn)也應(yīng)該是盡可能讓前面的位數(shù)為1.我們?nèi)ゲ榭磧蓚€數(shù)的位數(shù)。然后從第一位是1開始往下盡量找后面也是1的。如果沒選擇0也行。差不多就是這個思路，我去實現(xiàn)試試。
附上第一版代碼:
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當(dāng)前位是0則要找當(dāng)前位是1的。而且還要比limit小，
//當(dāng)然了如果val當(dāng)前為是1則找當(dāng)前為是0的。
if(cur.children[temp^1] != null && cur.children[temp^1].min<=limit) {
ans |= 1<<i;
temp ^= 1;
}
cur = cur.children[temp];
}
return ans;
}
}
上面的代碼是嘔心瀝血寫出來的。各種細節(jié)，各種位運算用到什么查什么。。。本來如果沒有l(wèi)imit是很簡單的一個題目。難點主要是在limit上。所以這里引用了一個每個樹的根樹上是有當(dāng)前子樹的最小值的。如果最小值還大于limit，說明這個分支根本不能走。然后如果當(dāng)前元素沒有對應(yīng)元素，則只能當(dāng)前元素勉強為0繼續(xù)往下判斷。
然后這個題對我來說難點最大的就是位運算了，像是我說的一點點去百度的。還有中間ans的或運算。我本來想直接拼接二進制的。后來發(fā)現(xiàn)太麻煩了就繼續(xù)找位運算的實現(xiàn)。
然后上面代碼的性能不咋地，我去看看性能第一的代碼吧：
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);
}
}
心態(tài)崩了，這個代碼沒太看懂。簡單理一下：因為存在重復(fù)元素，所以這個題手動把不同的元素排序，隊列變成了長度為len的升序了。
然后就用了一種二分法搜索了什么，到這就已經(jīng)看不懂了，所以這個就這樣吧，起碼用我的笨方法也能對付實現(xiàn)，下一題了。
奇怪的打印機
題目：有臺奇怪的打印機有以下兩個特殊要求：打印機每次只能打印由 同一個字符 組成的序列。每次可以在任意起始和結(jié)束位置打印新字符，并且會覆蓋掉原來已有的字符。給你一個字符串 s ，你的任務(wù)是計算這個打印機打印它需要的最少打印次數(shù)。
示例 1：
輸入：s = "aaabbb"
輸出：2
解釋：首先打印 "aaa" 然后打印 "bbb"。
示例 2：
輸入：s = "aba"
輸出：2
解釋：首先打印 "aaa" 然后在第二個位置打印 "b" 覆蓋掉原來的字符 'a'。
提示：
1 <= s.length <= 100
s 由小寫英文字母組成
思路：2021/5/24的每日一題，說真的，這個打印機真是太奇怪了，換一個就解決問題了。然后繼續(xù)說這道題，我的想法是第一步打底：也就是看從頭到尾是哪個元素出現(xiàn)的次數(shù)多，則頭到尾是這個字母。然后在這個字母的基礎(chǔ)上來覆蓋。而每一層覆蓋都可以看成是一次遍歷。這個題目的標(biāo)簽是深搜和動態(tài)規(guī)劃。感覺可以變成遞歸子問題。目前為止大概思路就是這樣，我去代碼實現(xiàn)試試。
第一版代碼思路有點問題。本來我是每一次找到出現(xiàn)次數(shù)最多的元素統(tǒng)一打印。然后再去拆分中間的具體次數(shù)的。結(jié)果發(fā)現(xiàn)遇到回文的那種abcdadcba這樣的就會出錯。但是就因為這樣又恰好符合了dp的思路：因為abcda其實和abcd本質(zhì)上應(yīng)該是一樣的次數(shù)。最后一個a完全可以在第一個a的時候順便打印。也就是遞推公式的一部分：s[i]==s[j],那么打印次數(shù)：i到j(luò)應(yīng)該和i到j(luò)-1一樣。
問題是當(dāng)s[i]!=s[j]的時候，哪怕i和j-1中間出現(xiàn)了s[j]，我們也不能保證j-1填充的時候可以填到最后。所以這個時候要分情況判斷了。到底是之前的+1還是可以直接上一次填充s[j]的時候待著這個元素。。總而言之思路是這樣的，我去實現(xiàn)試試。
第一版代碼：
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是沒區(qū)別的。都是一次。
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
//問題是最小值的可能：有沒有一個節(jié)點，讓當(dāng)前元素能混進去
//如果有其實結(jié)果應(yīng)該就是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.
然后順著二維數(shù)組往上推：最終推到第一行。差不多如下圖所示：
大概思路就這樣，果然有dp標(biāo)簽dp是跑不了的。我一開始就不應(yīng)該沉迷深搜無法自拔。。我這個代碼性能超過百分之八十九，我再去看看性能第一的代碼。
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]相等的元素中開始的。但是我自己覺得真的實現(xiàn)起來太麻煩了，就暴力遍歷了一遍，可是人家把這個思路用代碼實現(xiàn)了。用一種套接下標(biāo)的形式，可以追根溯源。?？偠灾髮懙姆?。
然后別的就沒啥了，整體遞推公式的一樣的思路。下一題。
所有可能的滿二叉樹
題目：滿二叉樹是一類二叉樹，其中每個結(jié)點恰好有 0 或 2 個子結(jié)點。返回包含 N 個結(jié)點的所有可能滿二叉樹的列表。 答案的每個元素都是一個可能樹的根結(jié)點。答案中每個樹的每個結(jié)點都必須有 node.val=0。你可以按任何順序返回樹的最終列表。
思路：首先這個題的數(shù)據(jù)范圍n小于等于20.而且其實這里有個概念：n是偶數(shù)的時候，是不可能有結(jié)果的。因為必然有一個根節(jié)點是單獨的。每個子節(jié)點都要0/2個子節(jié)點，所以偶數(shù)個節(jié)點是組不成完美二叉樹的。所以只要判斷奇數(shù)情況。N的范圍其實1,3,5。。。19.又縮小了一半。。我有個大膽的想法，不知道每種情況枚舉下來行不行。。。嘿嘿嘿。算了，正經(jīng)一點;題目標(biāo)簽是遞歸，所以我覺得首先根節(jié)點一定要有的。其次如果還有多余的元素則左右節(jié)點必有。這個時候把左右單獨遞歸。節(jié)點數(shù)的分法肯定是奇數(shù)分。比如說n=15.那么初始根節(jié)點用一個。左右分別1-13。3-11，5-9，7-7，9-5，11-3，13-1.這樣。然後其實本質(zhì)上我覺得肯定是左右可以對稱的。然後再依次往下去遍歷。大概思路是這樣，我去代碼實現(xiàn)下。
第一版代碼：
/**
* 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是偶數(shù)不用算了
if(n == 1) {
list.add(new TreeNode(0));
}else {
for(int i = 1 ; i<n ; i+=2) {
//i是左子樹可能的節(jié)點和，right是右子樹的。因為根節(jié)點占了一個，所以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了，但是我覺得可優(yōu)化的點應(yīng)該是記憶化：比如說子樹元素是3,5,7的這些其實只要計算一次就行了，但是如上我的寫法是計算了好幾次。我去試試優(yōu)化下。
/**
* 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是偶數(shù)不用算了
if(n == 1) {
list.add(new TreeNode(0));
}else {
for(int i = 1 ; i<n ; i+=2) {
//i是左子樹可能的節(jié)點和，right是右子樹的。因為根節(jié)點占了一個，所以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，是這個題的最快速度了。和第一版本相比就做了一個改變:將固定元素數(shù)的數(shù)字對應(yīng)的所有樹保存起來。然后重復(fù)運算的時候可以直接取值。剩下的沒啥區(qū)別了。這個題因為已經(jīng)性能最好了，所以我就不看性能第一的代碼了，下一題。
使所有區(qū)間的異或結(jié)果為0
題目：給你一個整數(shù)數(shù)組 nums 和一個整數(shù) k 。區(qū)間 [left, right]（left <= right）的 異或結(jié)果 是對下標(biāo)位于 left 和 right（包括 left 和 right ）之間所有元素進行 XOR 運算的結(jié)果：nums[left] XOR nums[left+1] XOR ... XOR nums[right] 。返回數(shù)組中 要更改的最小元素數(shù) ，以使所有長度為 k 的區(qū)間異或結(jié)果等于零。
示例 1：
輸入：nums = [1,2,0,3,0], k = 1
輸出：3
解釋：將數(shù)組 [1,2,0,3,0] 修改為 [0,0,0,0,0]
示例 2：
輸入：nums = [3,4,5,2,1,7,3,4,7], k = 3
輸出：3
解釋：將數(shù)組 [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
解釋：將數(shù)組[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，哎，回歸到這個題目吧。首先異或結(jié)果等于0，其實任何組合最多改變一個數(shù)就可以歸0 ，當(dāng)然了最少的也是最好的是不需要改變直接歸0.而且通過給的兩個例子我們可以看出來如果想做到滿足要求的結(jié)果，必然是以k為單位的循環(huán)。而說到了以k為單位的循環(huán)，我覺得這個題的思路差不多就來了，然后2的10次方，剛剛算了一下發(fā)現(xiàn)才1024，所以數(shù)據(jù)量也不是很大。初步的想法是每一組K個元素。然后分成總數(shù)/k向上取整組。然后按位對比。一樣的多的不該。不一樣的多的改。最終要實現(xiàn)以k長為子串的循環(huán)。思路大概是這樣，我去代碼實現(xiàn)下。
自己沒做出來，看了題解，貼一下正確代碼：
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 分別統(tǒng)計當(dāng)前列的「每個數(shù)的出現(xiàn)次數(shù)」和「有多少個數(shù)」
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 列：只需要考慮如何將該列變?yōu)?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 { // 其他列：考慮與前面列的關(guān)系
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];
}
這個主要是實現(xiàn)上面說過了，但是怎么落實到代碼中很難。但是有一個重點：我們不知道一組k長度的元素的循環(huán)體是什么樣子的。反正這個題可以演變成：
因此我們將這個一維的輸入看成二維，從而將問題轉(zhuǎn)化為：全部元素K個分一列。使得最終每列相等，同時「首行」的異或值為 0的最小修改次數(shù)。因為最后一列可能不是完整的，所以沒說每列都異或為0.上面的代碼看似是一個一維數(shù)組，但是本質(zhì)上是二維數(shù)組的壓縮，因為下一行只和上一行狀態(tài)有關(guān)，所以這里用了兩個一維數(shù)組來交替存儲狀態(tài)。這是個很常見的技巧。
繼續(xù)說這個題的遞推公式：其實第一列需要考慮的情況比較簡單， 只要所有的元素一樣就行了。所以計數(shù)也簡單，只要存儲這列非當(dāng)前元素的個數(shù)就行了（因為如果想要這列變成當(dāng)前元素，那么目前不是的都要改，所以計住要改多少）。
然后第二列開始既然是奇數(shù)第二列的元素和出現(xiàn)次數(shù)。但是這里計算就是1,2列的元素的異或結(jié)果。想要這一行異或結(jié)果為0那么要前面的列的異或結(jié)果等于最后一列的值，這里我是反復(fù)看debug的數(shù)據(jù)變化的。對于某一列來講，最壞的結(jié)果就是整列替換，所以保底就是列的個數(shù)。
比如1,2,3,1,3,4,1,2,5,1，2，k=3.這樣的結(jié)果第一個遍歷應(yīng)該如下（下標(biāo)從0開始）：
4,0，4,4...（因為分成四組，所以如果想要第一列都為0則要變四次。想要第一列都為1不用變了，想要第一列都為2變4次，依次類推）
第二次遍歷的結(jié)果如下：
4,4,3,1,4,4,,,,（這里這里的3,和1出現(xiàn)的原因：因為第一列是1，當(dāng)前列三個2一個3.1異或2的結(jié)果是3，所以如果想要第三列是3的話，需要改動一個元素，也就是第二列那一個三。同理如果想要第三列是2的話，需要改動三個元素，也就是第二列的三個2.4就不用解釋了，整列更改）
第三個遍歷的結(jié)果：
3,4,4,4...（這個和第二遍是類似的，想要當(dāng)前排異或結(jié)果為0則需要改變3個元素。因為本質(zhì)上最后一列是3,4,5這三個元素。而前兩列的異或結(jié)果是2有一次。3有三次。而想要當(dāng)前總異或結(jié)果為0.3本身就可以用了，所以只需要改變4,5這兩個就行了。但是因為第二排變成都是3就要改變一次。所以到當(dāng)前變成都是0就是2+1也就是三次。）
因為k=3.所以到此就計算結(jié)束。而答案就是最后一排的下標(biāo)為0的結(jié)果。
最后一排下標(biāo)為0說明的就是到了最后一列，保持整行異或為0的最小次數(shù)。
如是，這題完事了。
看著題解跑了兩個多小時才看明白，自己做是廢了，這個題就這樣吧，下一題。
反轉(zhuǎn)每對括號間的子串
題目：給出一個字符串 s（僅含有小寫英文字母和括號）。請你按照從括號內(nèi)到外的順序，逐層反轉(zhuǎn)每對匹配括號中的字符串，并返回最終的結(jié)果。注意，您的結(jié)果中 不應(yīng) 包含任何括號。
示例 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 中只有小寫英文字母和括號
我們確保所有括號都是成對出現(xiàn)的
思路：連續(xù)四天困難后終于見到春天了。這個題比較簡單。遞歸肯定可以實現(xiàn)。一層一層解析唄。我去代碼實現(xiàn)了。
第一版代碼：
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++;
}
}
}
這個題比較簡單，本來想遞歸，后來發(fā)現(xiàn)其實用棧就行了。畢竟遞歸也就是隱式棧而已。重點就是找出一對一對的括號。所以棧push和pop可以保證遇到的每一個）pop出來的都是對應(yīng)的左括號的位置。然后剩下的就沒啥了，一層一層的翻轉(zhuǎn)就可以了。當(dāng)然了我這里有個問題就是反復(fù)翻轉(zhuǎn)。比如（ab(cd)ef）。我這個代碼會先翻轉(zhuǎn)內(nèi)層括號，變成（ab（dc）ef）然后再翻轉(zhuǎn)外層變成（fe(cd)ba）.然后再統(tǒng)一去括號。理論上這個題絕對可以O(shè)(n)時間復(fù)雜度的，有點懶得想了，我去貼一下性能第一的代碼：
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();
}
}
怎么說呢，這個代碼我想到了。但是實現(xiàn)的時候發(fā)現(xiàn)還挺麻煩，就換了思路，不難想，這個題沒啥好說的。直接過了。
本篇筆記就記到這里，如果稍微幫到你了記得點個喜歡點個關(guān)注。也祝大家工作順順利利，生活健健康康！最近很喜歡的一句話：路漫漫兮其修遠，吾將上下而求索。對于算法來講，有時候覺得真的是門都沒入，愿我們在求索的路上一往無前！
