🌟欢迎来到 我的博客 —— 探索技术的无限可能！
题目链接：2009. 使数组连续的最少操作数
给你一个整数数组 nums 。每一次操作中，你可以将 nums 中 任意 一个元素替换成 任意 整数。
如果 nums 满足以下条件，那么它是 连续的 ：
- nums 中所有元素都是 互不相同 的。
- nums 中 最大 元素与 最小 元素的差等于 nums.length - 1 。
比方说，nums = [4, 2, 5, 3] 是 连续的 ，但是 nums = [1, 2, 3, 5, 6] 不是连续的 。
请你返回使 nums 连续 的 最少 操作次数。
示例 1：
输入：nums = [4,2,5,3]
输出：0
解释：nums 已经是连续的了。
示例 2：
输入：nums = [1,2,3,5,6]
输出：1
解释：一个可能的解是将最后一个元素变为 4 。
结果数组为 [1,2,3,5,4] ，是连续数组。
示例 3：
输入：nums = [1,10,100,1000]
输出：3
解释：一个可能的解是：
- 将第二个元素变为 2 。
- 将第三个元素变为 3 。
- 将第四个元素变为 4 。
结果数组为 [1,2,3,4] ，是连续数组。
提示：
1 <= nums.length <= 105
1 <= nums[i] <= 109
题解：
方法：排序 滑动窗口
正难则反，考虑最多保留多少个元素不变。
设 x 是修改后的连续数字的最大值，则修改后的连续数字的范围为闭区间 [x−n+1,x]，其中 nnn 是 nums 的长度。在修改前，对于已经在 [x−n+1,x] 中的数，我们无需修改。那么，x 取多少，可以让无需修改的数最多呢？
由于元素的位置不影响答案，且要求所有元素互不相同，我们可以将 nums从小到大排序，并去掉重复元素。设 a 为 nums 排序去重后的数组。把 a[i] 画在一条数轴上，本题相当于有一个长度为 n 的滑动窗口，我们需要计算窗口内最多可以包含多少个数轴上的点。
定理：只需要枚举 a[i] 作为窗口的右端点。
证明：在窗口从左向右滑动的过程中，如果窗口右端点处没有点，那么继续滑动，在滑到下一个点之前，窗口内包含的点的个数是不会增多的。
为了算出窗口内有多少个点，我们需要知道窗口包含的最左边的点在哪，设这个点的位置是 a[left]，则它必须大于等于窗口的左边界，即
a[left]≥a[i]−n+1
此时窗口内有 i−left+1个点，取其最大值，就得到了最多保留不变的元素个数。最后用 n 减去保留不变的元素个数，就得到了答案。
class Solution { public int minOperations(int[] nums) { Arrays.sort(nums); // 对数组进行排序 int n = nums.length; int m = 1; // 记录去重后数组的长度，初始值为 1 // 原地去重，将不重复的数字前移，保留第一个出现的相同数字 for (int i = 1; i < n; i++) { if (nums[i] != nums[i - 1]) { nums[m++] = nums[i]; } } int ans = 0; // 初始化结果值为 0 int left = 0; // 滑动窗口的左边界 for (int i = 0; i < m; i++) { while (nums[left] < nums[i] - n + 1) { // 确保窗口内的元素数量不小于 n left++; // 左边界向右移动，直到窗口内的元素数量满足要求 } ans = Math.max(ans, i - left + 1); // 更新结果值，取当前窗口大小的最大值 } return n - ans; // 返回需要操作的最小次数 } }
9.正整数和负整数的最大计数
题目链接：2529. 正整数和负整数的最大计数
给你一个按 非递减顺序 排列的数组 nums ，返回正整数数目和负整数数目中的最大值。
- 换句话讲，如果 nums 中正整数的数目是 pos ，而负整数的数目是 neg ，返回 pos 和 neg二者中的最大值。
注意：0 既不是正整数也不是负整数。
示例 1：
输入：nums = [-2,-1,-1,1,2,3]
输出：3
解释：共有 3 个正整数和 3 个负整数。计数得到的最大值是 3 。
示例 2：
输入：nums = [-3,-2,-1,0,0,1,2]
输出：3
解释：共有 2 个正整数和 3 个负整数。计数得到的最大值是 3 。
示例 3：
输入：nums = [5,20,66,1314]
输出：4
解释：共有 4 个正整数和 0 个负整数。计数得到的最大值是 4 。
提示：
1 <= nums.length <= 2000
-2000 <= nums[i] <= 2000
nums 按 非递减顺序 排列。
进阶：你可以设计并实现时间复杂度为 O(log(n)) 的算法解决此问题吗？
题解：
方法：遍历
遍历数组，统计负数数目 neg 和正数数目 pos。
最后返回 max(neg,pos)。
public class Solution { public int maximumCount(int[] nums) { int neg = 0; // 记录负数的个数 int pos = 0; // 记录正数的个数 for (int x : nums) { // 遍历数组中的每个元素 if (x < 0) { neg++; // 若元素小于 0，则负数个数加 1 } else if (x > 0) { pos++; // 若元素大于 0，则正数个数加 1 } } return Math.max(neg, pos); // 返回负数和正数中较大的个数 } }
方法：二分查找
public class Solution { public int maximumCount(int[] nums) { int neg = lowerBound(nums, 0); // 获取第一个大于等于0的数的位置（相当于负数的个数） // 第一个 > 0 的位置，等价于第一个 >= 1 的位置 int pos = nums.length - lowerBound(nums, 1); // 获取第一个大于等于1的数的位置（相当于正数的个数） return Math.max(neg, pos); // 返回负数和正数中较大的个数 } // 返回 nums 中第一个 >= target 的数的下标 // 如果不存在这样的数，返回 nums.length // 详见 https://www.bilibili.com/video/BV1AP41137w7/ private int lowerBound(int[] nums, int target) { // 二分范围：开区间 (left, right) int left = -1; int right = nums.length; // 开区间不为空 while (left + 1 < right) { // 循环不变量： // nums[left] < target // nums[right] >= target int mid = left + (right - left) / 2; if (nums[mid] >= target) { // 二分范围缩小至 (left, mid) right = mid; } else { // 二分范围缩小至 (mid, right) left = mid; } } // 此时 left 等于 right - 1 // 因为 nums[right - 1] < target 且 nums[right] >= target，所以答案是 right return right; } }
10.修改后的最大二进制字符串
题目链接：1702. 修改后的最大二进制字符串
给你一个二进制字符串 binary ，它仅有 0 或者 1 组成。你可以使用下面的操作任意次对它进行修改：
- 操作 1 ：如果二进制串包含子字符串 “00” ，你可以用 “10” 将其替换。
- 比方说， “00010” -> “10010”
- 操作 2 ：如果二进制串包含子字符串 “10” ，你可以用 “01” 将其替换。
- 比方说， “00010” -> “00001”
请你返回执行上述操作任意次以后能得到的 最大二进制字符串 。如果二进制字符串 x 对应的十进制数字大于二进制字符串 y 对应的十进制数字，那么我们称二进制字符串 x 大于二进制字符串 y 。
示例 1：
输入：binary = “000110”
输出：“111011”
解释：一个可行的转换为：
“000110” -> “000101”
“000101” -> “100101”
“100101” -> “110101”
“110101” -> “110011”
“110011” -> “111011”
示例 2：
输入：binary = “01”
输出：“01”
解释：“01” 没办法进行任何转换。
提示：
1 <= binary.length <= 105
binary 仅包含 ‘0’ 和 ‘1’ 。
题解：
方法：贪心
class Solution { public String maximumBinaryString(String binary) { int i = binary.indexOf('0'); // 找到第一个 '0' 的位置 if (i < 0) { // 如果没有 '0'，则直接返回原字符串 return binary; } char[] s = binary.toCharArray(); // 将字符串转换为字符数组 int cnt1 = 0; // 统计从第一个 '0' 开始到末尾的 '1' 的个数 for (i++; i < s.length; i++) { cnt1 += s[i] - '0'; // 统计 [i, n-1] 中 '1' 的个数 } // 构造最大二进制字符串 return "1".repeat(s.length - 1 - cnt1) + '0' + "1".repeat(cnt1); } }
11.互质树
题目链接：1766. 互质树
给你一个 n 个节点的树（也就是一个无环连通无向图），节点编号从 0 到 n - 1 ，且恰好有 n - 1 条边，每个节点有一个值。树的 根节点 为 0 号点。
给你一个整数数组 nums 和一个二维数组 edges 来表示这棵树。nums[i] 表示第 i 个点的值，edges[j] = [uj, vj] 表示节点 uj 和节点 vj 在树中有一条边。
当 gcd(x, y) == 1 ，我们称两个数 x 和 y 是 互质的 ，其中 gcd(x, y) 是 x 和 y 的 最大公约数 。
从节点 i 到 根 最短路径上的点都是节点 i 的祖先节点。一个节点 不是 它自己的祖先节点。
请你返回一个大小为 n 的数组 ans ，其中 ans[i]是离节点 i 最近的祖先节点且满足 nums[i] 和 nums[ans[i]] 是 互质的 ，如果不存在这样的祖先节点，ans[i] 为 -1 。
示例 1：
输入：nums = [2,3,3,2], edges = [[0,1],[1,2],[1,3]]
输出：[-1,0,0,1]
解释：上图中，每个节点的值在括号中表示。
- 节点 0 没有互质祖先。
- 节点 1 只有一个祖先节点 0 。它们的值是互质的（gcd(2,3) == 1）。
- 节点 2 有两个祖先节点，分别是节点 1 和节点 0 。节点 1 的值与它的值不是互质的（gcd(3,3) == 3）但节点 0 的值是互质的(gcd(2,3) == 1)，所以节点 0 是最近的符合要求的祖先节点。
- 节点 3 有两个祖先节点，分别是节点 1 和节点 0 。它与节点 1 互质（gcd(3,2) == 1），所以节点 1 是离它最近的符合要求的祖先节点。
示例 2：
输入：nums = [5,6,10,2,3,6,15], edges =
[[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]
输出：[-1,0,-1,0,0,0,-1]
提示：
nums.length == n
1 <= nums[i] <= 50
1 <= n <= 105
edges.length == n - 1
edges[j].length == 2
0 <= uj, vj < n
uj != vj
题解：
方法：深度优先搜索 数学 回溯 数论
DFS 中记录节点值的深度和编号，回溯写法
class Solution { private static final int MX = 51; private static final int[][] coprime = new int[MX][MX]; static { // 预处理 // coprime[i] 保存 [1, MX) 中与 i 互质的所有元素 for (int i = 1; i < MX; i++) { int k = 0; for (int j = 1; j < MX; j++) { if (gcd(i, j) == 1) { coprime[i][k++] = j; } } } } public int[] getCoprimes(int[] nums, int[][] edges) { int n = nums.length; List<Integer>[] g = new ArrayList[n]; Arrays.setAll(g, i -> new ArrayList<>()); for (int[] e : edges) { int x = e[0]; int y = e[1]; g[x].add(y); g[y].add(x); } int[] ans = new int[n]; Arrays.fill(ans, -1); int[] valDepth = new int[MX]; int[] valNodeId = new int[MX]; dfs(0, -1, 1, g, nums, ans, valDepth, valNodeId); return ans; } private void dfs(int x, int fa, int depth, List<Integer>[] g, int[] nums, int[] ans, int[] valDepth, int[] valNodeId) { // x 的节点值 int val = nums[x]; // 计算与 val 互质的祖先节点值中，节点深度最大的节点编号 int maxDepth = 0; for (int j : coprime[val]) { if (j == 0) { break; } if (valDepth[j] > maxDepth) { maxDepth = valDepth[j]; ans[x] = valNodeId[j]; } } // tmpDepth 和 tmpNodeId 用于恢复现场 int tmpDepth = valDepth[val]; int tmpNodeId = valNodeId[val]; // 保存 val 对应的节点深度和节点编号 valDepth[val] = depth; valNodeId[val] = x; // 向下递归 for (int y : g[x]) { if (y != fa) { dfs(y, x, depth + 1, g, nums, ans, valDepth, valNodeId); } } // 恢复现场 valDepth[val] = tmpDepth; valNodeId[val] = tmpNodeId; } private static int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } }
12.找到冠军 I
题目链接：2923. 找到冠军 I
一场比赛中共有 n 支队伍，按从 0 到 n - 1 编号。
给你一个下标从 0 开始、大小为 n * n 的二维布尔矩阵 grid 。对于满足 0 <= i, j <= n - 1 且 i != j 的所有 i, j ：如果 grid[i][j] == 1，那么 i 队比 j 队 强 ；否则，j 队比 i 队 强 。
在这场比赛中，如果不存在某支强于 a 队的队伍，则认为 a 队将会是 冠军 。
返回这场比赛中将会成为冠军的队伍。
示例 1：
输入：grid = [[0,1],[0,0]]
输出：0
解释：比赛中有两支队伍。
grid[0][1] == 1 表示 0 队比 1 队强。所以 0 队是冠军。
示例 2：
输入：grid = [[0,0,1],[1,0,1],[0,0,0]]
输出：1
解释：比赛中有三支队伍。
grid[1][0] == 1 表示 1 队比 0 队强。
grid[1][2] == 1 表示 1 队比 2 队强。
所以 1 队是冠军。
提示：
n == grid.length
n == grid[i].length
2 <= n <= 100
grid[i][j] 的值为 0 或 1
对于所有 i， grid[i][i] 等于 0.
对于满足 i != j 的所有 i, j ，grid[i][j] != grid[j][i] 均成立
生成的输入满足：如果 a 队比 b 队强，b 队比 c 队强，那么 a 队比 c 队强
题解：
方法：****
- 如果 grid[i][j]=1，说明 i 队比 j 队强。
- 如果 grid[i][j]=0，说明 i 队比 j 队弱。
- 没有平手。
所以 a 队要是冠军，a 队就要比其它 n−1 个队都要强。
如果 grid[i] 有 n−1 个 1，即元素和为 n−1，说明 i 队比其它 n−1 个队都要强，i 队是冠军。
也可以判断，对于这一行的所有不等于 i 的 j，都有 grid[i][j]=1。这样可以在遇到0 的时候，提前退出循环。
class Solution { public int findChampion(int[][] grid) { next: for (int i = 0; ; i++) { for (int j = 0; j < grid.length; j++) { if (j != i && grid[i][j] == 0) { continue next; } } return i; } } }
如果第 j 列的元素值都是 0，说明没有队伍可以击败 j 队，j 队是冠军。
class Solution { public int findChampion(int[][] grid) { next: for (int j = 0; ; j++) { for (int[] row : grid) { if (row[j] != 0) { continue next; } } return j; } } }
假设冠军是 ans=0，我们从 i=1 开始遍历，寻找可以击败 ans 的队伍，也就是 grid[i][ans]=1。
如果没有出现 grid[i][ans]=1，那么答案就是 ans，否则冠军可能是 i，更新 ans=i。然后从 i+1 继续向后遍历，因为 [1,i−1] 中没有比 0 强的队，更别说比 i 强了。重复上述过程，最后返回 ans。
class Solution { public int findChampion(int[][] grid) { int ans = 0; for (int i = 1; i < grid.length; i++) { if (grid[i][ans] == 1) { ans = i; } } return ans; } }
13.找到冠军 II
题目链接：2924. 找到冠军 II
一场比赛中共有 n 支队伍，按从 0 到 n - 1 编号。每支队伍也是 有向无环图（DAG） 上的一个节点。
给你一个整数 n 和一个下标从 0 开始、长度为 m 的二维整数数组 edges 表示这个有向无环图，其中 edges[i] = [ui, vi] 表示图中存在一条从 ui 队到 vi 队的有向边。
从 a 队到 b 队的有向边意味着 a 队比 b 队 强 ，也就是 b 队比 a 队 弱 。
在这场比赛中，如果不存在某支强于 a 队的队伍，则认为 a 队将会是 冠军 。
如果这场比赛存在 唯一 一个冠军，则返回将会成为冠军的队伍。否则，返回 -1 。
注意
环 是形如 a1, a2, …, an, an+1 的一个序列，且满足：节点 a1 与节点 an+1 是同一个节点；节点 a1, a2, …, an 互不相同；对于范围 [1, n] 中的每个 i ，均存在一条从节点 ai 到节点 ai+1 的有向边。
有向无环图 是不存在任何环的有向图。
示例 1：
输入：n = 3, edges = [[0,1],[1,2]]
输出：0
解释：1 队比 0 队弱。2 队比 1 队弱。所以冠军是 0 队。
示例 2：
输入：n = 4, edges = [[0,2],[1,3],[1,2]]
输出：-1
解释：2 队比 0 队和 1 队弱。3 队比 1 队弱。但是 1 队和 0 队之间不存在强弱对比。所以答案是 -1 。
提示：
1 <= n <= 100
m == edges.length
0 <= m <= n * (n - 1) / 2
edges[i].length == 2
0 <= edge[i][j] <= n - 1
edges[i][0] != edges[i][1]
生成的输入满足：如果 a 队比 b 队强，就不存在 b 队比 a 队强
生成的输入满足：如果 a 队比 b 队强，b 队比 c 队强，那么 a 队比 c 队强
题解：
class Solution { public int findChampion(int n, int[][] edges) { boolean[] isWeak = new boolean[n]; for (int[] e : edges) { isWeak[e[1]] = true; // 不是冠军 } int ans = -1; for (int i = 0; i < n; i++) { if (isWeak[i]) { continue; } if (ans != -1) { return -1; // 冠军只能有一个 } ans = i; } return ans; } }
14.设计哈希集合
题目链接：705. 设计哈希集合
不使用任何内建的哈希表库设计一个哈希集合（HashSet）。
实现 MyHashSet 类：
void add(key) 向哈希集合中插入值 key 。
bool contains(key) 返回哈希集合中是否存在这个值 key 。
void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。
示例：
输入：
[“MyHashSet”, “add”, “add”, “contains”, “contains”, “add”, “contains”,
“remove”, “contains”]
[[], [1], [2], [1], [3], [2], [2], [2], [2]]
输出：
[null, null, null, true, false, null, true, null, false]
解释：
MyHashSet myHashSet = new MyHashSet();
myHashSet.add(1); // set = [1]
myHashSet.add(2); // set = [1, 2]
myHashSet.contains(1); // 返回 True
myHashSet.contains(3); // 返回 False ，（未找到）
myHashSet.add(2); // set = [1, 2]
myHashSet.contains(2); // 返回 True
myHashSet.remove(2); // set = [1]
myHashSet.contains(2); // 返回 False ，（已移除）
提示：
0 <= key <= 106
最多调用 104 次 add、remove 和 contains
题解：
方法：数组 哈希表
class MyHashSet { private boolean[] data = new boolean[1000001]; public MyHashSet() { } public void add(int key) { data[key] = true; } public void remove(int key) { data[key] = false; } public boolean contains(int key) { return data[key]; } } /** * Your MyHashSet object will be instantiated and called as such: * MyHashSet obj = new MyHashSet(); * obj.add(key); * obj.remove(key); * boolean param_3 = obj.contains(key); */
