【题解】—— 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 不在站点映射中，返回 -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.最长的字母序连续子字符串的长度

题目链接：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