欢迎来到 我的博客 —— 探索技术的无限可能！
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
给你一个长度为 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
给你一个长度为 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一周小结45
发表评论 取消回复