力扣题解815

大家好，欢迎来到无限大的频道。祝大家中秋节快乐​。

今日继续给大家带来力扣题解。

题目描述（困难）​：

公交路线

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

• 例如，路线 routes[0] = [1, 5, 7] 表示第 0 辆公交车会一直按序列 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... 这样的车站路线行驶。

现在从 source 车站出发（初始时不在公交车上），要前往 target 车站。 期间仅可乘坐公交车。

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

解题思路

1. 图模型：

   • 将公交线路和站点视为图的节点和边。每个站点是一个节点，每条公交线路可以看作是连接多个站点的边。

   • 我们需要找出从 source 站点到 target 站点的最短路径（最少乘坐的公交车数量）。最短路径我们采用BFS算法

2. 哈希映射：

   • 使用哈希映射（在这里是链表实现的数组）来存储每个站点对应的公交线路。这样可以快速查找经过某个站点的所有公交线路。

3. 广度优先搜索（BFS）：

   • 使用 BFS 来遍历图，因为 BFS 能够找到最短路径。

   • BFS 从起始站点开始，逐层访问所有相邻的节点（公交线路），直到找到目标站点。

详细步骤

1. 检查起始和目标站点：

   • 如果 source 和 target 相同，直接返回 0，因为不需要乘坐公交车。

2. 构建哈希映射：

   • 使用 createHashMap 创建一个大小为 MAX_STOPS 的哈希映射数组 stop_to_routes。

   • 遍历每条线路，将每个站点映射到经过该站点的线路上。

3. BFS 初始化：

   • 创建一个队列 queue 来存储待访问的公交线路。

   • 使用 visitedRoutes 数组记录已访问的线路，使用 visitedStops 数组记录已访问的站点。

   • 将所有经过 source 的公交线路入队，并标记为已访问。

4. BFS 遍历：

   • 记录当前层的大小 levelSize，并增加深度 depth。

   • 遍历当前层的所有线路：

   • 如果当前站点是 target，则返回当前深度（乘坐的公交车数量）。

   • 如果当前站点未被访问，标记为已访问，并将该站点所有经过的未访问线路入队。

   • 对于每条线路，遍历其经过的所有站点：

   • 使用 while 循环进行 BFS，只要队列不为空：

5. 资源释放：

   • 如果遍历完所有线路仍未找到目标站点，释放所有动态分配的内存并返回 -1。

关键部分解释

• 哈希映射的使用：

  • 通过哈希映射，将站点映射到线路，能够快速获取经过某个站点的所有公交线路，避免了重复遍历，提高了效率。

• BFS 的实现：

  • BFS 的层次遍历特性确保了在找到目标站点时，返回的深度是最小的，即乘坐的公交车数量是最少的。

代码参考​：

// 定义结构用于保存每个站点经过的路线
typedef struct Node {
    int data;
    struct Node* next;
} Node;
​
Node** createHashMap(int size) {
    // 用于初始化动态大小的哈希表
    Node** map = (Node**)malloc(size * sizeof(Node*));
    for (int i = 0; i < size; i++) {
        map[i] = NULL;
    }
    return map;
}
​
void insertHashMap(Node** map, int key, int value) {
    // 将一个值插入到哈希表中
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = map[key];
    map[key] = newNode;
}
​
typedef struct {
    int *data;
    int front;
    int rear;
    int size;
    int capacity;
} Queue;
​
Queue* createQueue(int capacity) {
    // 初始化队列结构
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->capacity = capacity;
    queue->front = 0;
    queue->size = 0;
    queue->rear = capacity - 1;
    queue->data = (int*)malloc(capacity * sizeof(int));
    return queue;
}
​
int isFull(Queue* queue) {
    // 检查队列是否已满
    return (queue->size == queue->capacity);
}
​
int isEmpty(Queue* queue) {
    // 检查队列是否为空
    return (queue->size == 0);
}
​
void enqueue(Queue* queue, int item) {
    // 向队列中加入元素
    if (isFull(queue))
        return;
    queue->rear = (queue->rear + 1) % queue->capacity;
    queue->data[queue->rear] = item;
    queue->size = queue->size + 1;
}
​
int dequeue(Queue* queue) {
    // 从队列中移除元素
    if (isEmpty(queue))
        return -1;
    int item = queue->data[queue->front];
    queue->front = (queue->front + 1) % queue->capacity;
    queue->size = queue->size - 1;
    return item;
}
​
int numBusesToDestination(int** routes, int routesSize, int* routesColSize, int source, int target) {
    if (source == target) return 0;
​
    // Step 1: 使用哈希映射保存站点与线路的对应关系
    const int MAX_STOPS = 1000000;
    Node** stop_to_routes = createHashMap(MAX_STOPS);
    
    for (int i = 0; i < routesSize; i++) {
        for (int j = 0; j < routesColSize[i]; j++) {
            int stop = routes[i][j];
            insertHashMap(stop_to_routes, stop, i);
        }
    }
​
    // BFS初始化
    Queue* queue = createQueue(routesSize);
    int depth = 0;
    int* visitedRoutes = (int*)calloc(routesSize, sizeof(int));
    int* visitedStops = (int*)calloc(MAX_STOPS, sizeof(int));
​
    Node* current = stop_to_routes[source];
    while (current != NULL) {
        enqueue(queue, current->data);
        visitedRoutes[current->data] = 1;
        current = current->next;
    }
​
    while (!isEmpty(queue)) {
        int levelSize = queue->size;
        depth++;
​
        for (int i = 0; i < levelSize; i++) {
            int route = dequeue(queue);
​
            for (int j = 0; j < routesColSize[route]; j++) {
                int stop = routes[route][j];
                if (stop == target) {
                    free(visitedRoutes);
                    free(visitedStops);
                    free(queue->data);
                    free(queue);
                    for (int k = 0; k < MAX_STOPS; k++) {
                        Node* iter = stop_to_routes[k];
                        while (iter) {
                            Node* toFree = iter;
                            iter = iter->next;
                            free(toFree);
                        }
                    }
                    free(stop_to_routes);
​
                    return depth;
                }
                if (!visitedStops[stop]) {
                    visitedStops[stop] = 1;
                    Node* iter = stop_to_routes[stop];
                    while (iter != NULL) {
                        int nextRoute = iter->data;
                        if (!visitedRoutes[nextRoute]) {
                            enqueue(queue, nextRoute);
                            visitedRoutes[nextRoute] = 1;
                        }
                        iter = iter->next;
                    }
                }
            }
        }
    }
​
    // 资源释放
    free(visitedRoutes);
    free(visitedStops);
    free(queue->data);
    free(queue);
    for (int i = 0; i < MAX_STOPS; i++) {
        Node* iter = stop_to_routes[i];
        while (iter) {
            Node* toFree = iter;
            iter = iter->next;
            free(toFree);
        }
    }
    free(stop_to_routes);
​
    return -1;
}

时间复杂度：

• 构建哈希映射: 对于每个站点，将其加入相应的线路列表中。总共需要遍历所有站点，即 O(sum(routesColSize))。

• BFS搜索: 在最坏情况下，需要访问所有站点和所有线路。由于每个站点只会被访问一次，且每个线路也只会被访问一次，时间复杂度为 O(sum(routesColSize))。

• 因此，整体时间复杂度为 O(sum(routesColSize))。

空间复杂度：

• 哈希映射 stop_to_routes: 需要为每个站点存储经过的线路，最坏情况下为 O(sum(routesColSize))。

• 队列: 最多需要存储所有线路，即 O(routesSize)。

• 访问标记数组: visitedRoutes 大小为 O(routesSize)，visitedStops 大小为 O(MAX_STOPS)。

• 因此，整体空间复杂度为 O(sum(routesColSize) + routesSize + MAX_STOPS)。