【题解】—— LeetCode一周小结38

🌟欢迎来到 我的博客 —— 探索技术的无限可能！

🌟博客的简介（文章目录）

---

【题解】—— 每日一道题目栏

---

上接：【题解】—— LeetCode一周小结37

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 不在站点映射中，返回 -1if (!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.最长的字母序连续子字符串的长度

题目链接：2414. 最长的字母序连续子字符串的长度

字母序连续字符串 是由字母表中连续字母组成的字符串。换句话说，字符串 “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;}
}

下接：【题解】—— LeetCode一周小结39

---