🌟歡迎來(lái)到 我的博客 —— 探索技術(shù)的無(wú)限可能！

🌟博客的簡(jiǎn)介（文章目錄）

---

【題解】—— 每日一道題目欄

---

上接：【題解】—— LeetCode一周小結(jié)31

5.不含連續(xù)1的非負(fù)整數(shù)

題目鏈接：600. 不含連續(xù)1的非負(fù)整數(shù)

給定一個(gè)正整數(shù) n ，請(qǐng)你統(tǒng)計(jì)在 [0, n] 范圍的非負(fù)整數(shù)中，有多少個(gè)整數(shù)的二進(jìn)制表示中不存在 連續(xù)的 1 。

示例 1:

輸入: n = 5

輸出: 5

解釋:

下面列出范圍在 [0, 5] 的非負(fù)整數(shù)與其對(duì)應(yīng)的二進(jìn)制表示：

0 : 0

1 : 1

2 : 10

3 : 11

4 : 100

5 : 101

其中，只有整數(shù) 3 違反規(guī)則（有兩個(gè)連續(xù)的 1 ），其他 5 個(gè)滿足規(guī)則。

示例 2:

輸入: n = 1

輸出: 2

示例 3:

輸入: n = 2

輸出: 3

提示:

1 <= n <= 109

題解：
方法：數(shù)位 DP
????????

class Solution {public int findIntegers(int n) {int m = Integer.SIZE - Integer.numberOfLeadingZeros(n);int[][] memo = new int[m][2];for (int[] row : memo) {Arrays.fill(row, -1); // -1 表示沒(méi)有計(jì)算過(guò)}return dfs(m - 1, 0, true, n, memo); // 從高位到低位}// pre 表示前一個(gè)比特位填的數(shù)private int dfs(int i, int pre, boolean isLimit, int n, int[][] memo) {if (i < 0) {return 1;}if (!isLimit && memo[i][pre] >= 0) { // 之前計(jì)算過(guò)return memo[i][pre];}int up = isLimit ? n >> i & 1 : 1;int res = dfs(i - 1, 0, isLimit && up == 0, n, memo); // 填 0if (pre == 0 && up == 1) { // 可以填 1res += dfs(i - 1, 1, isLimit, n, memo); // 填 1}if (!isLimit) {memo[i][pre] = res; // 記憶化}return res;}
}

---

6.找出所有穩(wěn)定的二進(jìn)制數(shù)組 I

題目鏈接：3129. 找出所有穩(wěn)定的二進(jìn)制數(shù)組 I

給你 3 個(gè)正整數(shù) zero ，one 和 limit 。

一個(gè)
二進(jìn)制數(shù)組
arr 如果滿足以下條件，那么我們稱它是 穩(wěn)定的 ：

0 在 arr 中出現(xiàn)次數(shù) 恰好 為 zero 。
1 在 arr 中出現(xiàn)次數(shù) 恰好 為 one 。
arr 中每個(gè)長(zhǎng)度超過(guò) limit 的
子數(shù)組
都 同時(shí) 包含 0 和 1 。
請(qǐng)你返回 穩(wěn)定 二進(jìn)制數(shù)組的 總 數(shù)目。

由于答案可能很大，將它對(duì) 109 + 7 取余 后返回。

示例 1：

輸入：zero = 1, one = 1, limit = 2

輸出：2

解釋：

兩個(gè)穩(wěn)定的二進(jìn)制數(shù)組為 [1,0] 和 [0,1] ，兩個(gè)數(shù)組都有一個(gè) 0 和一個(gè) 1 ，且沒(méi)有子數(shù)組長(zhǎng)度大于 2 。

示例 2：

輸入：zero = 1, one = 2, limit = 1

輸出：1

解釋：

唯一穩(wěn)定的二進(jìn)制數(shù)組是 [1,0,1] 。

二進(jìn)制數(shù)組 [1,1,0] 和 [0,1,1] 都有長(zhǎng)度為 2 且元素全都相同的子數(shù)組，所以它們不穩(wěn)定。

示例 3：

輸入：zero = 3, one = 3, limit = 2

輸出：14

解釋：

所有穩(wěn)定的二進(jìn)制數(shù)組包括 [0,0,1,0,1,1] ，[0,0,1,1,0,1] ，[0,1,0,0,1,1]
，[0,1,0,1,0,1] ，[0,1,0,1,1,0] ，[0,1,1,0,0,1] ，[0,1,1,0,1,0]
，[1,0,0,1,0,1] ，[1,0,0,1,1,0] ，[1,0,1,0,0,1] ，[1,0,1,0,1,0]
，[1,0,1,1,0,0] ，[1,1,0,0,1,0] 和 [1,1,0,1,0,0] 。

提示：

1 <= zero, one, limit <= 200

題解：
方法：動(dòng)態(tài)規(guī)劃
????????

class Solution {public int numberOfStableArrays(int zero, int one, int limit) {final int mod = (int) 1e9 + 7;long[][][] f = new long[zero + 1][one + 1][2];for (int i = 1; i <= Math.min(zero, limit); ++i) {f[i][0][0] = 1;}for (int j = 1; j <= Math.min(one, limit); ++j) {f[0][j][1] = 1;}for (int i = 1; i <= zero; ++i) {for (int j = 1; j <= one; ++j) {long x = i - limit - 1 < 0 ? 0 : f[i - limit - 1][j][1];long y = j - limit - 1 < 0 ? 0 : f[i][j - limit - 1][0];f[i][j][0] = (f[i - 1][j][0] + f[i - 1][j][1] - x + mod) % mod;f[i][j][1] = (f[i][j - 1][0] + f[i][j - 1][1] - y + mod) % mod;}}return (int) ((f[zero][one][0] + f[zero][one][1]) % mod);}
}

---

7.找出所有穩(wěn)定的二進(jìn)制數(shù)組 II

題目鏈接：3130. 找出所有穩(wěn)定的二進(jìn)制數(shù)組 II

給你 3 個(gè)正整數(shù) zero ，one 和 limit 。

一個(gè)
二進(jìn)制數(shù)組
arr 如果滿足以下條件，那么我們稱它是 穩(wěn)定的 ：

0 在 arr 中出現(xiàn)次數(shù) 恰好 為 zero 。
1 在 arr 中出現(xiàn)次數(shù) 恰好 為 one 。
arr 中每個(gè)長(zhǎng)度超過(guò) limit 的
子數(shù)組
都 同時(shí) 包含 0 和 1 。
請(qǐng)你返回 穩(wěn)定 二進(jìn)制數(shù)組的 總 數(shù)目。

由于答案可能很大，將它對(duì) 109 + 7 取余 后返回。

示例 1：

輸入：zero = 1, one = 1, limit = 2

輸出：2

解釋：

兩個(gè)穩(wěn)定的二進(jìn)制數(shù)組為 [1,0] 和 [0,1] ，兩個(gè)數(shù)組都有一個(gè) 0 和一個(gè) 1 ，且沒(méi)有子數(shù)組長(zhǎng)度大于 2 。

示例 2：

輸入：zero = 1, one = 2, limit = 1

輸出：1

解釋：

唯一穩(wěn)定的二進(jìn)制數(shù)組是 [1,0,1] 。

二進(jìn)制數(shù)組 [1,1,0] 和 [0,1,1] 都有長(zhǎng)度為 2 且元素全都相同的子數(shù)組，所以它們不穩(wěn)定。

示例 3：

輸入：zero = 3, one = 3, limit = 2

輸出：14

解釋：

所有穩(wěn)定的二進(jìn)制數(shù)組包括 [0,0,1,0,1,1] ，[0,0,1,1,0,1] ，[0,1,0,0,1,1]
，[0,1,0,1,0,1] ，[0,1,0,1,1,0] ，[0,1,1,0,0,1] ，[0,1,1,0,1,0]
，[1,0,0,1,0,1] ，[1,0,0,1,1,0] ，[1,0,1,0,0,1] ，[1,0,1,0,1,0]
，[1,0,1,1,0,0] ，[1,1,0,0,1,0] 和 [1,1,0,1,0,0] 。

提示：

1 <= zero, one, limit <= 1000

題解：
方法：遞推
????????

class Solution {public int numberOfStableArrays(int zero, int one, int limit) {final int MOD = 1_000_000_007;int[][][] f = new int[zero + 1][one + 1][2];for (int i = 1; i <= Math.min(limit, zero); i++) {f[i][0][0] = 1;}for (int j = 1; j <= Math.min(limit, one); j++) {f[0][j][1] = 1;}for (int i = 1; i <= zero; i++) {for (int j = 1; j <= one; j++) {// + MOD 保證答案非負(fù)f[i][j][0] = (int) (((long) f[i - 1][j][0] + f[i - 1][j][1] + (i > limit ? MOD - f[i - limit - 1][j][1] : 0)) % MOD);f[i][j][1] = (int) (((long) f[i][j - 1][0] + f[i][j - 1][1] + (j > limit ? MOD - f[i][j - limit - 1][0] : 0)) % MOD);}}return (f[zero][one][0] + f[zero][one][1]) % MOD;}
}

---

8.找出與數(shù)組相加的整數(shù) I

題目鏈接：3131. 找出與數(shù)組相加的整數(shù) I

給你兩個(gè)長(zhǎng)度相等的數(shù)組 nums1 和 nums2。

數(shù)組 nums1 中的每個(gè)元素都與變量 x 所表示的整數(shù)相加。如果 x 為負(fù)數(shù)，則表現(xiàn)為元素值的減少。

在與 x 相加后，nums1 和 nums2 相等 。當(dāng)兩個(gè)數(shù)組中包含相同的整數(shù)，并且這些整數(shù)出現(xiàn)的頻次相同時(shí)，兩個(gè)數(shù)組 相等 。

返回整數(shù) x 。

示例 1:

輸入：nums1 = [2,6,4], nums2 = [9,7,5]

輸出：3

解釋：

與 3 相加后，nums1 和 nums2 相等。

示例 2:

輸入：nums1 = [10], nums2 = [5]

輸出：-5

解釋：

與 -5 相加后，nums1 和 nums2 相等。

示例 3:

輸入：nums1 = [1,1,1,1], nums2 = [1,1,1,1]

輸出：0

解釋：

與 0 相加后，nums1 和 nums2 相等。

提示：

1 <= nums1.length == nums2.length <= 100

0 <= nums1[i], nums2[i] <= 1000

測(cè)試用例以這樣的方式生成：存在一個(gè)整數(shù) x，使得 nums1 中的每個(gè)元素都與 x 相加后，nums1 與 nums2 相等。

題解：
方法：數(shù)學(xué)
????????

class Solution {public int addedInteger(int[] nums1, int[] nums2) {return min(nums2) - min(nums1);}private int min(int[] nums) {int res = Integer.MAX_VALUE;for (int x : nums) {res = Math.min(res, x);}return res;}
}

---

9.找出與數(shù)組相加的整數(shù) II

題目鏈接：3132. 找出與數(shù)組相加的整數(shù) II

給你兩個(gè)整數(shù)數(shù)組 nums1 和 nums2。

從 nums1 中移除兩個(gè)元素，并且所有其他元素都與變量 x 所表示的整數(shù)相加。如果 x 為負(fù)數(shù)，則表現(xiàn)為元素值的減少。

執(zhí)行上述操作后，nums1 和 nums2 相等 。當(dāng)兩個(gè)數(shù)組中包含相同的整數(shù)，并且這些整數(shù)出現(xiàn)的頻次相同時(shí)，兩個(gè)數(shù)組 相等 。

返回能夠?qū)崿F(xiàn)數(shù)組相等的 最小 整數(shù) x 。

示例 1:

輸入：nums1 = [4,20,16,12,8], nums2 = [14,18,10]

輸出：-2

解釋：

移除 nums1 中下標(biāo)為 [0,4] 的兩個(gè)元素，并且每個(gè)元素與 -2 相加后，nums1 變?yōu)?[18,14,10] ，與 nums2
相等。

示例 2:

輸入：nums1 = [3,5,5,3], nums2 = [7,7]

輸出：2

解釋：

移除 nums1 中下標(biāo)為 [0,3] 的兩個(gè)元素，并且每個(gè)元素與 2 相加后，nums1 變?yōu)?[7,7] ，與 nums2 相等。

提示：

3 <= nums1.length <= 200

nums2.length == nums1.length - 2

0 <= nums1[i], nums2[i] <= 1000

測(cè)試用例以這樣的方式生成：存在一個(gè)整數(shù) x，nums1 中的每個(gè)元素都與 x 相加后，再移除兩個(gè)元素，nums1 可以與 nums2 相等。

題解：
方法：O(nlogn) 排序+判斷子序列
????????

class Solution {public int minimumAddedInteger(int[] nums1, int[] nums2) {Arrays.sort(nums1);Arrays.sort(nums2);// 枚舉保留 nums1[2] 或者 nums1[1] 或者 nums1[0]// 倒著枚舉是因?yàn)?nums1[i] 越大答案越小，第一個(gè)滿足的就是答案for (int i = 2; i > 0; i--) {int x = nums2[0] - nums1[i];// 在 {nums1[i] + x} 中找子序列 nums2int j = 0;for (int k = i; k < nums1.length; k++) {if (nums2[j] == nums1[k] + x && ++j == nums2.length) {// nums2 是 {nums1[i] + x} 的子序列return x;}}}// 題目保證答案一定存在return nums2[0] - nums1[0];}
}

---

10.找到 Alice 和 Bob 可以相遇的建筑

題目鏈接：2940. 找到 Alice 和 Bob 可以相遇的建筑

給你一個(gè)下標(biāo)從 0 開始的正整數(shù)數(shù)組 heights ，其中 heights[i] 表示第 i 棟建筑的高度。

如果一個(gè)人在建筑 i ，且存在 i < j 的建筑 j 滿足 heights[i] < heights[j] ，那么這個(gè)人可以移動(dòng)到建筑 j 。

給你另外一個(gè)數(shù)組 queries ，其中 queries[i] = [ai, bi] 。第 i 個(gè)查詢中，Alice 在建筑 ai ，Bob 在建筑 bi 。

請(qǐng)你能返回一個(gè)數(shù)組 ans ，其中 ans[i] 是第 i 個(gè)查詢中，Alice 和 Bob 可以相遇的 最左邊的建筑 。如果對(duì)于查詢 i ，Alice 和 Bob 不能相遇，令 ans[i] 為 -1 。

示例 1：

輸入：heights = [6,4,8,5,2,7], queries = [[0,1],[0,3],[2,4],[3,4],[2,2]]

輸出：[2,5,-1,5,2]

解釋：第一個(gè)查詢中，Alice 和 Bob 可以移動(dòng)到建筑 2 ，因?yàn)?heights[0] < heights[2] 且
heights[1] < heights[2] 。

第二個(gè)查詢中，Alice 和 Bob 可以移動(dòng)到建筑 5 ，因?yàn)?heights[0] < heights[5] 且 heights[3]
< heights[5] 。

第三個(gè)查詢中，Alice 無(wú)法與 Bob 相遇，因?yàn)?Alice 不能移動(dòng)到任何其他建筑。

第四個(gè)查詢中，Alice 和 Bob 可以移動(dòng)到建筑 5 ，因?yàn)?heights[3] < heights[5] 且 heights[4]
< heights[5] 。

第五個(gè)查詢中，Alice 和 Bob 已經(jīng)在同一棟建筑中。

對(duì)于 ans[i] != -1 ，ans[i] 是 Alice 和 Bob 可以相遇的建筑中最左邊建筑的下標(biāo)。

對(duì)于 ans[i] == -1 ，不存在 Alice 和 Bob 可以相遇的建筑。

示例 2：

輸入：heights = [5,3,8,2,6,1,4,6], queries =
[[0,7],[3,5],[5,2],[3,0],[1,6]]

輸出：[7,6,-1,4,6]

解釋：第一個(gè)查詢中，Alice 可以直接移動(dòng)到 Bob 的建筑，因?yàn)?heights[0] < heights[7] 。

第二個(gè)查詢中，Alice 和 Bob 可以移動(dòng)到建筑 6 ，因?yàn)?heights[3] < heights[6] 且 heights[5]
< heights[6] 。

第三個(gè)查詢中，Alice 無(wú)法與 Bob 相遇，因?yàn)?Bob 不能移動(dòng)到任何其他建筑。

第四個(gè)查詢中，Alice 和 Bob 可以移動(dòng)到建筑 4 ，因?yàn)?heights[3] < heights[4] 且 heights[0]
< heights[4] 。

第五個(gè)查詢中，Alice 可以直接移動(dòng)到 Bob 的建筑，因?yàn)?heights[1] < heights[6] 。

對(duì)于 ans[i] != -1 ，ans[i] 是 Alice 和 Bob 可以相遇的建筑中最左邊建筑的下標(biāo)。

對(duì)于 ans[i] == -1 ，不存在 Alice 和 Bob 可以相遇的建筑。

提示：

1 <= heights.length <= 5 * 104

1 <= heights[i] <= 109

1 <= queries.length <= 5 * 104

queries[i] = [ai, bi]

0 <= ai, bi <= heights.length - 1

題解：
方法1：離線+最小堆
????????

class Solution {public int[] leftmostBuildingQueries(int[] heights, int[][] queries) {int[] ans = new int[queries.length];Arrays.fill(ans, -1);List<int[]>[] qs = new ArrayList[heights.length];Arrays.setAll(qs, i -> new ArrayList<>());for (int i = 0; i < queries.length; i++) {int a = queries[i][0];int b = queries[i][1];if (a > b) {int tmp = a;a = b;b = tmp; // 保證 a <= b}if (a == b || heights[a] < heights[b]) {ans[i] = b; // a 直接跳到 b} else {qs[b].add(new int[]{heights[a], i}); // 離線詢問(wèn)}}PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);for (int i = 0; i < heights.length; i++) {while (!pq.isEmpty() && pq.peek()[0] < heights[i]) {// 堆頂?shù)?heights[a] 可以跳到 heights[i]ans[pq.poll()[1]] = i;}for (int[] q : qs[i]) {pq.offer(q); // 后面再回答}}return ans;}
}

方法2：離線+單調(diào)棧二分
????????

class Solution {public int[] leftmostBuildingQueries(int[] heights, int[][] queries) {int n = heights.length;int[] ans = new int[queries.length];List<int[]>[] qs = new ArrayList[n];Arrays.setAll(qs, i -> new ArrayList<>());for (int i = 0; i < queries.length; i++) {int a = queries[i][0];int b = queries[i][1];if (a > b) {int tmp = a;a = b;b = tmp; // 保證 a <= b}if (a == b || heights[a] < heights[b]) {ans[i] = b; // a 直接跳到 b} else {qs[b].add(new int[]{heights[a], i}); // 離線詢問(wèn)}}int[] st = new int[n];int top = 0;for (int i = n - 1; i >= 0; i--) {for (int[] q : qs[i]) {ans[q[1]] = binarySearch(heights, st, top, q[0]);}while (top > 0 && heights[i] >= heights[st[top - 1]]) {top--;}st[top++] = i;}return ans;}// 返回 st 中最后一個(gè) > x 的高度的下標(biāo)// 如果不存在，返回 -1// https://www.bilibili.com/video/BV1AP41137w7/private int binarySearch(int[] heights, int[] st, int right, int x) {int left = -1; // 開區(qū)間 (left, right)while (left + 1 < right) { // 開區(qū)間不為空int mid = (left + right) >>> 1;if (heights[st[mid]] > x) {left = mid; // 范圍縮小到 (mid, right)} else {right = mid; // 范圍縮小到 (left, mid)}}return left < 0 ? -1 : st[left];}
}

方法3：在線+線段樹二分
????????

class Solution {public int[] leftmostBuildingQueries(int[] heights, int[][] queries) {int n = heights.length;mx = new int[2 << (Integer.SIZE - Integer.numberOfLeadingZeros(n))];build(1, 0, n - 1, heights);int[] ans = new int[queries.length];for (int i = 0; i < queries.length; i++) {int a = queries[i][0];int b = queries[i][1];if (a > b) {int tmp = a;a = b;b = tmp; // 保證 a <= b}if (a == b || heights[a] < heights[b]) {ans[i] = b; // a 直接跳到 b} else {// 線段樹二分，找 [b+1,n-1] 中的第一個(gè) > heights[a] 的位置ans[i] = query(1, 0, n - 1, b + 1, heights[a]);}}return ans;}private int[] mx;// 用 heights 初始化線段樹，維護(hù)區(qū)間最大值private void build(int o, int l, int r, int[] heights) {if (l == r) {mx[o] = heights[l];return;}int m = (l + r) / 2;build(o * 2, l, m, heights);build(o * 2 + 1, m + 1, r, heights);mx[o] = Math.max(mx[o * 2], mx[o * 2 + 1]);}// 返回 [L,n-1] 中第一個(gè) > v 的值的下標(biāo)// 如果不存在，返回 -1private int query(int o, int l, int r, int L, int v) {if (mx[o] <= v) { // 區(qū)間最大值 <= vreturn -1; // 沒(méi)有 > v 的數(shù)}if (l == r) { // 找到了return l;}int m = (l + r) / 2;if (L <= m) {int pos = query(o * 2, l, m, L, v); // 遞歸左子樹if (pos >= 0) { // 找到了return pos;}}return query(o * 2 + 1, m + 1, r, L, v); // 遞歸右子樹}
}

---

11.不相交的線

題目鏈接：1035. 不相交的線

在兩條獨(dú)立的水平線上按給定的順序?qū)懴?nums1 和 nums2 中的整數(shù)。

現(xiàn)在，可以繪制一些連接兩個(gè)數(shù)字 nums1[i] 和 nums2[j] 的直線，這些直線需要同時(shí)滿足：

nums1[i] == nums2[j]
且繪制的直線不與任何其他連線（非水平線）相交。
請(qǐng)注意，連線即使在端點(diǎn)也不能相交：每個(gè)數(shù)字只能屬于一條連線。

以這種方法繪制線條，并返回可以繪制的最大連線數(shù)。

示例 1：

輸入：nums1 = [1,4,2], nums2 = [1,2,4]

輸出：2

解釋：可以畫出兩條不交叉的線，如上圖所示。

但無(wú)法畫出第三條不相交的直線，因?yàn)閺?nums1[1]=4 到 nums2[2]=4 的直線將與從 nums1[2]=2 到
nums2[1]=2 的直線相交。

示例 2：

輸入：nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]

輸出：3

示例 3：

輸入：nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]

輸出：2

提示：

1 <= nums1.length, nums2.length <= 500

1 <= nums1[i], nums2[j] <= 2000

題解：
方法：動(dòng)態(tài)規(guī)劃
????????

class Solution {public int maxUncrossedLines(int[] nums1, int[] nums2) {int m = nums1.length, n = nums2.length;int[][] f = new int[m + 1][n + 1];for (int i = 1; i <= m; ++i) {for (int j = 1; j <= n; ++j) {if (nums1[i - 1] == nums2[j - 1]) {f[i][j] = f[i - 1][j - 1] + 1;} else {f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);}}}return f[m][n];}
}

下接：【題解】—— LeetCode一周小結(jié)33

---