🌟欢迎来到 我的博客 —— 探索技术的无限可能!
🌟博客的简介(文章目录)
【题解】—— 每日一道题目栏
上接:【题解】—— LeetCode一周小结27
8.寻找数组的中心下标
题目链接:724. 寻找数组的中心下标
给你一个整数数组 nums ,请计算数组的 中心下标 。
数组 中心下标 是数组的一个下标,其左侧所有元素相加的和等于右侧所有元素相加的和。
如果中心下标位于数组最左端,那么左侧数之和视为 0 ,因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
如果数组有多个中心下标,应该返回 最靠近左边 的那一个。如果数组不存在中心下标,返回 -1 。
示例 1:
输入:nums = [1, 7, 3, 6, 5, 6]
输出:3
解释:
中心下标是 3 。
左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ,
右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ,二者相等。
示例 2:
输入:nums = [1, 2, 3]
输出:-1
解释:
数组中不存在满足此条件的中心下标。
示例 3:
输入:nums = [2, 1, -1]
输出:0
解释:
中心下标是 0 。
左侧数之和 sum = 0 ,(下标 0 左侧不存在元素),
右侧数之和 sum = nums[1] + nums[2] = 1 + -1 = 0 。
提示:
1 <= nums.length <= 104
-1000 <= nums[i] <= 1000
题解:
方法:遍历数组
class Solution {
public int pivotIndex(int[] nums) {
int s = 0;
for (int num : nums) {
s += num;
}
int leftS = 0;
for (int i = 0; i < nums.length; i++) {
if (leftS * 2 == s - nums[i]) {
return i;
}
leftS += nums[i];
}
return -1;
}
}
9.最小化曼哈顿距离
题目链接:3102. 最小化曼哈顿距离
给你一个下标从 0 开始的数组 points ,它表示二维平面上一些点的整数坐标,其中 points[i] = [xi, yi] 。
两点之间的距离定义为它们的
曼哈顿距离
。
请你恰好移除一个点,返回移除后任意两点之间的 最大 距离可能的 最小 值。
示例 1:
输入:points = [[3,10],[5,15],[10,2],[4,4]]
输出:12
解释:移除每个点后的最大距离如下所示:
- 移除第 0 个点后,最大距离在点 (5, 15) 和 (10, 2) 之间,为 |5 - 10| + |15 - 2| = 18 。
- 移除第 1 个点后,最大距离在点 (3, 10) 和 (10, 2) 之间,为 |3 - 10| + |10 - 2| = 15 。
- 移除第 2 个点后,最大距离在点 (5, 15) 和 (4, 4) 之间,为 |5 - 4| + |15 - 4| = 12 。
- 移除第 3 个点后,最大距离在点 (5, 15) 和 (10, 2) 之间的,为 |5 - 10| + |15 - 2| = 18 。
在恰好移除一个点后,任意两点之间的最大距离可能的最小值是 12 。
示例 2:
输入:points = [[1,1],[1,1],[1,1]]
输出:0
解释:移除任一点后,任意两点之间的最大距离都是 0 。
提示:
3 <= points.length <= 105
points[i].length == 2
1 <= points[i][0], points[i][1] <= 108
题解:
方法:维护最大次大、最小次小
参考:【图解】曼哈顿距离转切比雪夫距离
class Solution {
public int minimumDistance(int[][] points) {
final int INF = Integer.MAX_VALUE;
int maxX1 = -INF, maxX2 = -INF, maxY1 = -INF, maxY2 = -INF;
int minX1 = INF, minX2 = INF, minY1 = INF, minY2 = INF;
for (int[] p : points) {
int x = p[0] + p[1];
int y = p[1] - p[0];
// x 最大次大
if (x > maxX1) {
maxX2 = maxX1;
maxX1 = x;
} else if (x > maxX2) {
maxX2 = x;
}
// x 最小次小
if (x < minX1) {
minX2 = minX1;
minX1 = x;
} else if (x < minX2) {
minX2 = x;
}
// y 最大次大
if (y > maxY1) {
maxY2 = maxY1;
maxY1 = y;
} else if (y > maxY2) {
maxY2 = y;
}
// y 最小次小
if (y < minY1) {
minY2 = minY1;
minY1 = y;
} else if (y < minY2) {
minY2 = y;
}
}
int ans = INF;
for (int[] p : points) {
int x = p[0] + p[1];
int y = p[1] - p[0];
int dx = (x == maxX1 ? maxX2 : maxX1) - (x == minX1 ? minX2 : minX1);
int dy = (y == maxY1 ? maxY2 : maxY1) - (y == minY1 ? minY2 : minY1);
ans = Math.min(ans, Math.max(dx, dy));
}
return ans;
}
}
10.统计移除递增子数组的数目 I
题目链接:2970. 统计移除递增子数组的数目 I
给你一个下标从 0 开始的 正 整数数组 nums 。
如果 nums 的一个子数组满足:移除这个子数组后剩余元素 严格递增 ,那么我们称这个子数组为 移除递增 子数组。比方说,[5, 3, 4, 6, 7] 中的 [3, 4] 是一个移除递增子数组,因为移除该子数组后,[5, 3, 4, 6, 7] 变为 [5, 6, 7] ,是严格递增的。
请你返回 nums 中 移除递增 子数组的总数目。
注意 ,剩余元素为空的数组也视为是递增的。
子数组 指的是一个数组中一段非空且连续的元素序列。
示例 1:
输入:nums = [1,2,3,4]
输出:10
解释:10 个移除递增子数组分别为:[1], [2], [3], [4], [1,2], [2,3], [3,4], [1,2,3],
[2,3,4] 和 [1,2,3,4]。移除任意一个子数组后,剩余元素都是递增的。注意,空数组不是移除递增子数组。
示例 2:
输入:nums = [6,5,7,8]
输出:7
解释:7 个移除递增子数组分别为:[5], [6], [5,7], [6,5], [5,7,8], [6,5,7] 和 [6,5,7,8]
。nums 中只有这 7 个移除递增子数组。
示例 3:
输入:nums = [8,7,6,6]
输出:3
解释:3 个移除递增子数组分别为:[8,7,6], [7,6,6] 和 [8,7,6,6] 。注意 [8,7] 不是移除递增子数组因为
移除 [8,7] 后 nums 变为 [6,6] ,它不是严格递增的。
提示:
1 <= nums.length <= 50
1 <= nums[i] <= 50
题解:
方法:双指针
class Solution {
public int incremovableSubarrayCount(int[] nums) {
int i = 0, n = nums.length;
while (i + 1 < n && nums[i] < nums[i + 1]) {
++i;
}
if (i == n - 1) {
return n * (n + 1) / 2;
}
int ans = i + 2;
for (int j = n - 1; j > 0; --j) {
while (i >= 0 && nums[i] >= nums[j]) {
--i;
}
ans += i + 2;
if (nums[j - 1] >= nums[j]) {
break;
}
}
return ans;
}
}
11.统计移除递增子数组的数目 II
题目链接:2972. 统计移除递增子数组的数目 II
给你一个下标从 0 开始的 正 整数数组 nums 。
如果 nums 的一个子数组满足:移除这个子数组后剩余元素 严格递增 ,那么我们称这个子数组为 移除递增 子数组。比方说,[5, 3, 4, 6, 7] 中的 [3, 4] 是一个移除递增子数组,因为移除该子数组后,[5, 3, 4, 6, 7] 变为 [5, 6, 7] ,是严格递增的。
请你返回 nums 中 移除递增 子数组的总数目。
注意 ,剩余元素为空的数组也视为是递增的。
子数组 指的是一个数组中一段连续的元素序列。
示例 1:
输入:nums = [1,2,3,4]
输出:10
解释:10 个移除递增子数组分别为:[1], [2], [3], [4], [1,2], [2,3], [3,4], [1,2,3],
[2,3,4] 和 [1,2,3,4]。移 除任意一个子数组后,剩余元素都是递增的。注意,空数组不是移除递增子数组。
示例 2:
输入:nums = [6,5,7,8]
输出:7
解释:7 个移除递增子数组分别为:[5], [6], [5,7], [6,5], [5,7,8], [6,5,7] 和 [6,5,7,8]
。nums 中只有这 7 个移除递增子数组。
示例 3:
输入:nums = [8,7,6,6]
输出:3
解释:3 个移除递增子数组分别为:[8,7,6], [7,6,6] 和 [8,7,6,6] 。注意 [8,7] 不是移除递增子数组因为移除 [8,7] 后 nums 变为 [6,6] ,它不是严格递增的。
提示:
1 <= nums.length <= 105
1 <= nums[i] <= 109
题解:
方法:双指针
class Solution {
public long incremovableSubarrayCount(int[] a) {
int n = a.length;
int i = 0;
while (i < n - 1 && a[i] < a[i + 1]) {
i++;
}
if (i == n - 1) { // 每个非空子数组都可以移除
return (long) n * (n + 1) / 2;
}
long ans = i + 2; // 不保留后缀的情况,一共 i+2 个
// 枚举保留的后缀为 a[j:]
for (int j = n - 1; j == n - 1 || a[j] < a[j + 1]; j--) {
while (i >= 0 && a[i] >= a[j]) {
i--;
}
// 可以保留前缀 a[:i+1], a[:i], ..., a[:0] 一共 i+2 个
ans += i + 2;
}
return ans;
}
}
12.最小数字游戏
题目链接:2974. 最小数字游戏
你有一个下标从 0 开始、长度为 偶数 的整数数组 nums ,同时还有一个空数组 arr 。Alice 和 Bob 决定玩一个游戏,游戏中每一轮 Alice 和 Bob 都会各自执行一次操作。游戏规则如下:
每一轮,Alice 先从 nums 中移除一个 最小 元素,然后 Bob 执行同样的操作。
接着,Bob 会将移除的元素添加到数组 arr 中,然后 Alice 也执行同样的操作。
游戏持续进行,直到 nums 变为空。
返回结果数组 arr 。
示例 1:
输入:nums = [5,4,2,3]
输出:[3,2,5,4]
解释:第一轮,Alice 先移除 2 ,然后 Bob 移除 3 。然后 Bob 先将 3 添加到 arr 中,接着 Alice 再将 2
添加到 arr 中。于是 arr = [3,2] 。第二轮开始时,nums = [5,4] 。Alice 先移除 4 ,然后 Bob 移除 5 。接着他们都将元素添加到 arr 中,arr
变为 [3,2,5,4] 。
示例 2:
输入:nums = [2,5]
输出:[5,2]
解释:第一轮,Alice 先移除 2 ,然后 Bob 移除 5 。然后 Bob 先将 5 添加到 arr 中,接着 Alice 再将 2
添加到 arr 中。于是 arr = [5,2] 。
提示:
1 <= nums.length <= 100
1 <= nums[i] <= 100
nums.length % 2 == 0
题解:
方法:模拟 + 优先队列
class Solution {
public int[] numberGame(int[] nums) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int x : nums) {
pq.offer(x);
}
int[] ans = new int[nums.length];
int i = 0;
while (!pq.isEmpty()) {
int a = pq.poll();
ans[i++] = pq.poll();
ans[i++] = a;
}
return ans;
}
}
13.判断一个数组是否可以变为有序
题目链接:3011. 判断一个数组是否可以变为有序
给你一个下标从 0 开始且全是 正 整数的数组 nums 。
一次 操作 中,如果两个 相邻 元素在二进制下数位为 1 的数目 相同 ,那么你可以将这两个元素交换。你可以执行这个操作 任意次 (也可以 0 次)。
如果你可以使数组变有序,请你返回 true ,否则返回 false 。
示例 1:
输入:nums = [8,4,2,30,15]
输出:true
解释:我们先观察每个元素的二进制表示。 2 ,4 和 8 分别都只有一个数位为 1 ,分别为 “10” ,“100” 和 “1000”
。15 和 30 分别有 4 个数位为 1 :“1111” 和 “11110” 。我们可以通过 4 个操作使数组有序:
- 交换 nums[0] 和 nums[1] 。8 和 4 分别只有 1 个数位为 1 。数组变为 [4,8,2,30,15] 。
- 交换 nums[1] 和 nums[2] 。8 和 2 分别只有 1 个数位为 1 。数组变为 [4,2,8,30,15] 。
- 交换 nums[0] 和 nums[1] 。4 和 2 分别只有 1 个数位为 1 。数组变为 [2,4,8,30,15] 。
- 交换 nums[3] 和 nums[4] 。30 和 15 分别有 4 个数位为 1 ,数组变为 [2,4,8,15,30] 。
数组变成有序的,所以我们返回 true 。
注意我们还可以通过其他的操作序列使数组变得有序。
示例 2:
输入:nums = [1,2,3,4,5]
输出:true
解释:数组已经是有序的,所以我们返回 true 。
示例 3:
输入:nums = [3,16,8,4,2]
输出:false
解释:无法通过操作使数组变为有序。
提示:
1 <= nums.length <= 100
1 <= nums[i] <= 28
题解:
方法:排序
class Solution {
public boolean canSortArray(int[] nums) {
int n = nums.length;
for (int i = 0; i < n;) {
int start = i;
int ones = Integer.bitCount(nums[i++]);
while (i < n && Integer.bitCount(nums[i]) == ones) {
i++;
}
Arrays.sort(nums, start, i);
}
for (int i = 1; i < n; i++) {
if (nums[i] < nums[i - 1]) {
return false;
}
}
return true;
}
}
14.保持城市天际线
题目链接:807. 保持城市天际线
给你一座由 n x n 个街区组成的城市,每个街区都包含一座立方体建筑。给你一个下标从 0 开始的 n x n 整数矩阵 grid ,其中 grid[r][c] 表示坐落于 r 行 c 列的建筑物的 高度 。
城市的 天际线 是从远处观察城市时,所有建筑物形成的外部轮廓。从东、南、西、北四个主要方向观测到的 天际线 可能不同。
我们被允许为 任意数量的建筑物 的高度增加 任意增量(不同建筑物的增量可能不同) 。 高度为 0 的建筑物的高度也可以增加。然而,增加的建筑物高度 不能影响 从任何主要方向观察城市得到的 天际线 。
在 不改变 从任何主要方向观测到的城市 天际线 的前提下,返回建筑物可以增加的 最大高度增量总和 。
示例 1:
输入:grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]
输出:35
解释:建筑物的高度如上图中心所示。
用红色绘制从不同方向观看得到的天际线。
在不影响天际线的情况下,增加建筑物的高度:
gridNew = [ [8, 4, 8, 7],
[7, 4, 7, 7], [9, 4, 8, 7], [3, 3, 3, 3] ]
示例 2:
输入:grid = [[0,0,0],[0,0,0],[0,0,0]]
输出:0
解释:增加任何建筑物的高度都会导致天际线的变化。
提示:
n == grid.length
n == grid[r].length
2 <= n <= 50
0 <= grid[r][c] <= 100
题解:
方法:贪心
class Solution {
public int maxIncreaseKeepingSkyline(int[][] grid) {
int n = grid.length;
int m = grid[0].length;
int[] rowMax = new int[n];
int[] colMax = new int[m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
rowMax[i] = Math.max(rowMax[i], grid[i][j]);
colMax[j] = Math.max(colMax[j], grid[i][j]);
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
ans += Math.min(rowMax[i], colMax[j]) - grid[i][j];
}
}
return ans;
}
}
下接:【题解】—— LeetCode一周小结29