【题解】—— LeetCode一周小结45

🌟欢迎来到 我的博客 —— 探索技术的无限可能！

🌟博客的简介（文章目录）

---

【题解】—— 每日一道题目栏

---

上接：【题解】—— LeetCode一周小结44

4.平方数之和

题目链接：633. 平方数之和

给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c 。

示例 1：

输入：c = 5

输出：true

解释：1 * 1 + 2 * 2 = 5

示例 2：

输入：c = 3

输出：false

提示：

0 <= c <= 231 - 1

题解：
方法：相向双指针
        

class Solution {public boolean judgeSquareSum(int c) {int a = 0;int b = (int) Math.sqrt(c);while (a <= b) {if (a * a == c - b * b) { // 避免溢出return true;}if (a * a < c - b * b) {a++;} else {b--;}}return false;}
}

---

5.求出硬币游戏的赢家

题目链接：3222. 求出硬币游戏的赢家

给你两个 正 整数 x 和 y ，分别表示价值为 75 和 10 的硬币的数目。

Alice 和 Bob 正在玩一个游戏。每一轮中，Alice 先进行操作，Bob 后操作。每次操作中，玩家需要拿走价值 总和 为 115 的硬币。如果一名玩家无法执行此操作，那么这名玩家 输掉 游戏。

两名玩家都采取 最优 策略，请你返回游戏的赢家。

示例 1：

输入：x = 2, y = 7

输出：“Alice”

解释：

游戏一次操作后结束：

Alice 拿走 1 枚价值为 75 的硬币和 4 枚价值为 10 的硬币。

示例 2：

输入：x = 4, y = 11

输出：“Bob”

解释：

游戏 2 次操作后结束：

Alice 拿走 1 枚价值为 75 的硬币和 4 枚价值为 10 的硬币。

Bob 拿走 1 枚价值为 75 的硬币和 4 枚价值为 10 的硬币。

提示：

1 <= x, y <= 100

题解：
方法：数学
        

class Solution {public String losingPlayer(int x, int y) {return Math.min(x, y / 4) % 2 != 0 ? "Alice" : "Bob";}
}

---

6.长度为 K 的子数组的能量值 I

题目链接：3254. 长度为 K 的子数组的能量值 I

给你一个长度为 n 的整数数组 nums 和一个正整数 k 。

一个数组的 能量值 定义为：

如果 所有 元素都是依次 连续 且 上升 的，那么能量值为 最大 的元素。
否则为 -1 。
你需要求出 nums 中所有长度为 k 的
子数组
的能量值。

请你返回一个长度为 n - k + 1 的整数数组 results ，其中 results[i] 是子数组 nums[i…(i + k - 1)] 的能量值。

示例 1：

输入：nums = [1,2,3,4,3,2,5], k = 3

输出：[3,4,-1,-1,-1]

解释：

nums 中总共有 5 个长度为 3 的子数组：

[1, 2, 3] 中最大元素为 3 。

[2, 3, 4] 中最大元素为 4 。

[3, 4, 3] 中元素 不是 连续的。

[4, 3, 2] 中元素 不是 上升的。

[3, 2, 5] 中元素 不是 连续的。

示例 2：

输入：nums = [2,2,2,2,2], k = 4

输出：[-1,-1]

示例 3：

输入：nums = [3,2,3,2,3,2], k = 2

输出：[-1,3,-1,3,-1]

提示：

1 <= n == nums.length <= 500

1 <= nums[i] <= 105

1 <= k <= n

题解：
方法：递推
        

class Solution {public int[] resultsArray(int[] nums, int k) {int n = nums.length;int[] f = new int[n];Arrays.fill(f, 1);for (int i = 1; i < n; ++i) {if (nums[i] == nums[i - 1] + 1) {f[i] = f[i - 1] + 1;}}int[] ans = new int[n - k + 1];for (int i = k - 1; i < n; ++i) {ans[i - k + 1] = f[i] >= k ? nums[i] : -1;}return ans;}
}

---

7.长度为 K 的子数组的能量值 II

题目链接：3255. 长度为 K 的子数组的能量值 II

给你一个长度为 n 的整数数组 nums 和一个正整数 k 。

一个数组的 能量值 定义为：

如果 所有 元素都是依次 连续 且 上升 的，那么能量值为 最大 的元素。
否则为 -1 。
你需要求出 nums 中所有长度为 k 的
子数组
的能量值。

请你返回一个长度为 n - k + 1 的整数数组 results ，其中 results[i] 是子数组 nums[i…(i + k - 1)] 的能量值。

示例 1：

输入：nums = [1,2,3,4,3,2,5], k = 3

输出：[3,4,-1,-1,-1]

解释：

nums 中总共有 5 个长度为 3 的子数组：

[1, 2, 3] 中最大元素为 3 。

[2, 3, 4] 中最大元素为 4 。

[3, 4, 3] 中元素 不是 连续的。

[4, 3, 2] 中元素 不是 上升的。

[3, 2, 5] 中元素 不是 连续的。

示例 2：

输入：nums = [2,2,2,2,2], k = 4

输出：[-1,-1]

示例 3：

输入：nums = [3,2,3,2,3,2], k = 2

输出：[-1,3,-1,3,-1]

提示：

1 <= n == nums.length <= 500

1 <= nums[i] <= 105

1 <= k <= n

题解：

        

class Solution {public int[] resultsArray(int[] nums, int k) {int[] ans = new int[nums.length - k + 1];Arrays.fill(ans, -1);int cnt = 0;for (int i = 0; i < nums.length; i++) {cnt = i == 0 || nums[i] == nums[i - 1] + 1 ? cnt + 1 : 1;if (cnt >= k) {ans[i - k + 1] = nums[i];}}return ans;}
}

---

8.判断矩形的两个角落是否可达

题目链接：3235. 判断矩形的两个角落是否可达

给你两个正整数 xCorner 和 yCorner 和一个二维整数数组 circles ，其中 circles[i] = [xi, yi, ri] 表示一个圆心在 (xi, yi) 半径为 ri 的圆。

坐标平面内有一个左下角在原点，右上角在 (xCorner, yCorner) 的矩形。你需要判断是否存在一条从左下角到右上角的路径满足：路径 完全 在矩形内部，不会 触碰或者经过 任何 圆的内部和边界，同时 只 在起点和终点接触到矩形。

如果存在这样的路径，请你返回 true ，否则返回 false 。

示例 1：

输入：X = 3, Y = 4, circles = [[2,1,1]]

输出：true

解释：

黑色曲线表示一条从 (0, 0) 到 (3, 4) 的路径。

示例 2：

输入：X = 3, Y = 3, circles = [[1,1,2]]

输出：false

解释：

不存在从 (0, 0) 到 (3, 3) 的路径。

示例 3：

输入：X = 3, Y = 3, circles = [[2,1,1],[1,2,1]]

输出：false

解释：

不存在从 (0, 0) 到 (3, 3) 的路径。

示例 4：

输入：X = 4, Y = 4, circles = [[5,5,1]]

输出：true

解释：

提示：

3 <= xCorner, yCorner <= 109

1 <= circles.length <= 1000

circles[i].length == 3

1 <= xi, yi, ri <= 109

题解：
方法：深度优先搜索
        

class Solution {public boolean canReachCorner(int X, int Y, int[][] circles) {boolean[] vis = new boolean[circles.length];for (int i = 0; i < circles.length; i++) {long x = circles[i][0], y = circles[i][1], r = circles[i][2];if (inCircle(x, y, r, 0, 0) || // 圆 i 包含矩形左下角inCircle(x, y, r, X, Y) || // 圆 i 包含矩形右上角// 圆 i 是否与矩形上边界/左边界相交相切!vis[i] && (x <= X && Math.abs(y - Y) <= r || y <= Y && x <= r) && dfs(i, X, Y, circles, vis)) {return false;}}return true;}// 判断点 (x,y) 是否在圆 (ox,oy,r) 内private boolean inCircle(long ox, long oy, long r, long x, long y) {return (ox - x) * (ox - x) + (oy - y) * (oy - y) <= r * r;}private boolean dfs(int i, int X, int Y, int[][] circles, boolean[] vis) {long x1 = circles[i][0], y1 = circles[i][1], r1 = circles[i][2];// 圆 i 是否与矩形右边界/下边界相交相切if (y1 <= Y && Math.abs(x1 - X) <= r1 || x1 <= X && y1 <= r1) {return true;}vis[i] = true;for (int j = 0; j < circles.length; j++) {long x2 = circles[j][0], y2 = circles[j][1], r2 = circles[j][2];// 在两圆相交相切的前提下，点 A 是否严格在矩形内if (!vis[j] &&(x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) <= (r1 + r2) * (r1 + r2) &&x1 * r2 + x2 * r1 < (r1 + r2) * X &&y1 * r2 + y2 * r1 < (r1 + r2) * Y &&dfs(j, X, Y, circles, vis)) {return true;}}return false;}
}

---

9.设计相邻元素求和服务

题目链接：3242. 设计相邻元素求和服务

给你一个 n x n 的二维数组 grid，它包含范围 [0, n2 - 1] 内的不重复元素。

实现 neighborSum 类：

neighborSum(int [][]grid) 初始化对象。
int adjacentSum(int value) 返回在 grid 中与 value 相邻的元素之和，相邻指的是与 value 在上、左、右或下的元素。
int diagonalSum(int value) 返回在 grid 中与 value 对角线相邻的元素之和，对角线相邻指的是与 value 在左上、右上、左下或右下的元素。

示例 1：

输入：

[“neighborSum”, “adjacentSum”, “adjacentSum”, “diagonalSum”,
“diagonalSum”]

[[[[0, 1, 2], [3, 4, 5], [6, 7, 8]]], [1], [4], [4], [8]]

输出： [null, 6, 16, 16, 4]

解释：

1 的相邻元素是 0、2 和 4。

4 的相邻元素是 1、3、5 和 7。

4 的对角线相邻元素是 0、2、6 和 8。

8 的对角线相邻元素是 4。

示例 2：

输入：

[“neighborSum”, “adjacentSum”, “diagonalSum”]

[[[[1, 2, 0, 3], [4, 7, 15, 6], [8, 9, 10, 11], [12, 13, 14, 5]]],
[15], [9]]

输出： [null, 23, 45]

解释：

15 的相邻元素是 0、10、7 和 6。

9 的对角线相邻元素是 4、12、14 和 15。

提示：

3 <= n == grid.length == grid[0].length <= 10

0 <= grid[i][j] <= n2 - 1

所有 grid[i][j] 值均不重复。

adjacentSum 和 diagonalSum 中的 value 均在范围 [0, n2 - 1] 内。

最多会调用 adjacentSum 和 diagonalSum 总共 2 * n2 次。

题解：
方法：预处理
        

class NeighborSum {private static final int[][] DIRS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {1, 1}, {-1, 1}, {-1, -1}, {1, -1}};private final int[][] s;public NeighborSum(int[][] grid) {int n = grid.length;s = new int[n * n][2];for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {int v = grid[i][j];for (int k = 0; k < 8; k++) {int x = i + DIRS[k][0];int y = j + DIRS[k][1];if (0 <= x && x < n && 0 <= y && y < n) {s[v][k / 4] += grid[x][y];}}}}}public int adjacentSum(int value) {return s[value][0];}public int diagonalSum(int value) {return s[value][1];}
}

---

10.有序数组中的单一元素

题目链接：540. 有序数组中的单一元素

给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。

请你找出并返回只出现一次的那个数。

你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。

示例 1:

输入: nums = [1,1,2,3,3,4,4,8,8]

输出: 2

示例 2:

输入: nums = [3,3,7,7,10,11,11]

输出: 10

提示:

1 <= nums.length <= 105

0 <= nums[i] <= 105

题解：
方法：二分
        

class Solution {public int singleNonDuplicate(int[] nums) {int left = -1;int right = nums.length / 2;while (left + 1 < right) {int mid = (left + right) >>> 1;if (nums[mid * 2] != nums[mid * 2 + 1]) {right = mid;} else {left = mid;}}return nums[right * 2];}
}

下接：【题解】—— LeetCode一周小结46

---