中等

給你一個整數數組 nums 和一個整數 k ，請你統計并返回 該數組中和為 k 的子數組的個數 。

子數組是數組中元素的連續非空序列。

示例 1：

輸入：nums = [1,1,1], k = 2
輸出：2

示例 2：

輸入：nums = [1,2,3], k = 3
輸出：2

提示：

• 1 <= nums.length <= 2 * 104
• -1000 <= nums[i] <= 1000
• -107 <= k <= 107

難度中等113

給你一個字符串 s，請你對 s 的子串進行檢測。

每次檢測，待檢子串都可以表示為 queries[i] = [left, right, k]。我們可以 重新排列 子串 s[left], ..., s[right]，并從中選擇 最多 k 項替換成任何小寫英文字母。

如果在上述檢測過程中，子串可以變成回文形式的字符串，那么檢測結果為 true，否則結果為 false。

返回答案數組 answer[]，其中 answer[i] 是第 i 個待檢子串 queries[i] 的檢測結果。

注意：在替換時，子串中的每個字母都必須作為 獨立的 項進行計數，也就是說，如果 s[left..right] = "aaa" 且 k = 2，我們只能替換其中的兩個字母。（另外，任何檢測都不會修改原始字符串 s，可以認為每次檢測都是獨立的）

示例：

輸入：s = "abcda", queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]
輸出：[true,false,false,true,true]
解釋：
queries[0] : 子串 = "d"，回文。
queries[1] : 子串 = "bc"，不是回文。
queries[2] : 子串 = "abcd"，只替換 1 個字符是變不成回文串的。
queries[3] : 子串 = "abcd"，可以變成回文的 "abba"。 也可以變成 "baab"，先重新排序變成 "bacd"，然后把 "cd" 替換為 "ab"。
queries[4] : 子串 = "abcda"，可以變成回文的 "abcba"。

提示：

• 1 <= s.length, queries.length <= 10^5
• 0 <= queries[i][0] <= queries[i][1] < s.length
• 0 <= queries[i][2] <= s.length
• s 中只有小寫英文字母

中等

給你一個字符串 s ，請你返回滿足以下條件的最長子字符串的長度：每個元音字母，即 ‘a’，‘e’，‘i’，‘o’，‘u’ ，在子字符串中都恰好出現了偶數次。

示例 1：

輸入：s = "eleetminicoworoep"
輸出：13
解釋：最長子字符串是 "leetminicowor" ，它包含 e，i，o 各 2 個，以及 0 個 a，u 。

示例 2：

輸入：s = "leetcodeisgreat"
輸出：5
解釋：最長子字符串是 "leetc" ，其中包含 2 個 e 。

示例 3：

輸入：s = "bcbcbc"
輸出：6
解釋：這個示例中，字符串 "bcbcbc" 本身就是最長的，因為所有的元音 a，e，i，o，u 都出現了 0 次。

提示：

• 1 <= s.length <= 5 x 10^5
• s 只包含小寫英文字母。

class Solution {public int findTheLongestSubstring(String s) {int n = s.length();// 用 bit位 標識對應字母奇偶性// sum[i] 標識 s[0:i) 的子串中每種字母出現次數的奇偶性int[] sum = new int[n+1];for(int i = 0; i < n; i++){int bit = 0;// 每個元音字母，即 'a'，'e'，'i'，'o'，'u' ，在子字符串中都恰好出現了偶數次。if(check(s.charAt(i)))bit = 1 << (s.charAt(i) - 'a');sum[i+1] = sum[i] ^ bit; }int res = 0;// 問題化為兩數之和  a ^ b = 0Map<Integer, Integer> map = new HashMap<>();for(int i = 0; i <= n; i++){// 注意求最長串長度，map中只保存sum第一次出現位置if(map.containsKey(sum[i]))res = Math.max(res, i - map.get(sum[i]));elsemap.put(sum[i], i);}return res;}public boolean check(Character c){return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';}
}

困難

給你一個字符串 s 。請返回 s 中最長的 超贊子字符串 的長度。

「超贊子字符串」需滿足滿足下述兩個條件：

• 該字符串是 s 的一個非空子字符串
• 進行任意次數的字符交換后，該字符串可以變成一個回文字符串

示例 1：

輸入：s = "3242415"
輸出：5
解釋："24241" 是最長的超贊子字符串，交換其中的字符后，可以得到回文 "24142"

示例 2：

輸入：s = "12345678"
輸出：1

示例 3：

輸入：s = "213123"
輸出：6
解釋："213123" 是最長的超贊子字符串，交換其中的字符后，可以得到回文 "231132"

示例 4：

輸入：s = "00"
輸出：2

提示：

• 1 <= s.length <= 10^5
• s 僅由數字組成

class Solution {/**進行任意次數的字符交換后，該字符串可以變成一個回文字符串 ==> 字符串「不同字符出現次數」為奇數的個數 <= 1*/public int longestAwesome(String s) {int n = s.length();int[] sum = new int[n+1];for(int i = 0; i < n; i++){int bit = 1 << (s.charAt(i) - '0');sum[i+1] = sum[i] ^ bit;}int res = 0;// 問題轉化為兩數之和 // a ^ b = 1 / 10 / 100 / 1000...Map<Integer, Integer> map = new HashMap<>();for(int i = 0; i <= n; i++){// 字符串「不同字符出現次數」為奇數的個數 = 0if(map.containsKey(sum[i]))res = Math.max(res, i - map.get(sum[i]));// 字符串「不同字符出現次數」為奇數的個數 = 1for(int j = 0; j < 10; j++){int target = (1 << j);// a ^ b == target ==> a = target ^ bif(map.containsKey(target ^ sum[i]))res = Math.max(res, i - map.get(target ^ sum[i]));}// 注意求最長串長度，map中只保存sum第一次出現位置if(!map.containsKey(sum[i]))map.put(sum[i], i);}return res;}
}

中等

如果某個字符串中 至多一個 字母出現 奇數 次，則稱其為 最美 字符串。

• 例如，"ccjjc" 和 "abab" 都是最美字符串，但 "ab" 不是。

給你一個字符串 word ，該字符串由前十個小寫英文字母組成（'a' 到 'j'）。請你返回 word 中 最美非空子字符串 的數目*。如果同樣的子字符串在 word 中出現多次，那么應當對 每次出現 分別計數。*

子字符串 是字符串中的一個連續字符序列。

示例 1：

輸入：word = "aba"
輸出：4
解釋：4 個最美子字符串如下所示：
- "aba" -> "a"
- "aba" -> "b"
- "aba" -> "a"
- "aba" -> "aba"

示例 2：

輸入：word = "aabb"
輸出：9
解釋：9 個最美子字符串如下所示：
- "aabb" -> "a"
- "aabb" -> "aa"
- "aabb" -> "aab"
- "aabb" -> "aabb"
- "aabb" -> "a"
- "aabb" -> "abb"
- "aabb" -> "b"
- "aabb" -> "bb"
- "aabb" -> "b"

示例 3：

輸入：word = "he"
輸出：2
解釋：2 個最美子字符串如下所示：
- "he" -> "h"
- "he" -> "e"

提示：

• 1 <= word.length <= 105
• word 由從 'a' 到 'j' 的小寫英文字母組成

class Solution {public long wonderfulSubstrings(String word) {int n = word.length();int[] sum = new int[n+1];for(int i = 0; i < n; i++){int bit = (1 << (word.charAt(i) - 'a'));sum[i+1] = sum[i] ^ bit;}long res = 0;Map<Integer, Integer> map = new HashMap<>();// 某個字符串中 至多一個 字母出現 奇數 次for(int i = 0; i <= n; i++){if(map.containsKey(sum[i]))res += map.get(sum[i]);for(int j = 0; j < 11; j++){int target = (1 << j);if(map.containsKey(target ^ sum[i]))res += map.get(target ^ sum[i]);}map.merge(sum[i], 1, Integer::sum);}return res;}
}

難度中等10

給你一個下標從 0 開始的整數數組 nums 和一個正整數 k 。

你可以對數組執行下述操作 任意次 ：

• 從數組中選出長度為 k 的 任一 子數組，并將子數組中每個元素都 減去 1 。

如果你可以使數組中的所有元素都等于 0 ，返回 true ；否則，返回 false 。

子數組 是數組中的一個非空連續元素序列。

示例 1：

輸入：nums = [2,2,3,1,1,0], k = 3
輸出：true
解釋：可以執行下述操作：
- 選出子數組 [2,2,3] ，執行操作后，數組變為 nums = [1,1,2,1,1,0] 。
- 選出子數組 [2,1,1] ，執行操作后，數組變為 nums = [1,1,1,0,0,0] 。
- 選出子數組 [1,1,1] ，執行操作后，數組變為 nums = [0,0,0,0,0,0] 。

示例 2：

輸入：nums = [1,3,1,1], k = 2
輸出：false
解釋：無法使數組中的所有元素等于 0 。

提示：

• 1 <= k <= nums.length <= 105
• 0 <= nums[i] <= 106

差分

class Solution {public boolean checkArray(int[] nums, int k) {int n = nums.length;int[] diff = new int[n + 1]; // 差分數組int s = 0; // 第 i 位被減的次數（<0，或者說差分數組當前值 i）for(int i = 0; i < nums.length; i++){s += diff[i]; // 累加標記，獲得差分數組當前值(被減的次數< 0)nums[i] = nums[i] + s; // 將當前位減去 操作次數if(nums[i] < 0) return false;if(nums[i] > 0){ // 還需要減掉 nums[i]，使得nums[i] = 0if(i + k > n) { // 表示無法操作區間為k的子數組了return false;}s -= nums[i]; // diff[i] -= nums[i]，由于不會遍歷diff[i]了，所以直接將影響放在s上diff[i+k] += nums[i]; // 只操作i+k的區間，恢復}}return true;}
}

可能變一下s的意思更好理解

class Solution {public boolean checkArray(int[] nums, int k) {int n = nums.length;int[] diff = new int[n+1];int s = 0; // 定義s表示 第i位被減去的次數(>0，操作的次數)for(int i = 0; i < n; i++){// 恢復第 i 位的值s += diff[i];nums[i] -= s; // 將第 i 位減去操作次數sif(nums[i] < 0) return false;if(nums[i] > 0){if(i+k > n) return false;// 區間再減去nums[i](diff[i] -= nums[i] and diff[i+k] -= nums[i])s += nums[i]; diff[i+k] -= nums[i]; }}return true;}
}

難度困難28

給你一個下標從 0 開始長度為 n 的整數數組 stations ，其中 stations[i] 表示第 i 座城市的供電站數目。

每個供電站可以在一定 范圍 內給所有城市提供電力。換句話說，如果給定的范圍是 r ，在城市 i 處的供電站可以給所有滿足 |i - j| <= r 且 0 <= i, j <= n - 1 的城市 j 供電。

• |x| 表示 x 的 絕對值 。比方說，|7 - 5| = 2 ，|3 - 10| = 7 。

一座城市的 電量 是所有能給它供電的供電站數目。

政府批準了可以額外建造 k 座供電站，你需要決定這些供電站分別應該建在哪里，這些供電站與已經存在的供電站有相同的供電范圍。

給你兩個整數 r 和 k ，如果以最優策略建造額外的發電站，返回所有城市中，最小供電站數目的最大值是多少。

這 k 座供電站可以建在多個城市。

示例 1：

輸入：stations = [1,2,4,5,0], r = 1, k = 2
輸出：5
解釋：
最優方案之一是把 2 座供電站都建在城市 1 。
每座城市的供電站數目分別為 [1,4,4,5,0] 。
- 城市 0 的供電站數目為 1 + 4 = 5 。
- 城市 1 的供電站數目為 1 + 4 + 4 = 9 。
- 城市 2 的供電站數目為 4 + 4 + 5 = 13 。
- 城市 3 的供電站數目為 5 + 4 = 9 。
- 城市 4 的供電站數目為 5 + 0 = 5 。
供電站數目最少是 5 。
無法得到更優解，所以我們返回 5 。

示例 2：

輸入：stations = [4,4,4,4], r = 0, k = 3
輸出：4
解釋：
無論如何安排，總有一座城市的供電站數目是 4 ，所以最優解是 4 。

提示：

• n == stations.length
• 1 <= n <= 105
• 0 <= stations[i] <= 105
• 0 <= r <= n - 1
• 0 <= k <= 109

class Solution {public long maxPower(int[] stations, int r, int k) {long left = 0, right = (long)1e15;while (left < right) {long mid = (left + right + 1) >> 1;if (!check(stations, r, k, mid))right = mid - 1;elseleft = mid;}return right;}// 將 i 位置供電站stations[i] 化為 區間[i-r, i+r] 的供電站數量，使用差分數組來維護區間更新后的值// 查看在 至多增加k個供電站 的條件下，每個城市最小供電站數目能否>=mnpower// 特別的，從左往右遍歷，當 i-r 位置城市供電站數目 < mnpower時，則需要在 r位置 建造供電站public boolean check(int[] stations, int r, int k, long mnpower) {int n = stations.length;long cnt = 0; // 額外建造供電站的數量long[] diff = new long[n + r + 1];for (int i = 0; i < r; i++) {diff[0] += stations[i];diff[i + r + 1] -= stations[i];}long s = 0; // 差分數組的當前值(第 i-r 位置上供電站的數目)for (int i = r; i < n + r; i++) {if (i < n) {diff[i - r] += stations[i];diff[i + r + 1] -= stations[i];}s += diff[i - r]; // 恢復 i-r 位置供電站數量if (s < mnpower) {long add = mnpower - s;cnt += add;if (cnt > k)return false;s += add;if (i < n)diff[i + r + 1] -= add;}}return true;}
}