【题解】—— LeetCode一周小结52
🌟欢迎来到 我的博客 —— 探索技术的无限可能！
🌟博客的简介（文章目录）
【题解】—— 每日一道题目栏
上接：【题解】—— LeetCode一周小结51
23.考场就座
题目链接：855. 考场就座
在考场里，有 n 个座位排成一行，编号为 0 到 n - 1。
当学生进入考场后，他必须坐在离最近的人最远的座位上。如果有多个这样的座位，他会坐在编号最小的座位上。(另外，如果考场里没有人，那么学生就坐在 0 号座位上。)
设计一个模拟所述考场的类。
实现 ExamRoom 类：
ExamRoom(int n) 用座位的数量 n 初始化考场对象。
int seat() 返回下一个学生将会入座的座位编号。
void leave(int p) 指定坐在座位 p 的学生将离开教室。保证座位 p 上会有一位学生。
示例 1：
输入：
[“ExamRoom”, “seat”, “seat”, “seat”, “seat”, “leave”, “seat”]
[[10], [], [], [], [], [4], []]
输出：
[null, 0, 9, 4, 2, null, 5]
解释：
ExamRoom examRoom = new ExamRoom(10);
examRoom.seat(); // 返回 0，房间里没有人，学生坐在 0 号座位。
examRoom.seat(); // 返回 9，学生最后坐在 9 号座位。
examRoom.seat(); // 返回 4，学生最后坐在 4 号座位。
examRoom.seat(); // 返回 2，学生最后坐在 2 号座位。
examRoom.leave(4);
examRoom.seat(); // 返回 5，学生最后坐在 5 号座位。
提示：
1 <= n <= 109
保证有学生正坐在座位 p 上。
seat 和 leave 最多被调用 104 次。
题解：
方法：有序集合 + 哈希表
class ExamRoom {
private TreeSet<int[]> ts = new TreeSet<>((a, b) -> {
int d1 = dist(a), d2 = dist(b);
return d1 == d2 ? a[0] - b[0] : d2 - d1;
});
private Map<Integer, Integer> left = new HashMap<>();
private Map<Integer, Integer> right = new HashMap<>();
private int n;
public ExamRoom(int n) {
this.n = n;
add(new int[] {-1, n});
}
public int seat() {
int[] s = ts.first();
int p = (s[0] + s[1]) >> 1;
if (s[0] == -1) {
p = 0;
} else if (s[1] == n) {
p = n - 1;
}
del(s);
add(new int[] {s[0], p});
add(new int[] {p, s[1]});
return p;
}
public void leave(int p) {
int l = left.get(p), r = right.get(p);
del(new int[] {l, p});
del(new int[] {p, r});
add(new int[] {l, r});
}
private int dist(int[] s) {
int l = s[0], r = s[1];
return l == -1 || r == n ? r - l - 1 : (r - l) >> 1;
}
private void add(int[] s) {
ts.add(s);
left.put(s[1], s[0]);
right.put(s[0], s[1]);
}
private void del(int[] s) {
ts.remove(s);
left.remove(s[1]);
right.remove(s[0]);
}
}
/**
* Your ExamRoom object will be instantiated and called as such:
* ExamRoom obj = new ExamRoom(n);
* int param_1 = obj.seat();
* obj.leave(p);
*/
24.吃苹果的最大数目
题目链接：1705. 吃苹果的最大数目
有一棵特殊的苹果树，一连 n 天，每天都可以长出若干个苹果。在第 i 天，树上会长出 apples[i] 个苹果，这些苹果将会在 days[i] 天后（也就是说，第 i + days[i] 天时）腐烂，变得无法食用。也可能有那么几天，树上不会长出新的苹果，此时用 apples[i] == 0 且 days[i] == 0 表示。
你打算每天 最多 吃一个苹果来保证营养均衡。注意，你可以在这 n 天之后继续吃苹果。
给你两个长度为 n 的整数数组 days 和 apples ，返回你可以吃掉的苹果的最大数目。
示例 1：
输入：apples = [1,2,3,5,2], days = [3,2,1,4,2]
输出：7
解释：你可以吃掉 7 个苹果：
- 第一天，你吃掉第一天长出来的苹果。
- 第二天，你吃掉一个第二天长出来的苹果。
- 第三天，你吃掉一个第二天长出来的苹果。过了这一天，第三天长出来的苹果就已经腐烂了。
- 第四天到第七天，你吃的都是第四天长出来的苹果。
示例 2：
输入：apples = [3,0,0,0,0,2], days = [3,0,0,0,0,2]
输出：5
解释：你可以吃掉 5 个苹果：
- 第一天到第三天，你吃的都是第一天长出来的苹果。
- 第四天和第五天不吃苹果。
- 第六天和第七天，你吃的都是第六天长出来的苹果。
提示：
apples.length == n
days.length == n
1 <= n <= 2 * 104
0 <= apples[i], days[i] <= 2 * 104
只有在 apples[i] = 0 时，days[i] = 0 才成立
题解：
方法：贪心
class Solution {
public int eatenApples(int[] apples, int[] days) {
int ans = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
for (int i = 0; i < apples.length || !pq.isEmpty(); i++) {
while (!pq.isEmpty() && pq.peek()[0] == i) { // 已腐烂
pq.poll();
}
if (i < apples.length && apples[i] > 0) {
pq.offer(new int[]{i + days[i], apples[i]});
}
if (!pq.isEmpty()) {
// 吃一个最早腐烂的苹果
ans++;
if (--pq.peek()[1] == 0) {
pq.poll();
}
}
}
return ans;
}
}
25.切蛋糕的最小总开销 I
题目链接：3218. 切蛋糕的最小总开销 I
有一个 m x n 大小的矩形蛋糕，需要切成 1 x 1 的小块。
给你整数 m ，n 和两个数组：
horizontalCut 的大小为 m - 1 ，其中 horizontalCut[i] 表示沿着水平线 i 切蛋糕的开销。
verticalCut 的大小为 n - 1 ，其中 verticalCut[j] 表示沿着垂直线 j 切蛋糕的开销。
一次操作中，你可以选择任意不是 1 x 1 大小的矩形蛋糕并执行以下操作之一：
沿着水平线 i 切开蛋糕，开销为 horizontalCut[i] 。
沿着垂直线 j 切开蛋糕，开销为 verticalCut[j] 。
每次操作后，这块蛋糕都被切成两个独立的小蛋糕。
每次操作的开销都为最开始对应切割线的开销，并且不会改变。
请你返回将蛋糕全部切成 1 x 1 的蛋糕块的 最小 总开销。
示例 1：
输入：m = 3, n = 2, horizontalCut = [1,3], verticalCut = [5]
输出：13
解释：
沿着垂直线 0 切开蛋糕，开销为 5 。
沿着水平线 0 切开 3 x 1 的蛋糕块，开销为 1 。
沿着水平线 0 切开 3 x 1 的蛋糕块，开销为 1 。
沿着水平线 1 切开 2 x 1 的蛋糕块，开销为 3 。
沿着水平线 1 切开 2 x 1 的蛋糕块，开销为 3 。
总开销为 5 + 1 + 1 + 3 + 3 = 13 。
示例 2：
输入：m = 2, n = 2, horizontalCut = [7], verticalCut = [4]
输出：15
解释：
沿着水平线 0 切开蛋糕，开销为 7 。
沿着垂直线 0 切开 1 x 2 的蛋糕块，开销为 4 。
沿着垂直线 0 切开 1 x 2 的蛋糕块，开销为 4 。
总开销为 7 + 4 + 4 = 15 。
提示：
1 <= m, n <= 20
horizontalCut.length == m - 1
verticalCut.length == n - 1
1 <= horizontalCut[i], verticalCut[i] <= 103
题解：
方法：贪心 + 双指针
class Solution {
public int minimumCost(int m, int n, int[] horizontalCut, int[] verticalCut) {
Arrays.sort(horizontalCut);
Arrays.sort(verticalCut);
int ans = 0;
int i = m - 2, j = n - 2;
int h = 1, v = 1;
while (i >= 0 || j >= 0) {
if (j < 0 || (i >= 0 && horizontalCut[i] > verticalCut[j])) {
ans += horizontalCut[i--] * v;
++h;
} else {
ans += verticalCut[j--] * h;
++v;
}
}
return ans;
}
}
26.字符串及其反转中是否存在同一子字符串
题目链接：3083. 字符串及其反转中是否存在同一子字符串
给你一个字符串 s ，请你判断字符串 s 是否存在一个长度为 2 的子字符串，在其反转后的字符串中也出现。
如果存在这样的子字符串，返回 true；如果不存在，返回 false 。
示例 1：
输入：s = “leetcode”
输出：true
解释：子字符串 “ee” 的长度为 2，它也出现在 reverse(s) == “edocteel” 中。
示例 2：
输入：s = “abcba”
输出：true
解释：所有长度为 2 的子字符串 “ab”、“bc”、“cb”、“ba” 也都出现在 reverse(s) == “abcba” 中。
示例 3：
输入：s = “abcd”
输出：false
解释：字符串 s 中不存在满足「在其反转后的字符串中也出现」且长度为 2 的子字符串。
提示：
1 <= s.length <= 100
字符串 s 仅由小写英文字母组成。
题解：
方法：一次遍历+位运算优化
class Solution {
public boolean isSubstringPresent(String S) {
char[] s = S.toCharArray();
boolean[][] vis = new boolean[26][26];
for (int i = 1; i < s.length; i++) {
int x = s[i - 1] - 'a';
int y = s[i] - 'a';
vis[x][y] = true;
if (vis[y][x]) {
return true;
}
}
return false;
}
}
优化
class Solution:
def isSubstringPresent(self, s: str) -> bool:
vis = [0] * 26
for x, y in pairwise(map(ord, s)):
x -= ord('a')
y -= ord('a')
vis[x] |= 1 << y
if vis[y] >> x & 1:
return True
return False
27.查询数组中元素的出现位置
题目链接：3159. 查询数组中元素的出现位置
给你一个整数数组 nums ，一个整数数组 queries 和一个整数 x 。
对于每个查询 queries[i] ，你需要找到 nums 中第 queries[i] 个 x 的位置，并返回它的下标。如果数组中 x 的出现次数少于 queries[i] ，该查询的答案为 -1 。
请你返回一个整数数组 answer ，包含所有查询的答案。
示例 1：
输入：nums = [1,3,1,7], queries = [1,3,2,4], x = 1
输出：[0,-1,2,-1]
解释：
第 1 个查询，第一个 1 出现在下标 0 处。
第 2 个查询，nums 中只有两个 1 ，所以答案为 -1 。
第 3 个查询，第二个 1 出现在下标 2 处。
第 4 个查询，nums 中只有两个 1 ，所以答案为 -1 。
示例 2：
输入：nums = [1,2,3], queries = [10], x = 5
输出：[-1]
解释：
第 1 个查询，nums 中没有 5 ，所以答案为 -1 。
提示：
1 <= nums.length, queries.length <= 105
1 <= queries[i] <= 105
1 <= nums[i], x <= 104
题解：
方法：模拟
class Solution {
public int[] occurrencesOfElement(int[] nums, int[] queries, int x) {
List<Integer> ids = new ArrayList<>();
for (int i = 0; i < nums.length; ++i) {
if (nums[i] == x) {
ids.add(i);
}
}
int m = queries.length;
int[] ans = new int[m];
for (int i = 0; i < m; ++i) {
int j = queries[i] - 1;
ans[i] = j < ids.size() ? ids.get(j) : -1;
}
return ans;
}
}
28.分割数组
题目链接：3046. 分割数组
给你一个长度为 偶数 的整数数组 nums 。你需要将这个数组分割成 nums1 和 nums2 两部分，要求：
nums1.length == nums2.length == nums.length / 2 。
nums1 应包含 互不相同 的元素。
nums2也应包含 互不相同 的元素。
如果能够分割数组就返回 true ，否则返回 false 。
示例 1：
输入：nums = [1,1,2,2,3,4]
输出：true
解释：分割 nums 的可行方案之一是 nums1 = [1,2,3] 和 nums2 = [1,2,4] 。
示例 2：
输入：nums = [1,1,1,1]
输出：false
解释：分割 nums 的唯一可行方案是 nums1 = [1,1] 和 nums2 = [1,1] 。但 nums1 和 nums2
都不是由互不相同的元素构成。因此，返回 false 。
提示：
1 <= nums.length <= 100
nums.length % 2 == 0
1 <= nums[i] <= 100
题解：
方法：哈希表
class Solution {
public boolean isPossibleToSplit(int[] nums) {
Map<Integer, Integer> cnt = new HashMap<>();
for (int x : nums) {
if (cnt.merge(x, 1, Integer::sum) > 2) { // ++cnt[x] > 2
return false;
}
}
return true;
}
}
29.通过投票对团队排名
题目链接：1366. 通过投票对团队排名
现在有一个特殊的排名系统，依据参赛团队在投票人心中的次序进行排名，每个投票者都需要按从高到低的顺序对参与排名的所有团队进行排位。
排名规则如下：
参赛团队的排名次序依照其所获「排位第一」的票的多少决定。如果存在多个团队并列的情况，将继续考虑其「排位第二」的票的数量。以此类推，直到不再存在并列的情况。
如果在考虑完所有投票情况后仍然出现并列现象，则根据团队字母的字母顺序进行排名。
给你一个字符串数组 votes 代表全体投票者给出的排位情况，请你根据上述排名规则对所有参赛团队进行排名。
请你返回能表示按排名系统 排序后 的所有团队排名的字符串。
示例 1：
输入：votes = [“ABC”,“ACB”,“ABC”,“ACB”,“ACB”]
输出：“ACB”
解释：
A 队获得五票「排位第一」，没有其他队获得「排位第一」，所以 A 队排名第一。
B 队获得两票「排位第二」，三票「排位第三」。
C 队获得三票「排位第二」，两票「排位第三」。
由于 C 队「排位第二」的票数较多，所以 C 队排第二，B 队排第三。
示例 2：
输入：votes = [“WXYZ”,“XYZW”]
输出：“XWYZ”
解释：
X 队在并列僵局打破后成为排名第一的团队。X 队和 W 队的「排位第一」票数一样，但是 X 队有一票「排位第二」，而 W
没有获得「排位第二」。
示例 3：
输入：votes = [“ZMNAGUEDSJYLBOPHRQICWFXTVK”]
输出：“ZMNAGUEDSJYLBOPHRQICWFXTVK”
解释：只有一个投票者，所以排名完全按照他的意愿。
提示：
1 <= votes.length <= 1000
1 <= votes[i].length <= 26
votes[i].length == votes[j].length for 0 <= i, j < votes.length
votes[i][j] 是英文 大写 字母
votes[i] 中的所有字母都是唯一的
votes[0] 中出现的所有字母 同样也 出现在 votes[j] 中，其中 1 <= j < votes.length
题解：
方法：数组 哈希表 排序
class Solution {
public String rankTeams(String[] votes) {
int m = votes[0].length();
int[][] cnts = new int[26][m];
for (String vote : votes) {
for (int i = 0; i < m; i++) {
cnts[vote.charAt(i) - 'A'][i]++;
}
}
return votes[0].chars()
.mapToObj(c -> (char) c)
.sorted((a, b) -> {
int c = Arrays.compare(cnts[b - 'A'], cnts[a - 'A']);
return c != 0 ? c : a - b;
})
.map(String::valueOf)
.collect(Collectors.joining());
}
}
下接：【题解】—— LeetCode一周小结53