難度簡單1

給你一個整數(shù) num 。你知道 Danny Mittal 會偷偷將 0 到 9 中的一個數(shù)字 替換 成另一個數(shù)字。

請你返回將 num 中 恰好一個 數(shù)字進行替換后，得到的最大值和最小值的差位多少。

注意：

• 當(dāng) Danny 將一個數(shù)字 d1 替換成另一個數(shù)字 d2 時，Danny 需要將 nums 中所有 d1 都替換成 d2 。
• Danny 可以將一個數(shù)字替換成它自己，也就是說 num 可以不變。
• Danny 可以將數(shù)字分別替換成兩個不同的數(shù)字分別得到最大值和最小值。
• 替換后得到的數(shù)字可以包含前導(dǎo) 0 。
• Danny Mittal 獲得周賽 326 前 10 名，讓我們恭喜他。

示例 1：

輸入：num = 11891
輸出：99009
解釋：
為了得到最大值，我們將數(shù)字 1 替換成數(shù)字 9 ，得到 99899 。
為了得到最小值，我們將數(shù)字 1 替換成數(shù)字 0 ，得到 890 。
兩個數(shù)字的差值為 99009 。

示例 2：

輸入：num = 90
輸出：99
解釋：
可以得到的最大值是 99（將 0 替換成 9），最小值是 0（將 9 替換成 0）。
所以我們得到 99 。

提示：

• 1 <= num <= 108

class Solution {public int minMaxDifference(int num) {String str = num + "";String max = str, min = str;for(int i = 0; i < str.length(); i++){if(str.charAt(i) != '9'){max = str.replace(str.charAt(i),'9');break;}}for(int i = 0; i < str.length(); i++){if(str.charAt(i) != '0'){min = str.replace(str.charAt(i), '0');break;}}return Integer.parseInt(max) - Integer.parseInt(min);}
}

class Solution {public int minMaxDifference(int num) {String str = num + "";char a = str.charAt(0), b = ' ';boolean flag = false;for(int i = 0; i < str.length(); i++){char c = str.charAt(i);if(c != '9'){flag = true;b = c;break;}}String min = str.replace(a, '0');String max = flag ? str.replace(b, '9') : str;return Integer.parseInt(max) - Integer.parseInt(min);}
}

難度中等5

給你一個下標(biāo)從 0 開始的整數(shù)數(shù)組 nums 。

• nums 的 最小 得分是滿足 0 <= i < j < nums.length 的 |nums[i] - nums[j]| 的最小值。
• nums的 最大 得分是滿足 0 <= i < j < nums.length 的 |nums[i] - nums[j]| 的最大值。
• nums 的分?jǐn)?shù)是 最大 得分與 最小 得分的和。

我們的目標(biāo)是最小化 nums 的分?jǐn)?shù)。你 最多 可以修改 nums 中 2 個元素的值。

請你返回修改 nums 中 至多兩個 元素的值后，可以得到的 最小分?jǐn)?shù) 。

|x| 表示 x 的絕對值。

示例 1：

輸入：nums = [1,4,3]
輸出：0
解釋：將 nums[1] 和 nums[2] 的值改為 1 ，nums 變?yōu)?[1,1,1] 。|nums[i] - nums[j]| 的值永遠(yuǎn)為 0 ，所以我們返回 0 + 0 = 0 。

示例 2：

輸入：nums = [1,4,7,8,5]
輸出：3
解釋：
將 nums[0] 和 nums[1] 的值變?yōu)?6 ，nums 變?yōu)?[6,6,7,8,5] 。
最小得分是 i = 0 且 j = 1 時得到的 |nums[i] - nums[j]| = |6 - 6| = 0 。
最大得分是 i = 3 且 j = 4 時得到的 |nums[i] - nums[j]| = |8 - 5| = 3 。
最大得分與最小得分之和為 3 。這是最優(yōu)答案。

提示：

• 3 <= nums.length <= 105
• 1 <= nums[i] <= 109

難度中等6

給你一個下標(biāo)從 0 開始的整數(shù)數(shù)組 nums 。

如果存在一些整數(shù)滿足 0 <= index1 < index2 < ... < indexk < nums.length ，得到 nums[index1] | nums[index2] | ... | nums[indexk] = x ，那么我們說 x 是 可表達(dá)的 。換言之，如果一個整數(shù)能由 nums 的某個子序列的或運算得到，那么它就是可表達(dá)的。

請你返回 nums 不可表達(dá)的 最小非零整數(shù) 。

示例 1：

輸入：nums = [2,1]
輸出：4
解釋：1 和 2 已經(jīng)在數(shù)組中，因為 nums[0] | nums[1] = 2 | 1 = 3 ，所以 3 是可表達(dá)的。由于 4 是不可表達(dá)的，所以我們返回 4 。

示例 2：

輸入：nums = [5,3,2]
輸出：1
解釋：1 是最小不可表達(dá)的數(shù)字。

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109

或操作越或越大

class Solution {public int minImpossibleOR(int[] nums) {// 腦經(jīng)急轉(zhuǎn)彎// 第一個不在nums中的2的冪// 如果2^1, ... , 2^k都在// 那么可以表示所有1...2^(k + 1) - 1的數(shù)Set<Integer> set = new HashSet<>();for(int i : nums){set.add(i);}for(int i = 0; i < 32; i++){if(!set.contains(1 << i)) return 1 << i;}return -1;}
}

難度困難5

給你兩個下標(biāo)從 0 開始的數(shù)組 nums1 和 nums2 ，和一個二維數(shù)組 queries 表示一些操作。總共有 3 種類型的操作：

1. 操作類型 1 為 queries[i] = [1, l, r] 。你需要將 nums1 從下標(biāo) l 到下標(biāo) r 的所有 0 反轉(zhuǎn)成 1 或?qū)?1 反轉(zhuǎn)成 0 。l 和 r 下標(biāo)都從 0 開始。
2. 操作類型 2 為 queries[i] = [2, p, 0] 。對于 0 <= i < n 中的所有下標(biāo)，令 nums2[i] = nums2[i] + nums1[i] * p 。
3. 操作類型 3 為 queries[i] = [3, 0, 0] 。求 nums2 中所有元素的和。

請你返回一個數(shù)組，包含所有第三種操作類型的答案。

示例 1：

輸入：nums1 = [1,0,1], nums2 = [0,0,0], queries = [[1,1,1],[2,1,0],[3,0,0]]
輸出：[3]
解釋：第一個操作后 nums1 變?yōu)?[1,1,1] 。第二個操作后，nums2 變成 [1,1,1] ，所以第三個操作的答案為 3 。所以返回 [3] 。

示例 2：

輸入：nums1 = [1], nums2 = [5], queries = [[2,0,0],[3,0,0]]
輸出：[5]
解釋：第一個操作后，nums2 保持不變?yōu)?[5] ，所以第二個操作的答案是 5 。所以返回 [5] 。

提示：

• 1 <= nums1.length,nums2.length <= 105
• nums1.length = nums2.length
• 1 <= queries.length <= 105
• queries[i].length = 3
• 0 <= l <= r <= nums1.length - 1
• 0 <= p <= 106
• 0 <= nums1[i] <= 1
• 0 <= nums2[i] <= 109

//有錯不想調(diào)試了，后面復(fù)習(xí)線段樹
class Solution {/**操作類型1：lazy更新 ： 0 表示不需要更新 != 0 表示需要更新*/public long[] handleQuery(int[] nums1, int[] nums2, int[][] queries) {int n = nums1.length;List<Long> ans = new ArrayList<>();long sum = 0;for(int x :nums2) sum += x;buildTree(root, 0,n-1, nums1);for(int[] q : queries){if(q[0] == 1) update(root, 0, N, q[1], q[2]);else if(q[0] == 2) sum += q[1] * 1L * sum();else ans.add(sum);}return ans.stream().mapToLong(Long::valueOf).toArray();}class Node {Node left, right;int val, add;}private int N = (int) 1e9;private Node root = new Node();public void buildTree(Node node, int start, int end, int[] nums1) {// 到達(dá)葉子節(jié)點if (start == end) {node.val = nums1[start];return ;}int mid = (start + end) >> 1;node.left = new Node();node.right = new Node();buildTree(node.left, start, mid, nums1);buildTree(node.right, mid + 1, end, nums1);// 向上更新pushUp(node);}//初始值start和end是固定的0-N，l和r是要更新的區(qū)間，更新值為valpublic void update(Node node, int start, int end, int l, int r) {if (l <= start && end <= r) {//node.val += (end - start + 1) * val;node.val = end - start + 1 - node.val;node.add = 1;return;}int mid = (start + end) >> 1;pushDown(node, mid - start + 1, end - mid, mid);if (l <= mid) update(node.left, start, mid, l, r);if (r > mid) update(node.right, mid + 1, end, l, r);pushUp(node);}public int query(Node node, int start, int end, int l, int r) {if (l <= start && end <= r) return node.val;int mid = (start + end) >> 1, ans = 0;pushDown(node, mid - start + 1, end - mid, mid);if (l <= mid) ans += query(node.left, start, mid, l, r);if (r > mid) ans += query(node.right, mid + 1, end, l, r);return ans;}private void pushUp(Node node) {node.val = node.left.val + node.right.val;}private void pushDown(Node node, int leftNum, int rightNum, int mid) {if (node.left == null) node.left = new Node();if (node.right == null) node.right = new Node();if (node.add == 0) return ;node.left.val += mid - leftNum - node.val;node.right.val += rightNum - mid - node.val;// 對區(qū)間進行「加減」的更新操作，下推懶惰標(biāo)記時需要累加起來，不能直接覆蓋node.left.add = 1;node.right.add = 1;node.add = 0;}private int sum(){return root.val;}
}

難度簡單2

給你兩個 二維 整數(shù)數(shù)組 nums1 和 nums2.

• nums1[i] = [idi, vali] 表示編號為 idi 的數(shù)字對應(yīng)的值等于 vali 。
• nums2[i] = [idi, vali] 表示編號為 idi 的數(shù)字對應(yīng)的值等于 vali 。

每個數(shù)組都包含 互不相同 的 id ，并按 id 以 遞增 順序排列。

請你將兩個數(shù)組合并為一個按 id 以遞增順序排列的數(shù)組，并符合下述條件：

• 只有在兩個數(shù)組中至少出現(xiàn)過一次的 id 才能包含在結(jié)果數(shù)組內(nèi)。
• 每個 id 在結(jié)果數(shù)組中 只能出現(xiàn)一次 ，并且其對應(yīng)的值等于兩個數(shù)組中該 id 所對應(yīng)的值求和。如果某個數(shù)組中不存在該 id ，則認(rèn)為其對應(yīng)的值等于 0 。

返回結(jié)果數(shù)組。返回的數(shù)組需要按 id 以遞增順序排列。

示例 1：

輸入：nums1 = [[1,2],[2,3],[4,5]], nums2 = [[1,4],[3,2],[4,1]]
輸出：[[1,6],[2,3],[3,2],[4,6]]
解釋：結(jié)果數(shù)組中包含以下元素：
- id = 1 ，對應(yīng)的值等于 2 + 4 = 6 。
- id = 2 ，對應(yīng)的值等于 3 。
- id = 3 ，對應(yīng)的值等于 2 。
- id = 4 ，對應(yīng)的值等于5 + 1 = 6 。

示例 2：

輸入：nums1 = [[2,4],[3,6],[5,5]], nums2 = [[1,3],[4,3]]
輸出：[[1,3],[2,4],[3,6],[4,3],[5,5]]
解釋：不存在共同 id ，在結(jié)果數(shù)組中只需要包含每個 id 和其對應(yīng)的值。

提示：

• 1 <= nums1.length, nums2.length <= 200
• nums1[i].length == nums2[j].length == 2
• 1 <= idi, vali <= 1000
• 數(shù)組中的 id 互不相同
• 數(shù)據(jù)均按 id 以嚴(yán)格遞增順序排列

class Solution {public int[][] mergeArrays(int[][] nums1, int[][] nums2) {List<int[]> list = new ArrayList<>();int i = 0, j = 0;while(i < nums1.length && j < nums2.length){int key = 0, val = 0;if(nums1[i][0] == nums2[j][0]){val = nums1[i][1] + nums2[j][1];key = nums1[i][0];i++; j++;}else if(nums1[i][0] < nums2[j][0]){val = nums1[i][1];key = nums1[i][0];i++;}else{val = nums2[j][1];key = nums2[j][0];j++;}list.add(new int[]{key, val});}if(i != nums1.length){while(i != nums1.length){list.add(new int[]{nums1[i][0], nums1[i][1]});i++;}}if(j != nums2.length){while(j != nums2.length){list.add(new int[]{nums2[j][0], nums2[j][1]});j++;}}int[][] res = new int[list.size()][2];for(int k = 0; k < list.size(); k++){res[k][0] = list.get(k)[0];res[k][1] = list.get(k)[1];}return res;}
}

難度簡單11

給你一個正整數(shù) n ，你可以執(zhí)行下述操作 任意 次：

• n 加上或減去 2 的某個 冪

返回使 n 等于 0 需要執(zhí)行的 最少 操作數(shù)。

如果 x == 2i 且其中 i >= 0 ，則數(shù)字 x 是 2 的冪。

示例 1：

輸入：n = 39
輸出：3
解釋：我們可以執(zhí)行下述操作：
- n 加上 20 = 1 ，得到 n = 40 。
- n 減去 23 = 8 ，得到 n = 32 。
- n 減去 25 = 32 ，得到 n = 0 。
可以證明使 n 等于 0 需要執(zhí)行的最少操作數(shù)是 3 。

示例 2：

輸入：n = 54
輸出：3
解釋：我們可以執(zhí)行下述操作：
- n 加上 21 = 2 ，得到 n = 56 。
- n 加上 23 = 8 ，得到 n = 64 。
- n 減去 26 = 64 ，得到 n = 0 。
使 n 等于 0 需要執(zhí)行的最少操作數(shù)是 3 。 

提示：

• 1 <= n <= 105