LeetCode周记 EP13

字数统计: 2.3k字   |   阅读时长: 9分

前言

这周的bus题挺有意思，学习了。

本周主题：动态规划、组合数学、BFS、优化建图

题目：

Bus Routes

Bus Routes

You are given an array routes representing bus routes where routes[i] is a bus route that the ith bus repeats forever.

For example, if routes[0] = [1, 5, 7], this means that the 0th bus travels in the sequence 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> … forever.
You will start at the bus stop source (You are not on any bus initially), and you want to go to the bus stop target. You can travel between bus stops by buses only.

Return the least number of buses you must take to travel from source to target. Return -1 if it is not possible.

这道题和地图应用中的公交路线计算非常贴合，实用价值很高。题意就是给了若干公交线路和起点终点，求最小换乘策略。

优化建图+BFS

由于求解的目标是最少乘坐的公交车数量，对于同一辆公交车，乘客可以在其路线中的任意车站间无代价地移动，于是我们可以把公交路线当作点。如果两条公交路线有相同车站，则可以在这两条路线间换乘公交车，那么这两条公交路线之间可视作有一条长度为$1$的边。这样建出的图包含的点数即为公交路线的数量，记作$n$。

完成了建图后，我们需要先明确新的图的起点和终点，然后使用广度优先搜索，计算出的起点和终点的最短路径，从而得到最少换乘次数。

注意到原本的起点车站和终点车站可能同时位于多条公交路线上，因此在新图上可能有多个起点和终点。对于这种情况，我们初始可以同时入队多个点，并在广度优先搜索结束后检查到各个终点的最短路径，取其最小值才是最少换乘次数。

实际建图时, 我们有以下两种方案：

  • 方案一：我们直接枚举左右两端点，检查两点对应的两公交路线是否有公共车站。利用哈希表，我们可以将单次比较的时间复杂度优化到均摊 $O(n)$ 。
  • 方案二：我们遍历所有公交路线，记录每一个车站属于哪些公交路线。然后我们遍历每一个车站，如果有多条公交路线经过该点，则在这些公交路线之间连边。

本题中我们采用方案二，据此还可以直接得到起点和终点在新图中对应的点。实际代码中，我们使用哈希映射来实时维护「车站所属公交路线列表」。假设当前枚举到公交路线 $i$ 中的车站 $site$, 此时哈希映射中已记录若干条公交路线经过车站 $site$, 我们只需要让点 $i$ 与这些点公交路线对应的点相连即可。完成了连线后, 我们再将公交路线 $i$ 加入到「车站 $site$ 所属公交路线列表」中。

特别地, 起点和终点相同时, 我们可以直接返回 0 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
    public int numBusesToDestination(int[][] routes, int source, int target) {
        if (source == target) {
            return 0;
        }

        int n = routes.length;
        boolean[][] edge = new boolean[n][n];
        // key:车站, value:班次列表
        Map<Integer, List<Integer>> rec = new HashMap<Integer, List<Integer>>();
        for (int i = 0; i < n; i++) {
            for (int site : routes[i]) {
                List<Integer> list = rec.getOrDefault(site, new ArrayList<Integer>());
                for (int j : list) {
                    edge[i][j] = edge[j][i] = true; // 班次连线
                }
                list.add(i);
                rec.put(site, list);
            }
        }

        int[] dis = new int[n]; // 记录从src到tgt的所有班次换乘数量
        Arrays.fill(dis, -1);
        Queue<Integer> que = new LinkedList<Integer>();
        for (int bus : rec.getOrDefault(source, new ArrayList<Integer>())) {
            dis[bus] = 1; // 起点班次数量为1
            que.offer(bus); // 起点班次入队
        }
        // 广度优先搜索，所有班次每次仅向前探测一次，保证终点第一次被搜索到时路径最短
        while (!que.isEmpty()) {
            int x = que.poll(); // 队头出队
            for (int y = 0; y < n; y++) {
                if (edge[x][y] && dis[y] == -1) {
                    dis[y] = dis[x] + 1;
                    que.offer(y); // 加入队尾
                }
            }
        }
        
        // 从能到终点的班次中筛选出最小距离
        int ret = Integer.MAX_VALUE;
        for (int bus : rec.getOrDefault(target, new ArrayList<Integer>())) {
            if (dis[bus] != -1) {
                ret = Math.min(ret, dis[bus]);
            }
        }
        return ret == Integer.MAX_VALUE ? -1 : ret;
    }
}

Count Special Integers

Count Special Integers

We call a positive integer special if all of its digits are distinct.

Given a positive integer n, return the number of special integers that belong to the interval [1, n].

到手首先考虑记忆化+暴力，用两个数组分别记录当前数字和每个数字的频次来避免重复计算，逐步从1增加到n计算，能过百分之八十，剩下超时。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// author: SilenceZheng66
class Solution {
    int[] arr = new int[10]; // 存放从1到10位的数字
    int[] check = new int[10]; // 计算arr是否有重复元素
    int waterLevel = 0; // 表示当前到达过的最高位数
    public int countSpecialNumbers(int n) {
        int res = 1;
        arr[0]++;
        check[1]++;
        for(int i = 2;i<=n;i++){
            recur(0);
            boolean valid = true;
            for(int x:check){
                if(x>1){
                    valid = false;
                    break;
                }
            }
            if(valid) res++;
        }
        return res;
    }

    public void recur(int p){
        if(arr[p]<9){
            if(waterLevel>=p) check[arr[p]]--;
            else waterLevel++;
            arr[p]++;
            check[arr[p]]++;
        }else{
            arr[p] = 0;
            check[0]++;
            check[9]--;
            recur(p+1);
        }
    }
}

动态规划+组合数学

另一种思路是通过组合数学拼出所有的特殊整数，这样就可以避免遍历所有可能的整数。将小于等于$n$的整数分为两种情况，记$n$十进制表示下位数为$k$：

  1. 位数小于$k$的特殊整数。
  2. 位数等于$k$的特殊整数。

对于位数小于 $k$ 的情况，分别计算位数为 1 到 $k-1$ 的情况下特殊整数的数量。考虑位数为 $k_0\left(k_0<k\right)$的情况。因为 $k_0<k$ ，所以任意放置数位上的数字，都能满足小于等于 $n$ 的条件。只需保证每一数位都互不相同。用组合数学的思路求解特殊整数的数量，从最高位开始考虑，可以有 9 种选择（除 0 外的任何整数），次高位也有 9 种选择（除最高位外的任何整数），接下来的数位的选择则依次减少 1 。把这些选择的可能性全部相乘则是位数为 $k_0$ 的特殊整数的数量。

接下来考虑位数等于 $k$ 的特殊整数。相同位数的数字比较大小，是从最高位开始比较，若不同，则最高位大的数字大；若相同，则比较次高位。次高位的比较原则和最高位一样。因此，我们在计算小于等于 $n$ 的特殊整数时，也需要按照这个原则。函数 $d p(mask, prefixSmaller)$ 用来计算以某些数字组合为前缀的特殊整数的数量。整数 mask 即表示了前叕中使用过的数字，二进制表示下，从最低位开始，第 $i$ 位如果为 1 则表示数字 $i$ 已经被使用过，在接下来的后缀中不能使用。布尔值 prefixSmaller 表示当前的前缀是否小于 $n$ 的前缀，如果是，则接下来的数字可以任意选择。如果不是，即当前的前缀等于 $n$ 的前缀，则接下来的数字只能小于或者等于 $n$ 同数位的数字。最后调用 $d p(0, f a l s e)$ 则为位数等于 $k$ 的特殊整数的数量。

最后把这两部分相加即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    Map<Integer, Integer> memo = new HashMap<Integer, Integer>();

    public int countSpecialNumbers(int n) {
        String nStr = String.valueOf(n);
        int res = 0;
        int prod = 9;
        for (int i = 0; i < nStr.length() - 1; i++) {
            res += prod;
            prod *= 9 - i;
        }
        res += dp(0, false, nStr);
        return res;
    }

    public int dp(int mask, boolean prefixSmaller, String nStr) {
        if (Integer.bitCount(mask) == nStr.length()) {
            return 1;
        }
        int key = mask * 2 + (prefixSmaller ? 1 : 0); // 用参数组合生成key用于记忆化
        if (!memo.containsKey(key)) { // 如果还没计算过，则计算当前参数下的组合数量
            int res = 0; 
            int lowerBound = mask == 0 ? 1 : 0; // 初始最高位时下界为1
            int upperBound = prefixSmaller ? 9 : nStr.charAt(Integer.bitCount(mask)) - '0';
            for (int i = lowerBound; i <= upperBound; i++) {
                if (((mask >> i) & 1) == 0) { // 数字i未被使用过
                    // 把i加入mask列表表示使用过
                    res += dp(mask | (1 << i), prefixSmaller || i < upperBound, nStr); 
                }
            }
            memo.put(key, res); // 在mask先进a后进b的情况下，后续mask先进b后进a的运算可以省略。
        }
        return memo.get(key);
    }
}

题解记录

还有一题有些意思不过写出来了，贴一下我的题解。

参考文献

[1] https://leetcode.cn/problems/count-special-integers/solutions/2916434/tong-ji-te-shu-zheng-shu-by-leetcode-sol-7qai/?envType=daily-question&envId=2024-09-20
[2] https://leetcode.cn/problems/bus-routes/solutions/847860/gong-jiao-lu-xian-by-leetcode-solution-yifz/?envType=daily-question&envId=2024-09-17

后记

首发于 silencezheng.top，转载请注明出处。

赏

谢谢打赏哟！

支付宝
微信

扫一扫，分享到微信

微信分享二维码
本站总访问量次 |

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

SilenceZheng66<br><br>记录所学技术<br>谢谢浏览