🌟欢迎来到 我的博客 —— 探索技术的无限可能！
5.不含连续1的非负整数
题目链接：600. 不含连续1的非负整数
给定一个正整数 n ，请你统计在 [0, n] 范围的非负整数中，有多少个整数的二进制表示中不存在 连续的 1 。
示例 1:
输入: n = 5
输出: 5
解释:
下面列出范围在 [0, 5] 的非负整数与其对应的二进制表示：
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
其中，只有整数 3 违反规则（有两个连续的 1 ），其他 5 个满足规则。
示例 2:
输入: n = 1
输出: 2
示例 3:
输入: n = 2
输出: 3
提示:
1 <= n <= 109
题解：
方法：数位 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 表示没有计算过
}
return dfs(m - 1, 0, true, n, memo); // 从高位到低位
}
// pre 表示前一个比特位填的数
private int dfs(int i, int pre, boolean isLimit, int n, int[][] memo) {
if (i < 0) {
return 1;
}
if (!isLimit && memo[i][pre] >= 0) { // 之前计算过
return memo[i][pre];
}
int up = isLimit ? n >> i & 1 : 1;
int res = dfs(i - 1, 0, isLimit && up == 0, n, memo); // 填 0
if (pre == 0 && up == 1) { // 可以填 1
res += dfs(i - 1, 1, isLimit, n, memo); // 填 1
}
if (!isLimit) {
memo[i][pre] = res; // 记忆化
}
return res;
}
}
6.找出所有稳定的二进制数组 I
题目链接：3129. 找出所有稳定的二进制数组 I
给你 3 个正整数 zero ，one 和 limit 。
一个
二进制数组
arr 如果满足以下条件，那么我们称它是 稳定的 ：
0 在 arr 中出现次数 恰好 为 zero 。
1 在 arr 中出现次数 恰好 为 one 。
arr 中每个长度超过 limit 的
子数组
都 同时 包含 0 和 1 。
请你返回 稳定 二进制数组的 总 数目。
由于答案可能很大，将它对 109 + 7 取余 后返回。
示例 1：
输入：zero = 1, one = 1, limit = 2
输出：2
解释：
两个稳定的二进制数组为 [1,0] 和 [0,1] ，两个数组都有一个 0 和一个 1 ，且没有子数组长度大于 2 。
示例 2：
输入：zero = 1, one = 2, limit = 1
输出：1
解释：
唯一稳定的二进制数组是 [1,0,1] 。
二进制数组 [1,1,0] 和 [0,1,1] 都有长度为 2 且元素全都相同的子数组，所以它们不稳定。
示例 3：
输入：zero = 3, one = 3, limit = 2
输出：14
解释：
所有稳定的二进制数组包括 [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
题解：
方法：动态规划
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.找出所有稳定的二进制数组 II
给你 3 个正整数 zero ，one 和 limit 。
一个
二进制数组
arr 如果满足以下条件，那么我们称它是 稳定的 ：
0 在 arr 中出现次数 恰好 为 zero 。
1 在 arr 中出现次数 恰好 为 one 。
arr 中每个长度超过 limit 的
子数组
都 同时 包含 0 和 1 。
请你返回 稳定 二进制数组的 总 数目。
由于答案可能很大，将它对 109 + 7 取余 后返回。
示例 1：
输入：zero = 1, one = 1, limit = 2
输出：2
解释：
两个稳定的二进制数组为 [1,0] 和 [0,1] ，两个数组都有一个 0 和一个 1 ，且没有子数组长度大于 2 。
示例 2：
输入：zero = 1, one = 2, limit = 1
输出：1
解释：
唯一稳定的二进制数组是 [1,0,1] 。
二进制数组 [1,1,0] 和 [0,1,1] 都有长度为 2 且元素全都相同的子数组，所以它们不稳定。
示例 3：
输入：zero = 3, one = 3, limit = 2
输出：14
解释：
所有稳定的二进制数组包括 [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[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.找出与数组相加的整数 I
题目链接：3131. 找出与数组相加的整数 I
给你两个长度相等的数组 nums1 和 nums2。
数组 nums1 中的每个元素都与变量 x 所表示的整数相加。如果 x 为负数，则表现为元素值的减少。
在与 x 相加后，nums1 和 nums2 相等 。当两个数组中包含相同的整数，并且这些整数出现的频次相同时，两个数组 相等 。
返回整数 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
测试用例以这样的方式生成：存在一个整数 x，使得 nums1 中的每个元素都与 x 相加后，nums1 与 nums2 相等。
题解：
方法：数学
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.找出与数组相加的整数 II
题目链接：3132. 找出与数组相加的整数 II
给你两个整数数组 nums1 和 nums2。
从 nums1 中移除两个元素，并且所有其他元素都与变量 x 所表示的整数相加。如果 x 为负数，则表现为元素值的减少。
执行上述操作后，nums1 和 nums2 相等 。当两个数组中包含相同的整数，并且这些整数出现的频次相同时，两个数组 相等 。
返回能够实现数组相等的 最小 整数 x 。
示例 1:
输入：nums1 = [4,20,16,12,8], nums2 = [14,18,10]
输出：-2
解释：
移除 nums1 中下标为 [0,4] 的两个元素，并且每个元素与 -2 相加后，nums1 变为 [18,14,10] ，与 nums2
相等。
示例 2:
输入：nums1 = [3,5,5,3], nums2 = [7,7]
输出：2
解释：
移除 nums1 中下标为 [0,3] 的两个元素，并且每个元素与 2 相加后，nums1 变为 [7,7] ，与 nums2 相等。
提示：
3 <= nums1.length <= 200
nums2.length == nums1.length - 2
0 <= nums1[i], nums2[i] <= 1000
测试用例以这样的方式生成：存在一个整数 x，nums1 中的每个元素都与 x 相加后，再移除两个元素，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]
// 倒着枚举是因为 nums1[i] 越大答案越小，第一个满足的就是答案
for (int i = 2; i > 0; i--) {
int x = nums2[0] - nums1[i];
// 在 {nums1[i] + x} 中找子序列 nums2
int 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 可以相遇的建筑
给你一个下标从 0 开始的正整数数组 heights ，其中 heights[i] 表示第 i 栋建筑的高度。
如果一个人在建筑 i ，且存在 i < j 的建筑 j 满足 heights[i] < heights[j] ，那么这个人可以移动到建筑 j 。
给你另外一个数组 queries ，其中 queries[i] = [ai, bi] 。第 i 个查询中，Alice 在建筑 ai ，Bob 在建筑 bi 。
请你能返回一个数组 ans ，其中 ans[i] 是第 i 个查询中，Alice 和 Bob 可以相遇的 最左边的建筑 。如果对于查询 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]
解释：第一个查询中，Alice 和 Bob 可以移动到建筑 2 ，因为 heights[0] < heights[2] 且
heights[1] < heights[2] 。第二个查询中，Alice 和 Bob 可以移动到建筑 5 ，因为 heights[0] < heights[5] 且 heights[3]
< heights[5] 。第三个查询中，Alice 无法与 Bob 相遇，因为 Alice 不能移动到任何其他建筑。
第四个查询中，Alice 和 Bob 可以移动到建筑 5 ，因为 heights[3] < heights[5] 且 heights[4]
< heights[5] 。第五个查询中，Alice 和 Bob 已经在同一栋建筑中。
对于 ans[i] != -1 ，ans[i] 是 Alice 和 Bob 可以相遇的建筑中最左边建筑的下标。
对于 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]
解释：第一个查询中，Alice 可以直接移动到 Bob 的建筑，因为 heights[0] < heights[7] 。
第二个查询中，Alice 和 Bob 可以移动到建筑 6 ，因为 heights[3] < heights[6] 且 heights[5]
< heights[6] 。第三个查询中，Alice 无法与 Bob 相遇，因为 Bob 不能移动到任何其他建筑。
第四个查询中，Alice 和 Bob 可以移动到建筑 4 ，因为 heights[3] < heights[4] 且 heights[0]
< heights[4] 。第五个查询中，Alice 可以直接移动到 Bob 的建筑，因为 heights[1] < heights[6] 。
对于 ans[i] != -1 ，ans[i] 是 Alice 和 Bob 可以相遇的建筑中最左边建筑的下标。
对于 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}); // 离线询问
}
}
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]) {
// 堆顶的 heights[a] 可以跳到 heights[i]
ans[pq.poll()[1]] = i;
}
for (int[] q : qs[i]) {
pq.offer(q); // 后面再回答
}
}
return ans;
}
}
方法2：离线+单调栈二分
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}); // 离线询问
}
}
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 中最后一个 > x 的高度的下标
// 如果不存在，返回 -1
// https://www.bilibili.com/video/BV1AP41137w7/
private int binarySearch(int[] heights, int[] st, int right, int x) {
int left = -1; // 开区间 (left, right)
while (left + 1 < right) { // 开区间不为空
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] 中的第一个 > heights[a] 的位置
ans[i] = query(1, 0, n - 1, b + 1, heights[a]);
}
}
return ans;
}
private int[] mx;
// 用 heights 初始化线段树，维护区间最大值
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] 中第一个 > v 的值的下标
// 如果不存在，返回 -1
private int query(int o, int l, int r, int L, int v) {
if (mx[o] <= v) { // 区间最大值 <= v
return -1; // 没有 > v 的数
}
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. 不相交的线
在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。
现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足：
nums1[i] == nums2[j]
且绘制的直线不与任何其他连线（非水平线）相交。
请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。
以这种方法绘制线条，并返回可以绘制的最大连线数。
示例 1：
输入：nums1 = [1,4,2], nums2 = [1,2,4]
输出：2
解释：可以画出两条不交叉的线，如上图所示。
但无法画出第三条不相交的直线，因为从 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
题解：
方法：动态规划
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];
}
}