黑板異或游戲
題目：黑板上寫著一個(gè)非負(fù)整數(shù)數(shù)組 nums[i] 使兔。Alice 和 Bob 輪流從黑板上擦掉一個(gè)數(shù)字践图，Alice 先手哮笆。如果擦除一個(gè)數(shù)字后朝聋，剩余的所有數(shù)字按位異或運(yùn)算得出的結(jié)果等于 0 的話嗡午，當(dāng)前玩家游戲失敗。 (另外冀痕，如果只剩一個(gè)數(shù)字荔睹，按位異或運(yùn)算得到它本身；如果無數(shù)字剩余言蛇，按位異或運(yùn)算結(jié)果為 0应媚。）并且，輪到某個(gè)玩家時(shí)猜极，如果當(dāng)前黑板上所有數(shù)字按位異或運(yùn)算結(jié)果等于 0，這個(gè)玩家獲勝消玄。假設(shè)兩個(gè)玩家每步都使用最優(yōu)解跟伏，當(dāng)且僅當(dāng) Alice 獲勝時(shí)返回 true。
示例：
輸入: nums = [1, 1, 2]
輸出: false
解釋:
Alice 有兩個(gè)選擇: 擦掉數(shù)字 1 或 2翩瓜。
如果擦掉 1, 數(shù)組變成 [1, 2]受扳。剩余數(shù)字按位異或得到 1 XOR 2 = 3。那么 Bob 可以擦掉任意數(shù)字兔跌，因?yàn)?Alice 會(huì)成為擦掉最后一個(gè)數(shù)字的人勘高，她總是會(huì)輸。
如果 Alice 擦掉 2坟桅，那么數(shù)組變成[1, 1]华望。剩余數(shù)字按位異或得到 1 XOR 1 = 0。Alice 仍然會(huì)輸?shù)粲螒颉?br> 提示：
1 <= N <= 1000
0 <= nums[i] <= 2^16
思路：這個(gè)題是2021/5/22的每日一題仅乓。5月果然是異或月赖舟。不過這個(gè)題是困難的。因?yàn)镹是大于0的夸楣。所以我們可以這么說宾抓，一個(gè)數(shù)組異或和不為0且元素?cái)?shù)大于1的話，肯定是可以找出一個(gè)數(shù)刪除豫喧，并且結(jié)果不為0.這個(gè)題目的標(biāo)簽是數(shù)學(xué)石洗，我覺得大概率是個(gè)找規(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ī)律鸟妙。這個(gè)題果然是數(shù)學(xué)題焦人。首先因?yàn)閮蓚€(gè)人是一個(gè)一個(gè)的拿挥吵。所以可以得出如此結(jié)論：如果A拿的時(shí)候是偶數(shù)，則每次A拿都是偶數(shù)花椭。而如果是偶數(shù)的話忽匈，異或非0，每個(gè)元素都大于0.所以擦掉一個(gè)元素不可能會(huì)出現(xiàn)0.也就是說A處于不敗的矿辽。
于是數(shù)組如果是偶數(shù)個(gè)A肯定獲勝丹允，直接true。
而如果是奇數(shù)的話袋倔，除非一上來A就獲勝了雕蔽，也就是全部元素異或?yàn)?了。否則就是B陷入不敗之地宾娜。所以結(jié)果如上批狐。
感覺這個(gè)題目看了題解很容易明白，但是自己想反正我是怎么也沒想出來前塔。這個(gè)題過了嚣艇，下一題。
數(shù)組中元素的最大異或值
題目：給你一個(gè)由非負(fù)整數(shù)組成的數(shù)組 nums 华弓。另有一個(gè)查詢數(shù)組 queries 食零，其中 queries[i] = [xi, mi] 。第 i 個(gè)查詢的答案是 xi 和任何 nums 數(shù)組中不超過 mi 的元素按位異或（XOR）得到的最大值寂屏。換句話說贰谣，答案是 max(nums[j] XOR xi) ，其中所有 j 均滿足 nums[j] <= mi 迁霎。如果 nums 中的所有元素都大于 mi吱抚，最終答案就是 -1 。返回一個(gè)整數(shù)數(shù)組 answer 作為查詢的答案考廉，其中 answer.length == queries.length 且 answer[i] 是第 i 個(gè)查詢的答案频伤。
示例 1：
輸入：nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]]
輸出：[3,3,7]
解釋：
- 0 和 1 是僅有的兩個(gè)不超過 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ù)范圍挺大岸更，所以暴力法肯定會(huì)超時(shí)，我就不尋思了膊升。其次因?yàn)閿?shù)值的范圍是10的九次方怎炊。所以說數(shù)組代替下標(biāo)排序這個(gè)想法也不現(xiàn)實(shí)。我暫時(shí)的想法是用前綴樹。因?yàn)槠鋵?shí)這個(gè)異或最大其實(shí)是有規(guī)律的评肆。比如當(dāng)前100110.異或最大的實(shí)現(xiàn)是盡量讓每一位都為0债查，如果無法實(shí)現(xiàn)也應(yīng)該是盡可能讓前面的位數(shù)為1.我們?nèi)ゲ榭磧蓚€(gè)數(shù)的位數(shù)。然后從第一位是1開始往下盡量找后面也是1的瓜挽。如果沒選擇0也行盹廷。差不多就是這個(gè)思路，我去實(shí)現(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];//一個(gè)1俄占，一個(gè)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;
}
}
上面的代碼是嘔心瀝血寫出來的祝拯。各種細(xì)節(jié)老厌，各種位運(yùn)算用到什么查什么堤如。了牛。米者。本來如果沒有l(wèi)imit是很簡單的一個(gè)題目。難點(diǎn)主要是在limit上畜晰。所以這里引用了一個(gè)每個(gè)樹的根樹上是有當(dāng)前子樹的最小值的。如果最小值還大于limit瑞筐，說明這個(gè)分支根本不能走凄鼻。然后如果當(dāng)前元素沒有對應(yīng)元素，則只能當(dāng)前元素勉強(qiáng)為0繼續(xù)往下判斷聚假。
然后這個(gè)題對我來說難點(diǎn)最大的就是位運(yùn)算了块蚌，像是我說的一點(diǎn)點(diǎn)去百度的。還有中間ans的或運(yùn)算膘格。我本來想直接拼接二進(jìn)制的峭范。后來發(fā)現(xiàn)太麻煩了就繼續(xù)找位運(yùn)算的實(shí)現(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)崩了纱控，這個(gè)代碼沒太看懂。簡單理一下：因?yàn)榇嬖谥貜?fù)元素菜秦，所以這個(gè)題手動(dòng)把不同的元素排序甜害，隊(duì)列變成了長度為len的升序了。
然后就用了一種二分法搜索了什么球昨，到這就已經(jīng)看不懂了尔店，所以這個(gè)就這樣吧，起碼用我的笨方法也能對付實(shí)現(xiàn)，下一題了嚣州。
奇怪的打印機(jī)
題目：有臺奇怪的打印機(jī)有以下兩個(gè)特殊要求：打印機(jī)每次只能打印由 同一個(gè)字符 組成的序列鲫售。每次可以在任意起始和結(jié)束位置打印新字符，并且會(huì)覆蓋掉原來已有的字符该肴。給你一個(gè)字符串 s 情竹，你的任務(wù)是計(jì)算這個(gè)打印機(jī)打印它需要的最少打印次數(shù)。
示例 1：
輸入：s = "aaabbb"
輸出：2
解釋：首先打印 "aaa" 然后打印 "bbb"沙庐。
示例 2：
輸入：s = "aba"
輸出：2
解釋：首先打印 "aaa" 然后在第二個(gè)位置打印 "b" 覆蓋掉原來的字符 'a'鲤妥。
提示：
1 <= s.length <= 100
s 由小寫英文字母組成
思路：2021/5/24的每日一題，說真的拱雏，這個(gè)打印機(jī)真是太奇怪了棉安，換一個(gè)就解決問題了。然后繼續(xù)說這道題铸抑，我的想法是第一步打底：也就是看從頭到尾是哪個(gè)元素出現(xiàn)的次數(shù)多贡耽，則頭到尾是這個(gè)字母。然后在這個(gè)字母的基礎(chǔ)上來覆蓋鹊汛。而每一層覆蓋都可以看成是一次遍歷蒲赂。這個(gè)題目的標(biāo)簽是深搜和動(dòng)態(tài)規(guī)劃。感覺可以變成遞歸子問題刁憋。目前為止大概思路就是這樣滥嘴，我去代碼實(shí)現(xiàn)試試。
第一版代碼思路有點(diǎn)問題至耻。本來我是每一次找到出現(xiàn)次數(shù)最多的元素統(tǒng)一打印若皱。然后再去拆分中間的具體次數(shù)的。結(jié)果發(fā)現(xiàn)遇到回文的那種abcdadcba這樣的就會(huì)出錯(cuò)尘颓。但是就因?yàn)檫@樣又恰好符合了dp的思路：因?yàn)閍bcda其實(shí)和abcd本質(zhì)上應(yīng)該是一樣的次數(shù)走触。最后一個(gè)a完全可以在第一個(gè)a的時(shí)候順便打印。也就是遞推公式的一部分：s[i]==s[j],那么打印次數(shù)：i到j(luò)應(yīng)該和i到j(luò)-1一樣疤苹。
問題是當(dāng)s[i]!=s[j]的時(shí)候互广，哪怕i和j-1中間出現(xiàn)了s[j]，我們也不能保證j-1填充的時(shí)候可以填到最后卧土。所以這個(gè)時(shí)候要分情況判斷了惫皱。到底是之前的+1還是可以直接上一次填充s[j]的時(shí)候待著這個(gè)元素。尤莺∫莩常總而言之思路是這樣的，我去實(shí)現(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];
}
//所有的排序扫皱。其實(shí)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 {//這個(gè)時(shí)候要看是+1還是不加了韩脑。
int min = Integer.MAX_VALUE;
for(int k = i;k<j;k++) {
//重點(diǎn)是這步：因?yàn)橹暗膁p[i][i]填充了1氢妈，所以最大的值也不過是dp[i][j-1]+1
//問題是最小值的可能：有沒有一個(gè)節(jié)點(diǎn)，讓當(dāng)前元素能混進(jìn)去
//如果有其實(shí)結(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];
}
}
這個(gè)重點(diǎn)就還是這個(gè)+1不加1的問題段多。而且單一某個(gè)元素一定要印刷一次首量，所以dp[i][i] = 1.
然后順著二維數(shù)組往上推：最終推到第一行。差不多如下圖所示：
大概思路就這樣进苍，果然有dp標(biāo)簽dp是跑不了的加缘。我一開始就不應(yīng)該沉迷深搜無法自拔。觉啊。我這個(gè)代碼性能超過百分之八十九拣宏，我再去看看性能第一的代碼。
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];
}
}
但凡每次我覺得我行了杠人，力扣總能輕蔑的告訴我勋乾，我不行。
這個(gè)代碼是我想象中的樣子嗡善，但是我自己沒寫出來辑莫。
之前我就說了，斷點(diǎn)一定是從和s[j]相等的元素中開始的罩引。但是我自己覺得真的實(shí)現(xiàn)起來太麻煩了各吨，就暴力遍歷了一遍，可是人家把這個(gè)思路用代碼實(shí)現(xiàn)了袁铐。用一種套接下標(biāo)的形式揭蜒，可以追根溯源。昭躺。總而言之大寫的服伪嫁。
然后別的就沒啥了领炫，整體遞推公式的一樣的思路。下一題张咳。
所有可能的滿二叉樹
題目：滿二叉樹是一類二叉樹帝洪，其中每個(gè)結(jié)點(diǎn)恰好有 0 或 2 個(gè)子結(jié)點(diǎn)。返回包含 N 個(gè)結(jié)點(diǎn)的所有可能滿二叉樹的列表脚猾。 答案的每個(gè)元素都是一個(gè)可能樹的根結(jié)點(diǎn)葱峡。答案中每個(gè)樹的每個(gè)結(jié)點(diǎn)都必須有 node.val=0。你可以按任何順序返回樹的最終列表龙助。
思路：首先這個(gè)題的數(shù)據(jù)范圍n小于等于20.而且其實(shí)這里有個(gè)概念：n是偶數(shù)的時(shí)候砰奕，是不可能有結(jié)果的。因?yàn)楸厝挥幸粋€(gè)根節(jié)點(diǎn)是單獨(dú)的。每個(gè)子節(jié)點(diǎn)都要0/2個(gè)子節(jié)點(diǎn)军援，所以偶數(shù)個(gè)節(jié)點(diǎn)是組不成完美二叉樹的仅淑。所以只要判斷奇數(shù)情況。N的范圍其實(shí)1,3,5胸哥。涯竟。。19.又縮小了一半空厌。庐船。我有個(gè)大膽的想法，不知道每種情況枚舉下來行不行嘲更。筐钟。。嘿嘿嘿哮内。算了盗棵，正經(jīng)一點(diǎn);題目標(biāo)簽是遞歸，所以我覺得首先根節(jié)點(diǎn)一定要有的北发。其次如果還有多余的元素則左右節(jié)點(diǎn)必有纹因。這個(gè)時(shí)候把左右單獨(dú)遞歸。節(jié)點(diǎn)數(shù)的分法肯定是奇數(shù)分琳拨。比如說n=15.那么初始根節(jié)點(diǎn)用一個(gè)瞭恰。左右分別1-13。3-11狱庇，5-9惊畏，7-7，9-5密任，11-3颜启，13-1.這樣。然後其實(shí)本質(zhì)上我覺得肯定是左右可以對稱的浪讳。然後再依次往下去遍歷缰盏。大概思路是這樣，我去代碼實(shí)現(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é)點(diǎn)和口猜，right是右子樹的。因?yàn)楦?jié)點(diǎn)占了一個(gè)透揣，所以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;
}
}
這個(gè)題的重點(diǎn)就是左右子樹的每一種可能都要去計(jì)算济炎。雖然這個(gè)代碼ac了，但是我覺得可優(yōu)化的點(diǎn)應(yīng)該是記憶化：比如說子樹元素是3,5,7的這些其實(shí)只要計(jì)算一次就行了辐真，但是如上我的寫法是計(jì)算了好幾次须尚。我去試試優(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é)點(diǎn)和，right是右子樹的恨闪。因?yàn)楦?jié)點(diǎn)占了一個(gè)倘感，所以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);
}
}
這個(gè)代碼1ms，是這個(gè)題的最快速度了咙咽。和第一版本相比就做了一個(gè)改變:將固定元素?cái)?shù)的數(shù)字對應(yīng)的所有樹保存起來老玛。然后重復(fù)運(yùn)算的時(shí)候可以直接取值。剩下的沒啥區(qū)別了钧敞。這個(gè)題因?yàn)橐呀?jīng)性能最好了蜡豹，所以我就不看性能第一的代碼了，下一題溉苛。
使所有區(qū)間的異或結(jié)果為0
題目：給你一個(gè)整數(shù)數(shù)組 nums 和一個(gè)整數(shù) k 镜廉。區(qū)間 [left, right]（left <= right）的 異或結(jié)果 是對下標(biāo)位于 left 和 right（包括 left 和 right ）之間所有元素進(jìn)行 XOR 運(yùn)算的結(jié)果：nums[left] XOR nums[left+1] XOR ... XOR nums[right] 。返回?cái)?shù)組中 要更改的最小元素?cái)?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的每日一題。又叒叕是困難的寂玲，力扣這個(gè)四連困難有點(diǎn)東西啊塔插，感覺是在勸退像我這樣的fw，哎拓哟，回歸到這個(gè)題目吧想许。首先異或結(jié)果等于0，其實(shí)任何組合最多改變一個(gè)數(shù)就可以歸0 断序，當(dāng)然了最少的也是最好的是不需要改變直接歸0.而且通過給的兩個(gè)例子我們可以看出來如果想做到滿足要求的結(jié)果流纹，必然是以k為單位的循環(huán)。而說到了以k為單位的循環(huán)违诗，我覺得這個(gè)題的思路差不多就來了漱凝，然后2的10次方，剛剛算了一下發(fā)現(xiàn)才1024诸迟，所以數(shù)據(jù)量也不是很大茸炒。初步的想法是每一組K個(gè)元素。然后分成總數(shù)/k向上取整組亮蒋。然后按位對比扣典。一樣的多的不該妆毕。不一樣的多的改慎玖。最終要實(shí)現(xiàn)以k長為子串的循環(huán)。思路大概是這樣笛粘，我去代碼實(shí)現(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)計(jì)當(dāng)前列的「每個(gè)數(shù)的出現(xiàn)次數(shù)」和「有多少個(gè)數(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];
}
這個(gè)主要是實(shí)現(xiàn)上面說過了润努，但是怎么落實(shí)到代碼中很難关斜。但是有一個(gè)重點(diǎn)：我們不知道一組k長度的元素的循環(huán)體是什么樣子的。反正這個(gè)題可以演變成：
因此我們將這個(gè)一維的輸入看成二維铺浇，從而將問題轉(zhuǎn)化為：全部元素K個(gè)分一列痢畜。使得最終每列相等，同時(shí)「首行」的異或值為 0的最小修改次數(shù)鳍侣。因?yàn)樽詈笠涣锌赡懿皇峭暾亩∠。詻]說每列都異或?yàn)?.上面的代碼看似是一個(gè)一維數(shù)組，但是本質(zhì)上是二維數(shù)組的壓縮倚聚，因?yàn)橄乱恍兄缓蜕弦恍袪顟B(tài)有關(guān)线衫，所以這里用了兩個(gè)一維數(shù)組來交替存儲(chǔ)狀態(tài)。這是個(gè)很常見的技巧惑折。
繼續(xù)說這個(gè)題的遞推公式：其實(shí)第一列需要考慮的情況比較簡單授账， 只要所有的元素一樣就行了。所以計(jì)數(shù)也簡單惨驶，只要存儲(chǔ)這列非當(dāng)前元素的個(gè)數(shù)就行了（因?yàn)槿绻胍@列變成當(dāng)前元素白热，那么目前不是的都要改，所以計(jì)住要改多少）敞咧。
然后第二列開始既然是奇數(shù)第二列的元素和出現(xiàn)次數(shù)棘捣。但是這里計(jì)算就是1,2列的元素的異或結(jié)果。想要這一行異或結(jié)果為0那么要前面的列的異或結(jié)果等于最后一列的值休建，這里我是反復(fù)看debug的數(shù)據(jù)變化的乍恐。對于某一列來講，最壞的結(jié)果就是整列替換测砂，所以保底就是列的個(gè)數(shù)茵烈。
比如1,2,3,1,3,4,1,2,5,1，2砌些，k=3.這樣的結(jié)果第一個(gè)遍歷應(yīng)該如下（下標(biāo)從0開始）：
4,0呜投，4,4...（因?yàn)榉殖伤慕M，所以如果想要第一列都為0則要變四次存璃。想要第一列都為1不用變了仑荐，想要第一列都為2變4次，依次類推）
第二次遍歷的結(jié)果如下：
4,4,3,1,4,4,,,,（這里這里的3,和1出現(xiàn)的原因：因?yàn)榈谝涣惺?纵东，當(dāng)前列三個(gè)2一個(gè)3.1異或2的結(jié)果是3粘招，所以如果想要第三列是3的話，需要改動(dòng)一個(gè)元素偎球，也就是第二列那一個(gè)三洒扎。同理如果想要第三列是2的話辑甜，需要改動(dòng)三個(gè)元素，也就是第二列的三個(gè)2.4就不用解釋了袍冷，整列更改）
第三個(gè)遍歷的結(jié)果：
3,4,4,4...（這個(gè)和第二遍是類似的磷醋，想要當(dāng)前排異或結(jié)果為0則需要改變3個(gè)元素。因?yàn)楸举|(zhì)上最后一列是3,4,5這三個(gè)元素胡诗。而前兩列的異或結(jié)果是2有一次邓线。3有三次。而想要當(dāng)前總異或結(jié)果為0.3本身就可以用了煌恢，所以只需要改變4,5這兩個(gè)就行了褂痰。但是因?yàn)榈诙抛兂啥际?就要改變一次。所以到當(dāng)前變成都是0就是2+1也就是三次症虑。）
因?yàn)閗=3.所以到此就計(jì)算結(jié)束缩歪。而答案就是最后一排的下標(biāo)為0的結(jié)果。
最后一排下標(biāo)為0說明的就是到了最后一列谍憔，保持整行異或?yàn)?的最小次數(shù)匪蝙。
如是，這題完事了习贫。
看著題解跑了兩個(gè)多小時(shí)才看明白逛球，自己做是廢了，這個(gè)題就這樣吧苫昌，下一題颤绕。
反轉(zhuǎn)每對括號間的子串
題目：給出一個(gè)字符串 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ù)四天困難后終于見到春天了。這個(gè)題比較簡單婉陷。遞歸肯定可以實(shí)現(xiàn)帚称。一層一層解析唄。我去代碼實(shí)現(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++;
}
}
}
這個(gè)題比較簡單闯睹，本來想遞歸，后來發(fā)現(xiàn)其實(shí)用棧就行了担神。畢竟遞歸也就是隱式棧而已楼吃。重點(diǎn)就是找出一對一對的括號。所以棧push和pop可以保證遇到的每一個(gè)）pop出來的都是對應(yīng)的左括號的位置。然后剩下的就沒啥了所刀，一層一層的翻轉(zhuǎn)就可以了。當(dāng)然了我這里有個(gè)問題就是反復(fù)翻轉(zhuǎn)捞挥。比如（ab(cd)ef）浮创。我這個(gè)代碼會(huì)先翻轉(zhuǎn)內(nèi)層括號，變成（ab（dc）ef）然后再翻轉(zhuǎn)外層變成（fe(cd)ba）.然后再統(tǒng)一去括號砌函。理論上這個(gè)題絕對可以O(shè)(n)時(shí)間復(fù)雜度的斩披，有點(diǎ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();
}
}
怎么說呢讹俊，這個(gè)代碼我想到了垦沉。但是實(shí)現(xiàn)的時(shí)候發(fā)現(xiàn)還挺麻煩，就換了思路仍劈，不難想厕倍，這個(gè)題沒啥好說的。直接過了贩疙。
本篇筆記就記到這里讹弯，如果稍微幫到你了記得點(diǎn)個(gè)喜歡點(diǎn)個(gè)關(guān)注。也祝大家工作順順利利这溅，生活健健康康组民！最近很喜歡的一句話：路漫漫兮其修遠(yuǎn)，吾將上下而求索悲靴。對于算法來講臭胜，有時(shí)候覺得真的是門都沒入，愿我們在求索的路上一往無前癞尚！
