当前位置：首页 > news >正文

第 89 场周赛：山脉数组的峰值索引、车队、考场就坐、相似度为 K 的字符串

news 2025/7/1 5:48:26

Q1、[中等] 山脉数组的峰值索引

1、题目描述

给定一个长度为 n 的整数山脉数组 arr ，其中的值递增到一个 峰值元素 然后递减。

返回峰值元素的下标。

你必须设计并实现时间复杂度为 O(log(n)) 的解决方案。

示例 1：
输入：arr = [0,1,0]
输出：1
示例 2：
输入：arr = [0,2,1,0]
输出：1
示例 3：
输入：arr = [0,10,5,2]
输出：1
提示：

3 <= arr.length <= 105
0 <= arr[i] <= 106
题目数据保证 arr 是一个山脉数组

2、解题思路

山脉数组特性：
- 存在一个峰值元素，其左侧所有元素严格递增，右侧所有元素严格递减。
- 峰值元素是数组中最大的元素。
二分查找应用：
- 由于数组是有序的（先增后减），可以利用二分查找来快速定位峰值。
- 比较中间元素与其相邻元素，判断当前处于上升段还是下降段：
  - 如果 arr[mid] > arr[mid-1]，说明处于上升段，峰值在右侧。
  - 否则，处于下降段，峰值在左侧。
边界处理：
- 初始化 left 和 right 时，跳过首尾元素（它们不可能是峰值）。
- 循环条件确保找到唯一的峰值。

3、代码实现

C++

class Solution {
public:int peakIndexInMountainArray(vector<int>& arr) {int left = 1; // 左边界从第二个元素开始（第一个不可能是峰值）int right = arr.size() - 2; // 右边界到倒数第二个元素（最后一个不可能是峰值）while (left < right) {// 计算中间位置，向上取整避免死循环int mid = left + (right - left + 1) / 2;if (arr[mid] > arr[mid - 1]) {// 处于上升段，峰值在右侧left = mid;} else {// 处于下降段，峰值在左侧right = mid - 1;}}// 最终 left 和 right 重合，即为峰值下标return left;}
};

Java

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

Python

class Solution:def peakIndexInMountainArray(self, arr: List[int]) -> int:left, right = 1, len(arr) - 2while left < right:mid = (left + right + 1) // 2  # 向上取整if arr[mid] > arr[mid - 1]:left = midelse:right = mid - 1return left

在这里插入图片描述

4、复杂度分析

时间复杂度：O(log n)，标准的二分查找，每次将搜索范围减半。
空间复杂度：O(1)，只使用了常数级别的额外空间。

Q2、[中等] 车队

1、题目描述

在一条单行道上，有 n 辆车开往同一目的地。目的地是几英里以外的 target 。

给定两个整数数组 position 和 speed ，长度都是 n ，其中 position[i] 是第 i 辆车的位置， speed[i] 是第 i 辆车的速度(单位是英里/小时)。

一辆车永远不会超过前面的另一辆车，但它可以追上去，并以较慢车的速度在另一辆车旁边行驶。

车队是指并排行驶的一辆或几辆汽车。车队的速度是车队中最慢的车的速度。

即便一辆车在 target 才赶上了一个车队，它们仍然会被视作是同一个车队。

返回到达目的地的车队数量。

示例 1：

**输入：**target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]

**输出：**3

解释：

从 10（速度为 2）和 8（速度为 4）开始的车会组成一个车队，它们在 12 相遇。车队在 target 形成。
从 0（速度为 1）开始的车不会追上其它任何车，所以它自己是一个车队。
从 5（速度为 1）和 3（速度为 3）开始的车组成一个车队，在 6 相遇。车队以速度 1 移动直到它到达 target。

示例 2：

**输入：**target = 10, position = [3], speed = [3]

**输出：**1

解释：

只有一辆车，因此只有一个车队。

示例 3：

**输入：**target = 100, position = [0,2,4], speed = [4,2,1]

**输出：**1

解释：

从 0（速度为 4）和 2（速度为 2）开始的车组成一个车队，在 4 相遇。从 4 开始的车（速度为 1）移动到了 5。
然后，在 4（速度为 2）的车队和在 5（速度为 1）的车成为一个车队，在 6 相遇。车队以速度 1 移动直到它到达 target。

提示：

n == position.length == speed.length
1 <= n <= 105
0 < target <= 106
0 <= position[i] < target
position 中每个值都不同
0 < speed[i] <= 106

2、解题思路

问题分析：
- 车辆按位置和速度行驶，不能超车，只能追上并形成车队。
- 车队的速度是其最慢车辆的速度。
- 车辆按位置排序后，从后向前检查是否能形成车队。
关键观察：
- 如果一辆车到达目的地的时间比它前面的车短，它们不会形成车队。
- 否则，前面的车会被追上，形成车队，且车队的时间为当前车的到达时间。
算法选择：
- 计算每辆车到达目的地的时间。
- 按位置排序车辆（从近到远）。
- 从后向前遍历，比较相邻车辆的到达时间：
  - 如果后车时间更短，则不能形成车队，车队数量加1。
  - 否则，前车会被后车追上，更新前车的到达时间为后车的到达时间。

3、代码实现

C++

// 车辆类，记录位置和到达时间
class Car {
public:int position;double time;Car(int p, double t) : position(p), time(t) {}
};class Solution {
public:int carFleet(int target, vector<int>& position, vector<int>& speed) {int n = position.size();if (n == 0) {return 0;}vector<Car> cars;// 计算每辆车到达目的地的时间for (int i = 0; i < n; ++i) {double time = static_cast<double>(target - position[i]) / speed[i];cars.emplace_back(position[i], time);}// 按位置从近到远排序sort(cars.begin(), cars.end(), [](const Car& a, const Car& b) {return a.position < b.position;});int fleetCount = 0;int i = n - 1; // 从最远的车开始检查while (i > 0) {if (cars[i].time < cars[i - 1].time) {// 前车无法被追上，车队数量加1fleetCount++;} else {// 前车会被追上，保持后车的到达时间cars[i - 1].time = cars[i].time;}i--;}// 最后一辆车单独为一个车队return fleetCount + 1;}
};

Java

class Car {int position;double time;Car(int p, double t) {position = p;time = t;}
}class Solution {public int carFleet(int target, int[] position, int[] speed) {int n = position.length;if (n == 0)return 0;Car[] cars = new Car[n];for (int i = 0; i < n; ++i) {double time = (double) (target - position[i]) / speed[i];cars[i] = new Car(position[i], time);}Arrays.sort(cars, (a, b) -> a.position - b.position);int fleetCount = 0;int i = n - 1;while (i > 0) {if (cars[i].time < cars[i - 1].time) {fleetCount++;} else {cars[i - 1].time = cars[i].time;}i--;}return fleetCount + 1;}
}

Python

class Solution:def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:n = len(position)if n == 0:return 0cars = []for i in range(n):time = (target - position[i]) / speed[i]cars.append((position[i], time))# 按位置排序cars.sort()fleet_count = 0i = n - 1while i > 0:if cars[i][1] < cars[i - 1][1]:fleet_count += 1else:cars[i - 1] = (cars[i - 1][0], cars[i][1])i -= 1return fleet_count + 1

在这里插入图片描述

4、复杂度分析

时间复杂度：O(n log n)，主要是排序的时间复杂度。
空间复杂度：O(n)，存储车辆信息所需空间。

Q3、[中等] 考场就坐

1、题目描述

在考场里，有 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 次。

2、解题思路

数据结构选择：
- 有序集合 seats：维护当前被占用的座位，便于快速查找相邻座位。
- 优先队列 pq：存储所有可能的空位区间，按区间长度排序，最长的优先处理。
座位选择策略：
- 新学生应坐的座位是现有区间中离最近的人最远的位置。
- 若区间 [a, b]，最优座位是 (a + b) // 2，距离为 (b - a) // 2。
- 比较所有区间的可能座位，选择最优。
处理离开座位：
- 学生离开后，合并左右相邻的空位区间，并更新优先队列。

3、代码实现

C++

// 自定义比较器, 用于优先队列中的区间排序
// 优先选择长度较大的区间, 若长度相同则选择起始点较小的区间
struct Comp {bool operator()(const pair<int, int>& p1, const pair<int, int>& p2) {// 计算两个区间的半长度 (即距离)int d1 = p1.second - p1.first;int d2 = p2.second - p2.first;// 比较半长度, 较大的优先: 若相同起始点小的优先return d1 / 2 < d2 / 2 || (d1 / 2 == d2 / 2 && p1.first > p2.first);}
};class ExamRoom {
private:int n;          // 考场座位总数set<int> seats; // 当前被占用的座位 (自动排序)priority_queue<pair<int, int>, vector<pair<int, int>>, Comp> pq; // 可用区间优化队列public:ExamRoom(int n) : n(n) {}// 安排下一个学生就坐int seat() {// 情况 1: 考场无人, 直接坐 0 号座位if (seats.empty()) {seats.insert(0);return 0;}// 计算最左和最右的空位区间长度int left = *seats.begin();           // 最左被占用座位到 0 的距离int right = n - 1 - *seats.rbegin(); // 最右被占用座位到 n-1 的距离// 检查优先队列中的区间是否有效while (!pq.empty() && seats.size() >= 2) {auto p = pq.top(); // 获取当前最优区间// 验证区间是否未被分割且端点仍被占用if (seats.count(p.first) && seats.count(p.second) &&*next(seats.find(p.first)) == p.second) {int d = p.second - p.first; // 区间长度// 如果当前区间不是最优 (比左右边界短), 则退出循环if (d / 2 < right || (d / 2 <= left && p.first != 0)) {break;}// 分割区间并插入新座位pq.pop();int new_seat = p.first + d / 2; // 计算最优座位pq.push({p.first, new_seat});   // 插入左半区间pq.push({new_seat, p.second});  // 插入右半区间seats.insert(new_seat);         // 占用新座位return new_seat;}// 无效区间，弹出队列pq.pop();}// 处理最左或最右的区间（当队列中没有更优区间时）if (right > left) {                    // 最右区间更优pq.push({*seats.rbegin(), n - 1}); // 插入最右区间seats.insert(n - 1);               // 占用最右座位return n - 1;} else {                          // 最左区间更优pq.push({0, *seats.begin()}); // 插入最左区间seats.insert(0);              // 占用最左座位return 0;}}// 学生离开座位pvoid leave(int p) {auto it = seats.find(p);int left = -1, right = -1;// 获取左右相邻座位（如果存在）if (it != seats.begin()) {left = *prev(it);}if (next(it) != seats.end()) {right = *next(it);}seats.erase(p); // 移除该座位// 如果左右都有相邻座位，则合并为新区间加入队列if (left != -1 && right != -1) {pq.push({left, right});}}
};

Java

class ExamRoom {private int n; // 考场座位总数private TreeSet<Integer> seats; // 当前被占用的座位 (自动排序)private PriorityQueue<int[]> pq; // 可用区间优先队列// 构造函数，初始化考场public ExamRoom(int n) {this.n = n;seats = new TreeSet<>();// 优先队列排序规则：区间长度大的优先，长度相同则起始点小的优先pq = new PriorityQueue<>((a, b) -> {int d1 = a[1] - a[0], d2 = b[1] - b[0];if (d1 / 2 != d2 / 2) {return d2 / 2 - d1 / 2; // 长度大的优先} else {return a[0] - b[0]; // 长度相同则起始点小的优先}});}// 安排下一个学生就座public int seat() {// 情况1：考场无人，直接坐0号座位if (seats.isEmpty()) {seats.add(0);return 0;}// 计算最左和最右的空位区间长度int left = seats.first(); // 最左被占用座位到0的距离int right = n - 1 - seats.last(); // 最右被占用座位到n-1的距离// 检查优先队列中的区间是否有效while (!pq.isEmpty() && seats.size() >= 2) {int[] p = pq.peek(); // 获取当前最优区间// 验证区间是否未被分割且端点仍被占用if (!seats.contains(p[0]) || !seats.contains(p[1]) || seats.higher(p[0]) != p[1]) {pq.poll(); // 无效区间，弹出队列continue;}int d = p[1] - p[0]; // 区间长度// 如果当前区间不是最优（比左右边界短），则退出循环if (d / 2 < right && (d / 2 <= left && p[0] != 0)) {break;}// 分割区间并插入新座位pq.poll(); // 移除当前区间int newSeat = p[0] + d / 2; // 计算最优座位pq.offer(new int[] { p[0], newSeat }); // 插入左半区间pq.offer(new int[] { newSeat, p[1] }); // 插入右半区间seats.add(newSeat); // 占用新座位return newSeat;}// 处理最左或最右的区间（当队列中没有更优区间时）if (right > left) { // 最右区间更优pq.offer(new int[] { seats.last(), n - 1 }); // 插入最右区间seats.add(n - 1); // 占用最右座位return n - 1;} else { // 最左区间更优pq.offer(new int[] { 0, seats.first() }); // 插入最左区间seats.add(0); // 占用最左座位return 0;}}// 学生离开座位ppublic void leave(int p) {// 获取左右相邻座位（如果存在）Integer left = seats.lower(p);Integer right = seats.higher(p);seats.remove(p); // 移除该座位// 如果左右都有相邻座位，则合并为新区间加入队列if (left != null && right != null) {pq.offer(new int[] { left, right });}}
}

在这里插入图片描述

4、复杂度分析

时间复杂度：
- seat()：平均 O(log n)，最坏 O(n)。
- leave()：平均 O(log n)，最坏 O(n)。
空间复杂度：O(n)，存储座位和区间信息。

Q4、[困难] 相似度为 K 的字符串

1、题目描述

对于某些非负整数 k ，如果交换 s1 中两个字母的位置恰好 k 次，能够使结果字符串等于 s2 ，则认为字符串 s1 和 s2 的 相似度为 k 。

给你两个字母异位词 s1 和 s2 ，返回 s1 和 s2 的相似度 k 的最小值。

示例 1：
输入：s1 = "ab", s2 = "ba"
输出：1
示例 2：
输入：s1 = "abc", s2 = "bca"
输出：2
提示：

1 <= s1.length <= 20
s2.length == s1.length
s1 和 s2 只包含集合 {'a', 'b', 'c', 'd', 'e', 'f'} 中的小写字母
s2 是 s1 的一个字母异位词

2、解题思路

这是一个典型的状态空间搜索问题，可以使用广度优先搜索（BFS）来解决。由于直接交换两个字符可以快速接近目标字符串，BFS 能够保证在最短的交换次数内找到解。

状态表示：每个状态是当前的字符串 cur 和下一个需要处理的字符位置 pos。
初始状态：s1 和位置 0。
状态转移：对于当前字符串 cur，从 pos 开始，找到第一个 cur[pos] != s2[pos] 的位置。然后，遍历 pos 之后的字符，找到可以交换的字符 cur[j] == s2[pos]，交换 cur[pos] 和 cur[j]，生成新状态。
终止条件：当前字符串 cur 等于 s2 时，返回当前的交换次数（即 BFS 的层数）。
去重：使用哈希集合 visit 记录已经访问过的状态，避免重复处理。

3、代码实现

C++

class Solution {
public:int kSimilarity(string s1, string s2) {int n = s1.size();queue<pair<string, int>> q;  // 队列存储当前字符串和下一个处理位置unordered_set<string> visit; // 记录已访问的字符串q.emplace(s1, 0);            // 初始状态：s1 和位置 0visit.emplace(s1);           // 标记 s1 为已访问// step 表示当前的交换次数for (int step = 0;; ++step) {int size = q.size(); // 当前层的状态数for (int i = 0; i < size; ++i) {auto [cur, pos] = q.front(); // 取出队首状态q.pop();// 找到目标字符串，返回当前交换次数if (cur == s2) {return step;}// 跳过已经匹配的位置while (pos < n && cur[pos] == s2[pos]) {pos++;}// 从 pos + 1 开始寻找可以交换的字符for (int j = pos + 1; j < n; ++j) {// 找到可以交换的字符：cur[j] 需要等于 s2[pos] 且不等于 s2[j]if (cur[j] != s2[j] && cur[j] == s2[pos]) {swap(cur[pos], cur[j]); // 交换字符// 如果新字符串未被访问if (!visit.count(cur)) {visit.emplace(cur);      // 标记为已访问q.emplace(cur, pos + 1); // 加入队列，处理下一个位置}swap(cur[pos], cur[j]); // 恢复字符，继续尝试其他交换}}}}}
};

Java

class Solution {public int kSimilarity(String s1, String s2) {int n = s1.length();Queue<Pair<String, Integer>> q = new LinkedList<>(); // 队列存储当前字符串和下一个处理位置Set<String> visit = new HashSet<>(); // 记录已访问的字符串q.offer(new Pair<>(s1, 0)); // 初始状态：s1 和位置 0visit.add(s1); // 标记 s1 为已访问// step 表示当前的交换次数for (int step = 0;; ++step) {int size = q.size(); // 当前层的状态数for (int i = 0; i < size; ++i) {Pair<String, Integer> p = q.poll();String cur = p.getKey();int pos = p.getValue();// 找到目标字符串，返回当前交换次数if (cur.equals(s2)) {return step;}// 跳过已经匹配的位置while (pos < n && cur.charAt(pos) == s2.charAt(pos)) {pos++;}// 从 pos + 1 开始寻找可以交换的字符for (int j = pos + 1; j < n; ++j) {// 找到可以交换的字符：cur[j] 需要等于 s2[pos] 且不等于 s2[j]if (cur.charAt(j) != s2.charAt(j) && cur.charAt(j) == s2.charAt(pos)) {char[] arr = cur.toCharArray();swap(arr, pos, j); // 交换字符String next = new String(arr);if (!visit.contains(next)) { // 如果新字符串未被访问visit.add(next); // 标记为已访问q.offer(new Pair<>(next, pos + 1)); // 加入队列，处理下一个位置}}}}}}private void swap(char[] arr, int i, int j) {char tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}
}

Python

class Solution:def kSimilarity(self, s1: str, s2: str) -> int:n = len(s1)q = deque([(s1, 0)])  # 队列存储当前字符串和下一个处理位置visit = {s1}  # 记录已访问的字符串step = 0while q:size = len(q)  # 当前层的状态数for _ in range(size):cur, pos = q.popleft()if cur == s2:  # 找到目标字符串，返回当前交换次数return step# 跳过已经匹配的位置while pos < n and cur[pos] == s2[pos]:pos += 1# 从 pos + 1 开始寻找可以交换的字符for j in range(pos + 1, n):# 找到可以交换的字符：cur[j] 需要等于 s2[pos] 且不等于 s2[j]if cur[j] != s2[j] and cur[j] == s2[pos]:# 交换字符arr = list(cur)arr[pos], arr[j] = arr[j], arr[pos]next_str = "".join(arr)if next_str not in visit:  # 如果新字符串未被访问visit.add(next_str)  # 标记为已访问q.append((next_str, pos + 1))  # 加入队列，处理下一个位置step += 1

在这里插入图片描述

4、复杂度分析

时间复杂度：最坏情况下为 O(n^2)，其中 n 是字符串长度。每个状态可能生成 O(n) 个新状态，最多有 O(n!) 种排列，但在实际问题中由于去重和剪枝，实际运行时间会远小于理论最坏情况。
空间复杂度：O(n!)，用于存储访问过的字符串状态。但在实际问题中，由于去重和剪枝，实际空间消耗会远小于理论最坏情况。

查看全文

http://www.lqws.cn/news/577027.html