🌟欢迎来到 我的博客 —— 探索技术的无限可能！
16.公交站间的距离
题目链接：1184. 公交站间的距离
环形公交路线上有 n 个站，按次序从 0 到 n - 1 进行编号。我们已知每一对相邻公交站之间的距离，distance[i] 表示编号为 i 的车站和编号为 (i + 1) % n 的车站之间的距离。
环线上的公交车都可以按顺时针和逆时针的方向行驶。
返回乘客从出发点 start 到目的地 destination 之间的最短距离。
示例 1：
输入：distance = [1,2,3,4], start = 0, destination = 1
输出：1
解释：公交站 0 和 1 之间的距离是 1 或 9，最小值是 1。
示例 2：
输入：distance = [1,2,3,4], start = 0, destination = 2
输出：3
解释：公交站 0 和 2 之间的距离是 3 或 7，最小值是 3。
示例 3：
输入：distance = [1,2,3,4], start = 0, destination = 3
输出：4
解释：公交站 0 和 3 之间的距离是 6 或 4，最小值是 4。
提示：
1 <= n <= 10^4
distance.length == n
0 <= start, destination < n
0 <= distance[i] <= 10^4
题解：
方法：遍历
class Solution { public int distanceBetweenBusStops(int[] distance, int s, int t) { if (s > t) { // swap(s, t) int tmp = s; s = t; t = tmp; } int d1 = 0; int d2 = 0; for (int i = 0; i < distance.length; i++) { if (s <= i && i < t) { d1 += distance[i]; } else { d2 += distance[i]; } } return Math.min(d1, d2); } }
17.公交路线
题目链接：815. 公交路线
给你一个数组 routes ，表示一系列公交线路，其中每个 routes[i] 表示一条公交线路，第 i 辆公交车将会在上面循环行驶。
例如，路线 routes[0] = [1, 5, 7] 表示第 0 辆公交车会一直按序列 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> … 这样的车站路线行驶。
现在从 source 车站出发（初始时不在公交车上），要前往 target 车站。 期间仅可乘坐公交车。
求出 最少乘坐的公交车数量 。如果不可能到达终点车站，返回 -1 。
示例 1：
输入：routes = [[1,2,7],[3,6,7]], source = 1, target = 6
输出：2
解释：最优策略是先乘坐第一辆公交车到达车站 7 , 然后换乘第二辆公交车到车站 6 。
示例 2：
输入：routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15,
target = 12
输出：-1
提示：
1 <= routes.length <= 500.
1 <= routes[i].length <= 105
routes[i] 中的所有值 互不相同
sum(routes[i].length) <= 105
0 <= routes[i][j] < 106
0 <= source, target < 106
题解：
方法：BFS
class Solution { public int numBusesToDestination(int[][] routes, int source, int target) { if (source == target) { return 0; } // 使用 HashMap 构建站点到公交线路的映射 Map<Integer, List<Integer>> g = new HashMap<>(); for (int i = 0; i < routes.length; i++) { for (int stop : routes[i]) { g.computeIfAbsent(stop, k -> new ArrayList<>()).add(i); } } // 如果 source 或 target 不在站点映射中，返回 -1 if (!g.containsKey(source) || !g.containsKey(target)) { return -1; } // 初始化队列和访问集合 Deque<int[]> q = new ArrayDeque<>(); Set<Integer> visBus = new HashSet<>(); Set<Integer> visStop = new HashSet<>(); q.offer(new int[] {source, 0}); visStop.add(source); // 开始广度优先搜索 while (!q.isEmpty()) { int[] current = q.poll(); int stop = current[0], busCount = current[1]; // 如果当前站点是目标站点，返回所需的公交次数 if (stop == target) { return busCount; } // 遍历经过当前站点的所有公交线路 for (int bus : g.get(stop)) { if (visBus.add(bus)) { // 遍历该线路上的所有站点 for (int nextStop : routes[bus]) { if (visStop.add(nextStop)) { q.offer(new int[] {nextStop, busCount + 1}); } } } } } return -1; // 如果无法到达目标站点，返回 -1 } }
18.坐上公交的最晚时间
题目链接：2332. 坐上公交的最晚时间
给你一个下标从 0 开始长度为 n 的整数数组 buses ，其中 buses[i] 表示第 i 辆公交车的出发时间。同时给你一个下标从 0 开始长度为 m 的整数数组 passengers ，其中 passengers[j] 表示第 j 位乘客的到达时间。所有公交车出发的时间互不相同，所有乘客到达的时间也互不相同。
给你一个整数 capacity ，表示每辆公交车 最多 能容纳的乘客数目。
每位乘客都会搭乘下一辆有座位的公交车。如果你在 y 时刻到达，公交在 x 时刻出发，满足 y <= x 且公交没有满，那么你可以搭乘这一辆公交。最早 到达的乘客优先上车。
返回你可以搭乘公交车的最晚到达公交站时间。你 不能 跟别的乘客同时刻到达。
注意：数组 buses 和 passengers 不一定是有序的。
示例 1：
输入：buses = [10,20], passengers = [2,17,18,19], capacity = 2
输出：16
解释：
第 1 辆公交车载着第 1 位乘客。
第 2 辆公交车载着你和第 2 位乘客。
注意你不能跟其他乘客同一时间到达，所以你必须在第二位乘客之前到达。
示例 2：
输入：buses = [20,30,10], passengers = [19,13,26,4,25,11,21], capacity =
2
输出：20
解释：
第 1 辆公交车载着第 4 位乘客。
第 2 辆公交车载着第 6 位和第 2 位乘客。
第 3 辆公交车载着第 1 位乘客和你。
提示：
n == buses.length
m == passengers.length
1 <= n, m, capacity <= 105
2 <= buses[i], passengers[i] <= 109
buses 中的元素 互不相同 。
passengers 中的元素 互不相同 。
题解：
方法：模拟
class Solution { public int latestTimeCatchTheBus(int[] buses, int[] passengers, int capacity) { Arrays.sort(buses); Arrays.sort(passengers); int j = 0, c = 0; for (int t : buses) { c = capacity; while (c > 0 && j < passengers.length && passengers[j] <= t) { --c; ++j; } } --j; int ans = c > 0 ? buses[buses.length - 1] : passengers[j]; while (j >= 0 && ans == passengers[j]) { --ans; --j; } return ans; } }
19.最长的字母序连续子字符串的长度
字母序连续字符串 是由字母表中连续字母组成的字符串。换句话说，字符串 “abcdefghijklmnopqrstuvwxyz” 的任意子字符串都是 字母序连续字符串 。
例如，“abc” 是一个字母序连续字符串，而 “acb” 和 “za” 不是。
给你一个仅由小写英文字母组成的字符串 s ，返回其 最长 的 字母序连续子字符串 的长度。
示例 1：
输入：s = “abacaba”
输出：2
解释：共有 4 个不同的字母序连续子字符串 “a”、“b”、“c” 和 “ab” 。
“ab” 是最长的字母序连续子字符串。
示例 2：
输入：s = “abcde”
输出：5
解释：“abcde” 是最长的字母序连续子字符串。
提示：
1 <= s.length <= 105
s 由小写英文字母组成
题解：
方法：遍历
class Solution { public int longestContinuousSubstring(String S) { char[] s = S.toCharArray(); int ans = 1; int cnt = 1; for (int i = 1; i < s.length; i++) { if (s[i - 1] + 1 == s[i]) { ans = Math.max(ans, ++cnt); } else { cnt = 1; } } return ans; } }
20.统计特殊整数
题目链接：2376. 统计特殊整数
如果一个正整数每一个数位都是 互不相同 的，我们称它是 特殊整数 。
给你一个 正 整数 n ，请你返回区间 [1, n] 之间特殊整数的数目。
示例 1：
输入：n = 20
输出：19
解释：1 到 20 之间所有整数除了 11 以外都是特殊整数。所以总共有 19 个特殊整数。
示例 2：
输入：n = 5
输出：5
解释：1 到 5 所有整数都是特殊整数。
示例 3：
输入：n = 135
输出：110
解释：从 1 到 135 总共有 110 个整数是特殊整数。
不特殊的部分数字为：22 ，114 和 131 。
提示：
1 <= n <= 2 * 109
题解：
方法：状态压缩 + 数位 DP
class Solution { private char[] s; private Integer[][] f; public int countSpecialNumbers(int n) { s = String.valueOf(n).toCharArray(); f = new Integer[s.length][1 << 10]; return dfs(0, 0, true, true); } private int dfs(int i, int mask, boolean lead, boolean limit) { if (i >= s.length) { return lead ? 0 : 1; } if (!limit && !lead && f[i][mask] != null) { return f[i][mask]; } int up = limit ? s[i] - '0' : 9; int ans = 0; for (int j = 0; j <= up; ++j) { if ((mask >> j & 1) == 1) { continue; } if (lead && j == 0) { ans += dfs(i + 1, mask, true, limit && j == up); } else { ans += dfs(i + 1, mask | (1 << j), false, limit && j == up); } } if (!limit && !lead) { f[i][mask] = ans; } return ans; } }
21.边积分最高的节点
题目链接：2374. 边积分最高的节点
给你一个有向图，图中有 n 个节点，节点编号从 0 到 n - 1 ，其中每个节点都 恰有一条 出边。
图由一个下标从 0 开始、长度为 n 的整数数组 edges 表示，其中 edges[i] 表示存在一条从节点 i 到节点 edges[i] 的 有向 边。
节点 i 的 边积分 定义为：所有存在一条指向节点 i 的边的节点的 编号 总和。
返回 边积分 最高的节点。如果多个节点的 边积分 相同，返回编号 最小 的那个。
示例 1：
输入：edges = [1,0,0,0,0,7,7,5]
输出：7
解释：
- 节点 1、2、3 和 4 都有指向节点 0 的边，节点 0 的边积分等于 1 + 2 + 3 + 4 = 10 。
- 节点 0 有一条指向节点 1 的边，节点 1 的边积分等于 0 。
- 节点 7 有一条指向节点 5 的边，节点 5 的边积分等于 7 。
- 节点 5 和 6 都有指向节点 7 的边，节点 7 的边积分等于 5 + 6 = 11 。
节点 7 的边积分最高，所以返回 7 。
示例 2：
输入：edges = [2,0,0,2]
输出：0
解释：
- 节点 1 和 2 都有指向节点 0 的边，节点 0 的边积分等于 1 + 2 = 3 。
- 节点 0 和 3 都有指向节点 2 的边，节点 2 的边积分等于 0 + 3 = 3 。
节点 0 和 2 的边积分都是 3 。由于节点 0 的编号更小，返回 0 。
提示：
n == edges.length
2 <= n <= 105
0 <= edges[i] < n
edges[i] != i
题解：
方法：一次遍历
class Solution { public int edgeScore(int[] edges) { int ans = 0; long[] score = new long[edges.length]; for (int i = 0; i < edges.length; i++) { int to = edges[i]; score[to] += i; if (score[to] > score[ans] || score[to] == score[ans] && to < ans) { ans = to; } } return ans; } }
22.找到小镇的法官
题目链接：997. 找到小镇的法官
小镇里有 n 个人，按从 1 到 n 的顺序编号。传言称，这些人中有一个暗地里是小镇法官。
如果小镇法官真的存在，那么：
小镇法官不会信任任何人。
每个人（除了小镇法官）都信任这位小镇法官。
只有一个人同时满足属性 1 和属性 2 。
给你一个数组 trust ，其中 trust[i] = [ai, bi] 表示编号为 ai 的人信任编号为 bi 的人。
如果小镇法官存在并且可以确定他的身份，请返回该法官的编号；否则，返回 -1 。
示例 1：
输入：n = 2, trust = [[1,2]]
输出：2
示例 2：
输入：n = 3, trust = [[1,3],[2,3]]
输出：3
示例 3：
输入：n = 3, trust = [[1,3],[2,3],[3,1]]
输出：-1
提示：
1 <= n <= 1000
0 <= trust.length <= 104
trust[i].length == 2
trust 中的所有trust[i] = [ai, bi] 互不相同
ai != bi
1 <= ai, bi <= n
题解：
方法：计数
class Solution { public int findJudge(int n, int[][] trust) { int[] cnt1 = new int[n + 1]; int[] cnt2 = new int[n + 1]; for (var t : trust) { int a = t[0], b = t[1]; ++cnt1[a]; ++cnt2[b]; } for (int i = 1; i <= n; ++i) { if (cnt1[i] == 0 && cnt2[i] == n - 1) { return i; } } return -1; } }
