当前位置： 首页 > news >正文

力扣题解815

news 2024/9/25 1:21:14

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

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

题目描述（困难）​：

公交路线

给你一个数组 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)。


http://www.mrgr.cn/news/29064.html

相关文章：

  • 星火AI-智能PPT生成 API 文档
  • Python 课程15-PyTorch
  • SAP到底是谁的系统？business or IT?
  • IDEA 2024.3 EAP新特征早览！
  • 电脑的固态硬盘
  • 53 最大子数组和
  • 【FreeRL】Rainbow_DQN的实现和测试
  • AI教你学Python ：详解Python元组与集合、字典基础和字符串操作（补充）
  • 学成在线练习（HTML+CSS)
  • Spring 源码解读：手动实现Environment抽象与配置属性
  • 【前端】prop传值的用法
  • 等保测评：企业如何选择合适的测评机构
  • Vue特性
  • C++11新增特性：lambda表达式、function包装器、bind绑定
  • Python 爬虫入门 - Request 静态页面数据获取
  • 《微信小程序实战（2） · 组件封装》
  • ubuntu虚拟机装载共享文件夹导致的诡异错误
  • 太阳能光伏板航拍红外图像缺陷分类数据集
  • funny lidar slam
  • 前端基于Rust实现的Wasm进行图片压缩的技术文档