网站广告推广平台,搜索引擎谷歌,小程序模板大全,常见的网页布局结构有哪些#x1f31f;欢迎来到 我的博客 —— 探索技术的无限可能#xff01; #x1f31f;博客的简介#xff08;文章目录#xff09; 【题解】—— 每日一道题目栏 上接#xff1a;【题解】—— LeetCode一周小结31
5.不含连续1的非负整数
题目链接#xff1a;600. 不含连续… 欢迎来到 我的博客 —— 探索技术的无限可能 博客的简介文章目录 【题解】—— 每日一道题目栏 上接【题解】—— LeetCode一周小结31
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); // 填 0if (pre 0 up 1) { // 可以填 1res 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
题目链接3130. 找出所有稳定的二进制数组 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 测试用例以这样的方式生成存在一个整数 xnums1 中的每个元素都与 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} 中找子序列 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 可以相遇的建筑
给你一个下标从 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);Listint[][] 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}); // 离线询问}}PriorityQueueint[] 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];Listint[][] 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 {// 线段树二分找 [b1,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 的值的下标// 如果不存在返回 -1private int query(int o, int l, int r, int L, int v) {if (mx[o] v) { // 区间最大值 vreturn -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];}
}下接【题解】—— LeetCode一周小结33
