🌟欢迎来到 我的博客 —— 探索技术的无限可能！
30.座位预约管理系统
题目链接：1845. 座位预约管理系统
请你设计一个管理 n 个座位预约的系统，座位编号从 1 到 n 。
请你实现 SeatManager 类：
SeatManager(int n) 初始化一个 SeatManager 对象，它管理从 1 到 n 编号的 n 个座位。所有座位初始都是可预约的。
int reserve() 返回可以预约座位的 最小编号 ，此座位变为不可预约。
void unreserve(int seatNumber) 将给定编号 seatNumber 对应的座位变成可以预约。
示例 1：
输入：
[“SeatManager”, “reserve”, “reserve”, “unreserve”, “reserve”,
“reserve”, “reserve”, “reserve”, “unreserve”]
[[5], [], [], [2], [], [], [], [], [5]]
输出：
[null, 1, 2, null, 2, 3, 4, 5, null]
解释：
SeatManager seatManager = new SeatManager(5); // 初始化 SeatManager ，有 5
个座位。
seatManager.reserve(); // 所有座位都可以预约，所以返回最小编号的座位，也就是 1 。
seatManager.reserve(); // 可以预约的座位为 [2,3,4,5] ，返回最小编号的座位，也就是 2 。
seatManager.unreserve(2); // 将座位 2 变为可以预约，现在可预约的座位为 [2,3,4,5] 。
seatManager.reserve(); // 可以预约的座位为 [2,3,4,5] ，返回最小编号的座位，也就是 2 。
seatManager.reserve(); // 可以预约的座位为 [3,4,5] ，返回最小编号的座位，也就是 3 。
seatManager.reserve(); // 可以预约的座位为 [4,5] ，返回最小编号的座位，也就是 4 。
seatManager.reserve(); // 唯一可以预约的是座位 5 ，所以返回 5 。
seatManager.unreserve(5); // 将座位 5 变为可以预约，现在可预约的座位为 [5] 。
提示：
1 <= n <= 105
1 <= seatNumber <= n
每一次对 reserve 的调用，题目保证至少存在一个可以预约的座位。
每一次对 unreserve 的调用，题目保证 seatNumber 在调用函数前都是被预约状态。
对 reserve 和 unreserve 的调用 总共 不超过 105 次。
题解：
方法：维护可预约的座位
class SeatManager { private final PriorityQueue<Integer> available = new PriorityQueue<>(); public SeatManager(int n) { for (int i = 1; i <= n; i++) { available.add(i); } } public int reserve() { return available.poll(); } public void unreserve(int seatNumber) { available.add(seatNumber); } }
2024.10
1.最低票价
题目链接：983. 最低票价
在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。
火车票有 三种不同的销售方式 ：
一张 为期一天 的通行证售价为 costs[0] 美元；
一张 为期七天 的通行证售价为 costs[1] 美元；
一张 为期三十天 的通行证售价为 costs[2] 美元。
通行证允许数天无限制的旅行。 例如，如果我们在第 2 天获得一张 为期 7 天 的通行证，那么我们可以连着旅行 7 天：第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。
返回 你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费 。
示例 1：
输入：days = [1,4,6,7,8,20], costs = [2,7,15]
输出：11
解释：
例如，这里有一种购买通行证的方法，可以让你完成你的旅行计划：
在第 1 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 1 天生效。
在第 3 天，你花了 costs[1] = $7 买了一张为期 7 天的通行证，它将在第 3, 4, …, 9 天生效。
在第 20 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 20 天生效。
你总共花了 $11，并完成了你计划的每一天旅行。
示例 2：
输入：days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
输出：17
解释：
例如，这里有一种购买通行证的方法，可以让你完成你的旅行计划：
在第 1 天，你花了 costs[2] = $15 买了一张为期 30 天的通行证，它将在第 1, 2, …, 30 天生效。
在第 31 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 31 天生效。
你总共花了 $17，并完成了你计划的每一天旅行。
提示：
1 <= days.length <= 365
1 <= days[i] <= 365
days 按顺序严格递增
costs.length == 3
1 <= costs[i] <= 1000
题解：
方法：递归 记忆化搜索 双指针 动态规划
class Solution { public int mincostTickets(int[] days, int[] costs) { int lastDay = days[days.length - 1]; boolean[] isTravel = new boolean[lastDay + 1]; for (int d : days) { isTravel[d] = true; } int[] memo = new int[lastDay + 1]; return dfs(lastDay, isTravel, costs, memo); } private int dfs(int i, boolean[] isTravel, int[] costs, int[] memo) { if (i <= 0) { return 0; } if (memo[i] > 0) { // 之前计算过 return memo[i]; } if (!isTravel[i]) { return memo[i] = dfs(i - 1, isTravel, costs, memo); } return memo[i] = Math.min(dfs(i - 1, isTravel, costs, memo) + costs[0], Math.min(dfs(i - 7, isTravel, costs, memo) + costs[1], dfs(i - 30, isTravel, costs, memo) + costs[2])); } }
2.准时到达的列车最小时速
题目链接：1870. 准时到达的列车最小时速
给你一个浮点数 hour ，表示你到达办公室可用的总通勤时间。要到达办公室，你必须按给定次序乘坐 n 趟列车。另给你一个长度为 n 的整数数组 dist ，其中 dist[i] 表示第 i 趟列车的行驶距离（单位是千米）。
每趟列车均只能在整点发车，所以你可能需要在两趟列车之间等待一段时间。
例如，第 1 趟列车需要 1.5 小时，那你必须再等待 0.5 小时，搭乘在第 2 小时发车的第 2 趟列车。
返回能满足你准时到达办公室所要求全部列车的 最小正整数 时速（单位：千米每小时），如果无法准时到达，则返回 -1 。
生成的测试用例保证答案不超过 107 ，且 hour 的 小数点后最多存在两位数字 。
示例 1：
输入：dist = [1,3,2], hour = 6
输出：1
解释：速度为 1 时：
- 第 1 趟列车运行需要 1/1 = 1 小时。
- 由于是在整数时间到达，可以立即换乘在第 1 小时发车的列车。第 2 趟列车运行需要 3/1 = 3 小时。
- 由于是在整数时间到达，可以立即换乘在第 4 小时发车的列车。第 3 趟列车运行需要 2/1 = 2 小时。
- 你将会恰好在第 6 小时到达。
示例 2：
输入：dist = [1,3,2], hour = 2.7
输出：3
解释：速度为 3 时：
- 第 1 趟列车运行需要 1/3 = 0.33333 小时。
- 由于不是在整数时间到达，故需要等待至第 1 小时才能搭乘列车。第 2 趟列车运行需要 3/3 = 1 小时。
- 由于是在整数时间到达，可以立即换乘在第 2 小时发车的列车。第 3 趟列车运行需要 2/3 = 0.66667 小时。
- 你将会在第 2.66667 小时到达。
示例 3：
输入：dist = [1,3,2], hour = 1.9
输出：-1
解释：不可能准时到达，因为第 3 趟列车最早是在第 2 小时发车。
提示：
n == dist.length
1 <= n <= 105
1 <= dist[i] <= 105
1 <= hour <= 109
hours 中，小数点后最多存在两位数字
题解：
方法：数学 二分查找
class Solution { public int minSpeedOnTime(int[] dist, double hour) { int n = dist.length; long h100 = Math.round(hour * 100); // 下面不会用到任何浮点数 long delta = h100 - (n - 1) * 100; if (delta <= 0) { // 无法到达终点 return -1; } int maxDist = 0; long sumDist = 0; for (int d : dist) { maxDist = Math.max(maxDist, d); sumDist += d; } if (h100 <= n * 100) { // 特判 // 见题解中的公式 return Math.max(maxDist, (int) ((dist[n - 1] * 100 - 1) / delta + 1)); } int left = (int) ((sumDist * 100 - 1) / h100); // 也可以初始化成 0（简单写法） int h = (int) (h100 / (n * 100)); int right = (maxDist - 1) / h + 1; // 也可以初始化成 maxDist（简单写法） while (left + 1 < right) { int mid = (left + right) >>> 1; if (check(mid, dist, h100)) { right = mid; } else { left = mid; } } return right; } private boolean check(int v, int[] dist, long h100) { int n = dist.length; long t = 0; for (int i = 0; i < n - 1; i++) { t += (dist[i] - 1) / v + 1; } return (t * v + dist[n - 1]) * 100 <= h100 * v; } }
3.规定时间内到达终点的最小花费
题目链接：1928. 规定时间内到达终点的最小花费
一个国家有 n 个城市，城市编号为 0 到 n - 1 ，题目保证 所有城市 都由双向道路 连接在一起 。道路由二维整数数组 edges 表示，其中 edges[i] = [xi, yi, timei] 表示城市 xi 和 yi 之间有一条双向道路，耗费时间为 timei 分钟。两个城市之间可能会有多条耗费时间不同的道路，但是不会有道路两头连接着同一座城市。
每次经过一个城市时，你需要付通行费。通行费用一个长度为 n 且下标从 0 开始的整数数组 passingFees 表示，其中 passingFees[j] 是你经过城市 j 需要支付的费用。
一开始，你在城市 0 ，你想要在 maxTime 分钟以内 （包含 maxTime 分钟）到达城市 n - 1 。旅行的 费用 为你经过的所有城市 通行费之和 （包括 起点和终点城市的通行费）。
给你 maxTime，edges 和 passingFees ，请你返回完成旅行的 最小费用 ，如果无法在 maxTime 分钟以内完成旅行，请你返回 -1 。
示例 1：
输入：maxTime = 30, edges =
[[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]], passingFees =
[5,1,2,20,20,3]
输出：11
解释：最优路径为 0 -> 1 -> 2 -> 5 ，总共需要耗费 30 分钟，需要支付 11 的通行费。
示例 2：
输入：maxTime = 29, edges =
[[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]], passingFees =
[5,1,2,20,20,3]
输出：48
解释：最优路径为 0 -> 3 -> 4 -> 5 ，总共需要耗费 26 分钟，需要支付 48 的通行费。
你不能选择路径 0 -> 1 -> 2 -> 5 ，因为这条路径耗费的时间太长。
示例 3：
输入：maxTime = 25, edges =
[[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]], passingFees =
[5,1,2,20,20,3]
输出：-1
解释：无法在 25 分钟以内从城市 0 到达城市 5 。
提示：
1 <= maxTime <= 1000
n == passingFees.length
2 <= n <= 1000
n - 1 <= edges.length <= 1000
0 <= xi, yi <= n - 1
1 <= timei <= 1000
1 <= passingFees[j] <= 1000
图中两个节点之间可能有多条路径。
图中不含有自环。
题解：
方法：动态规划
class Solution { public int minCost(int maxTime, int[][] edges, int[] passingFees) { int n = passingFees.length; List<int[]>[] graph = new ArrayList[n]; // 用邻接表存储图 Arrays.setAll(graph, i -> new ArrayList<>()); for (int[] edge : edges) { int u = edge[0], v = edge[1], time = edge[2]; graph[u].add(new int[]{v, time}); // 添加边 u -> v graph[v].add(new int[]{u, time}); // 添加边 v -> u } int[][] dist = new int[n][maxTime + 1]; // 初始化距离数组 for (int[] row : dist) { Arrays.fill(row, Integer.MAX_VALUE); } dist[0][0] = passingFees[0]; // 起点费用 PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0])); pq.offer(new int[]{dist[0][0], 0, 0}); // (最小费用, 当前节点, 累计时间) while (!pq.isEmpty()) { int cost = pq.peek()[0]; int city = pq.peek()[1]; int curTime = pq.peek()[2]; pq.poll(); for (int[] neighbor : graph[city]) { int nextCity = neighbor[0]; int edgeTime = neighbor[1]; int newCost = cost + passingFees[nextCity]; // 通行费 int newTime = curTime + edgeTime; // 总时间 if (newTime <= maxTime && newCost < dist[nextCity][newTime]) { dist[nextCity][newTime] = newCost; pq.offer(new int[]{newCost, nextCity, newTime}); } } } int res = Integer.MAX_VALUE; for (int i = 0; i <= maxTime; i++) { res = Math.min(res, dist[n - 1][i]); } return res == Integer.MAX_VALUE ? -1 : res; } }
4.飞机座位分配概率
题目链接：1227. 飞机座位分配概率
有 n 位乘客即将登机，飞机正好有 n 个座位。第一位乘客的票丢了，他随便选了一个座位坐下。
剩下的乘客将会：
如果他们自己的座位还空着，就坐到自己的座位上，
当他们自己的座位被占用时，随机选择其他座位
第 n 位乘客坐在自己的座位上的概率是多少？
示例 1：
输入：n = 1
输出：1.00000
解释：第一个人只会坐在自己的位置上。
示例 2：
输入: n = 2
输出: 0.50000
解释：在第一个人选好座位坐下后，第二个人坐在自己的座位上的概率是 0.5。
提示：
1 <= n <= 10^5
题解：
方法：动态规划
class Solution { public double nthPersonGetsNthSeat(int n) { return n == 1 ? 1 : 0.5; } }
5.完成旅途的最少时间
题目链接：2187. 完成旅途的最少时间
给你一个数组 time ，其中 time[i] 表示第 i 辆公交车完成 一趟旅途 所需要花费的时间。
每辆公交车可以 连续 完成多趟旅途，也就是说，一辆公交车当前旅途完成后，可以 立马开始 下一趟旅途。每辆公交车 独立 运行，也就是说可以同时有多辆公交车在运行且互不影响。
给你一个整数 totalTrips ，表示所有公交车 总共 需要完成的旅途数目。请你返回完成 至少 totalTrips 趟旅途需要花费的 最少 时间。
示例 1：
输入：time = [1,2,3], totalTrips = 5
输出：3
解释：
- 时刻 t = 1 ，每辆公交车完成的旅途数分别为 [1,0,0] 。
已完成的总旅途数为 1 + 0 + 0 = 1 。- 时刻 t = 2 ，每辆公交车完成的旅途数分别为 [2,1,0] 。
已完成的总旅途数为 2 + 1 + 0 = 3 。- 时刻 t = 3 ，每辆公交车完成的旅途数分别为 [3,1,1] 。
已完成的总旅途数为 3 + 1 + 1 = 5 。所以总共完成至少 5 趟旅途的最少时间为 3 。
示例 2：
输入：time = [2], totalTrips = 1
输出：2
解释：
只有一辆公交车，它将在时刻 t = 2 完成第一趟旅途。
所以完成 1 趟旅途的最少时间为 2 。
提示：
1 <= time.length <= 105
1 <= time[i], totalTrips <= 107
题解：
方法：二分查找
class Solution { public long minimumTime(int[] time, int totalTrips) { int minT = Integer.MAX_VALUE; int maxT = 0; for (int t : time) { minT = Math.min(minT, t); maxT = Math.max(maxT, t); } int avg = (totalTrips - 1) / time.length + 1; // 循环不变量：check(left) 恒为 false long left = (long) minT * avg - 1; // 循环不变量：check(right) 恒为 true long right = Math.min((long) maxT * avg, (long) minT * totalTrips); // 开区间 (left, right) 不为空 while (left + 1 < right) { long mid = (left + right) >>> 1; if (check(mid, time, totalTrips)) { // 缩小二分区间为 (left, mid) right = mid; } else { // 缩小二分区间为 (mid, right) left = mid; } } // 此时 left 等于 right-1 // check(left) = false 且 check(right) = true，所以答案是 right return right; // 最小的 true } private boolean check(long x, int[] time, int totalTrips) { long sum = 0; for (int t : time) { sum += x / t; if (sum >= totalTrips) { return true; } } return false; } }
6.加油站
题目链接：134. 加油站
在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。
示例 1:
输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。
示例 2:
输入: gas = [2,3,4], cost = [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。
提示:
gas.length == n
cost.length == n
1 <= n <= 105
0 <= gas[i], cost[i] <= 104
题解：
方法：贪心 图 数组
class Solution { public int canCompleteCircuit(int[] gas, int[] cost) { int ans = 0; int minS = 0; // 最小油量 int s = 0; // 油量 for (int i = 0; i < gas.length; i++) { s += gas[i] - cost[i]; // 在 i 处加油，然后从 i 到 i+1 if (s < minS) { minS = s; // 更新最小油量 ans = i + 1; // 注意 s 减去 cost[i] 之后，汽车在 i+1 而不是 i } } // 循环结束后，s 即为 gas 之和减去 cost 之和 return s < 0 ? -1 : ans; } }
