每日算法-250411

这是我今天的 LeetCode 刷题记录和心得，主要涉及了二分查找的应用。

3143. 正方形中的最多点数

题目简述:

思路

本题的核心思路是 二分查找。

解题过程

为什么可以二分？
我们可以对正方形的半边长 len 进行二分。当正方形的半边长 len 越大时，可能包含的点越多，但也越有可能包含具有相同标签的点。反之，len 越小，包含的点越少，标签冲突的可能性也越小。包含点数的多少以及是否合法（无重复标签）相对于 len 的增长，具有一定的单调性（或者说，存在一个最大的 len 使得正方形合法），这满足二分查找的条件。

二分什么？
我们需要二分查找满足条件的最大正方形半边长 len。查找范围可以从 0 到所有点坐标绝对值的最大值。

如何检查（check 函数）？
check(len) 函数用于判断以半边长 len 构成的正方形是否“合法”。
合法性判断包含两步：

遍历所有点，检查其坐标 (x, y) 是否满足 abs(x) <= len 且 abs(y) <= len。
对于落在正方形内的点，使用一个哈希表（或大小为 26 的数组 hash）记录出现的标签。如果在添加一个点的标签时，发现该标签已经存在于哈希表中（即 hash[s[i] - 'a'] >= 1），则说明存在重复标签，该 len 值对应的正方形不合法，check 返回 false。
如果遍历完所有点都没有发现重复标签，则该 len 合法，check 返回 true。

指针如何移动？
在二分查找过程中：

计算中间值 mid。
调用 check(mid)：
- 如果 check(mid) 返回 true，说明半边长为 mid 的正方形是合法的。这表示我们可能可以找到一个更大的合法正方形，因此我们尝试增大边长，将搜索范围的左边界更新为 left = mid + 1。同时，因为这是一个合法的 len，我们需要记录下此时正方形内的点数（可以在 check 函数内部完成，或者在 check 返回 true 时更新全局变量 ret）。
- 如果 check(mid) 返回 false，说明半边长为 mid 的正方形不合法（有标签冲突），意味着当前的 len 太大了，我们需要缩短边长，将搜索范围的右边界更新为 right = mid - 1。

最终结果:
二分查找结束后，变量 ret 中存储的就是满足条件的最大合法正方形所包含的点数。

复杂度

时间复杂度: $\log M)$ ，其中 $N$ 是点的数量， $M$ 是坐标的最大绝对值（二分查找的上界）。check 函数需要 $O (N)$ 时间，二分查找进行 $\log M$ 次。
空间复杂度: $O (C)$ 或 $O (N)$ 。 $O (C)$ 是指存储标签计数的哈希表/数组所需空间（ $C = 26$ ）。如果考虑最坏情况下所有点标签不同且都在某个正方形内，可能认为是 $O (N)$ ，但通常关注辅助空间，所以 $O (C)$ 更精确描述 check 函数的额外空间。

Code

class Solution {private int ret;public int maxPointsInsideSquare(int[][] points, String ss) {char[] s = ss.toCharArray();int left = 0;int right = 0;for (int[] point : points) {right = Math.max(right, Math.max(Math.abs(point[0]), Math.abs(point[1])));}while (left <= right) {int mid = left + (right - left) / 2;if (check(points, s, mid)) {left = mid + 1;} else {right = mid - 1;}}return ret;}private boolean check(int[][] points, char[] s, int len) {int[] hash = new int[26];int tmp = 0; // 合法正方形里点的个数// 1.是不是合法的for (int i = 0; i < points.length; i++) {if (Math.abs(points[i][0]) <= len && Math.abs(points[i][1]) <= len) {if (hash[s[i] - 'a'] >= 1) {// 标签已经存在return false;}hash[s[i] - 'a']++;tmp++;}}// 2.更新数目ret = tmp;return true;}
}

69. x 的平方根

题目简述:

思路

采用 二分查找。

解题过程

为什么可以二分？
我们要找的是一个整数 ans，使得 ans * ans <= x 并且 (ans + 1) * (ans + 1) > x。考虑函数 f(y) = y * y，这是一个在非负整数域上的单调递增函数。我们需要找到满足 y*y <= x 的最大整数 y。这种在单调序列（或具有单调性质的函数）上查找满足特定条件的边界值的问题，非常适合使用二分查找。

二分什么？
二分查找的目标值，即可能的平方根 mid。查找范围是 [0, x]（或者可以优化为 [0, x/2 + 1] 或像代码中的 [1, x/2]，需要处理 x=0, 1 的边界情况，原代码 right = x/2 对于 x=0, 1 需要注意，但最终逻辑能处理）。

指针如何移动？
在二分查找 [left, right] 区间内：

计算中间值 mid。为了防止 mid * mid 溢出 int，使用 long 类型进行计算和比较。
比较 (long)mid * mid 与 x：
- 如果 mid * mid < x：说明 mid 太小了，它可能是平方根的一部分，但我们应该尝试更大的值。真正的整数平方根应该在 mid 的右侧（或就是 mid 本身）。所以，更新搜索区间的左边界 left = mid + 1。
- 如果 mid * mid >= x：说明 mid 可能等于 x 的平方根，或者比它大。我们需要尝试更小的值（或者 mid 就是边界）。所以，更新搜索区间的右边界 right = mid - 1。

返回什么？
循环终止条件是 left > right。根据二分查找的实现方式，最终 left 指针将指向第一个满足 mid * mid > x 的 mid（或者说，left 是满足 (left-1)*(left-1) <= x 的最小 left）。
分析代码中的返回逻辑 return left * left == x ? left : left - 1;：

循环结束后，left 的值是第一个使得 mid*mid >= x 评估为 true 时的 mid 值加 1（或者是 mid 本身，如果 mid*mid == x 且之后 right 被设为 mid-1 导致循环结束）。
如果 left * left == x，说明 left 正好是 x 的精确整数平方根，直接返回 left。
如果 left * left != x (根据循环条件，此时必然是 left * left > x)，这意味着 left 已经超过了目标平方根，而 left - 1 是最后一个满足 (left - 1) * (left - 1) <= x 的整数。因此，返回 left - 1 作为 x 的平方根的整数部分。

复杂度

时间复杂度: $O(\log x)$ ，二分查找的范围是 x（或 x/2），每次迭代区间减半。
空间复杂度: $O (1)$ ，只需要常数级别的额外空间。

Code

class Solution {public int mySqrt(int x) {int left = 1, right = x / 2;while (left <= right) {long mid = left + (right - left) / 2;if (mid * mid < x) {left = (int)mid + 1;} else {right = (int)mid - 1;}}return left * left == x ? left : left - 1;}
}

2300. 咒语和药水的成功对数（复习）

题目简述:

这是第二次写这道题，已经可以说是完全掌握了，就不再多说了，详细题解请看每日算法-250407。

核心思路回顾:
为了高效计算每个 spell 能成功组合的 potion 数量，我们可以：

对 potions 数组进行排序。
对于每个 spell = spells[i]，我们需要找到 potions 中满足 spell * potion >= success 的药水数量。由于 potions 已排序，spell * potion 的值也相对于 potion 是单调递增的（因为 spell > 0）。
因此，我们可以使用 二分查找 在排序后的 potions 数组中找到 第一个 满足 potion >= success / spell （注意整数除法和精度问题，最好是比较乘积 (long)spell * potions[mid] >= success）的药水的索引 idx。
所有从 idx 到数组末尾 m-1 的药水都将满足条件。所以，对于 spells[i]，成功的组合数量是 m - idx。

代码 (复习)

class Solution {public int[] successfulPairs(int[] spells, int[] potions, long success) {Arrays.sort(potions);int n = spells.length, m = potions.length;for (int i = 0; i < spells.length; i++) {spells[i] = m - check(potions, spells[i], success);}return spells;}private int check(int[] arr, int spell, long k) {int left = 0, right = arr.length - 1;while (left <= right) {int mid = left + (right - left) / 2;long x = (long)arr[mid] * (long)spell;if (x < k) {left = mid + 1;} else {right = mid - 1;}}return left;}
}