brezezee

公交路线

给你一个数组 routes ，表示一系列公交线路，其中每个 routes[i] 表示一条公交线路，第 i 辆公交车将会在上面循环行驶。

例如，路线 routes[0] = [1, 5, 7] 表示第 0 辆公交车会一直按序列 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> … 这样的车站路线行驶。
现在从 source 车站出发（初始时不在公交车上），要前往 target 车站。 期间仅可乘坐公交车。

求出 最少乘坐的公交车数量 。如果不可能到达终点车站，返回 -1 。

class Solution {
public:
    int numBusesToDestination(vector<vector<int>>& routes, int S, int T) {
        // 计算从一个站点到第i辆公交需要转几趟车，公交通过这些站点联系起来
        if (S == T) return 0;
        int n = routes.size(); // 车的数量
        unordered_map<int, vector<int>> graph;
        for (int i = 0; i < n; ++ i) {
            for (int station : routes[i]) { // 第i辆车的路线
                graph[station].push_back(i); // 站点 可到 乘坐该公交
            }
        }

        // 层序遍历，从站点开始，枚举它可乘坐的公交，再得到公交可到的站点，再枚举可乘公交
        queue<int> q;
        q.push(S);
        vector<int> st(n + 1);
        
        int dist = 0;

        while (q.size()) {
            // 层序遍历， 更新每层的信息（层数、层中点的数量）
            ++ dist;
            int layer = q.size();
            while (layer --) {
                int sta = q.front();q.pop();  // 将该层顶点出队
                
                for (int bus : graph[sta]) {  // 枚举可乘公交
                    if (st[bus]) continue;
                    st[bus] = 1;
                    for (int cur_sta : routes[bus]) {
                        if (cur_sta == T) return dist;
                        q.push(cur_sta);                
                    }
                }
            }
        }   
        return -1;
    }
};

经纬度切分

将球体按经纬度切割，边上的经度和纬度可能不会交叉 ，问一组切割后的块数

不同子串的数量

不同子串定义为子串中的字符全部不一样，且不同的下标认为是不同的字符，即aab中有两个ab是满足的。

排列组合问题，将每个字符出现的次数统计出来，答案就是次数+1的累乘。