[LeetCode] 815. Bus Routes

cyixlq 发布于2019-08-16 13:54 / 1578人阅读

Problem

We have a list of bus routes. Each routes[i] is a bus route that the i-th bus repeats forever. For example if routes[0] = [1, 5, 7], this means that the first bus (0-th indexed) travels in the sequence 1->5->7->1->5->7->1->... forever.

We start at bus stop S (initially not on a bus), and we want to go to bus stop T. Travelling by buses only, what is the least number of buses we must take to reach our destination? Return -1 if it is not possible.

Example:

Input: 
routes = [[1, 2, 7], [3, 6, 7]]
S = 1
T = 6
Output: 2
Explanation: 
The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.

Note:

1 <= routes.length <= 500.
1 <= routes[i].length <= 500.
0 <= routes[i][j] < 10 ^ 6.

Solution

class Solution {
    public int numBusesToDestination(int[][] routes, int S, int T) {
        if (S == T) return 0;
        
        //pre-processing: save > for BFS
        Map> map = new HashMap<>();
        for (int i = 0; i < routes.length; i++) {
            for (int stop: routes[i]) {
                if (!map.containsKey(stop)) map.put(stop, new ArrayList<>());
                map.get(stop).add(i);
            }
        }
        
        if (!map.containsKey(S) || !map.containsKey(T)) return -1;
        
        Set visited = new HashSet<>(); //to store visited routes
        Deque queue = new ArrayDeque<>();
        queue.offer(S);
        
        int transitions = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            transitions++;
            for (int i = 0; i < size; i++) {
                int curStop = queue.poll();
                List buses = map.get(curStop);
                for (int bus: buses) {
                    if (visited.contains(bus)) continue;
                    visited.add(bus);
                    for (int stop: routes[bus]) {
                        if (stop == T) return transitions;
                        else queue.offer(stop);
                    }
                }
            }
        }
        
        return -1;
    }
}

云服务器 GPU云服务器 Routes LeetCode Bus d bus

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/72547.html

SpringCloud微服务实战笔记

摘要：服务提供者的运行机制用了双层结构来维护注册的服务信息，第一层为服务的名称，第二层为服务的实例名称。服务注册中心的运行机制为了防止服务的异常下线，会周期性的清理列表中未续约的服务。负载均衡器的基本功能维护该服务下的所有节点列表。 Spring Boot Spring Boot有什么作用 Spring Boot通过自动化的配置简化Spring原有的样板化的配置。 Spring Boo...

chunquedong 2019-08-16 10:55 评论0 收藏0
Vue组件——子组件向父组件传递数据以及路由

摘要：自定义事件我们知道，父组件使用传递数据给子组件。另外，父组件可以在使用子组件的地方直接用来监听子组件触发的事件。为了让组件可以组合，我们需要一种方式来混合父组件的内容与子组件自己的模板。自定义事件我们知道，父组件使用 prop 传递数据给子组件。但子组件怎么跟父组件通信呢？这个时候 Vue 的自定义事件系统就派得上用场了。使用绑定自定义事件v-on 每个 Vue 实例都实现了事...

CoorChice 2019-08-01 17:58 评论0 收藏0
Vue 后台模板 [Vue admin] SanJi Boot Admin Iview

摘要：导读很久没有写文章了最近一直在忙之前一直想着可以把项目中的页面使用进行重写前几天算是阶段性的完成了这个计划后期会随着的模块不断增多对其进行对应的升级与扩展简介项目源码已托管到码云上使用技术实现了什么功能基于进行登陆时的认证支持跨域需要后台配导读：很久没有写文章了,最近一直在忙,之前一直想着可以把SanJi Boot Security项目中的页面使用 Vue+webpack 进行重写...

546669204 2019-08-22 13:45 评论0 收藏0
Vue2.0 学习笔记

摘要：父子组件通信父组件通过向下传递数据给子组件，子组件通过给父组件发送消息。是一个对象而不是字符串数组时，它包含验证要求。状态管理由于多个状态分散的跨越在许多组件和交互间，大型应用的复杂度也随之增长。提供了，可以通过文档学习。什么是vue vue是一个前端框架，主要两个特点：数据绑定、组件化。安装环境根据教程安装环境：node.js、npm、webpack、vue-cli主要的命...

cgh1999520 2019-08-21 11:25 评论0 收藏0
前端知识点总结——VUE（持续更新中）

摘要：前端知识点总结持续更新中框架和库的区别框架有着自己的语法特点都有对应的各个模块库专注于一点框架的好处提到代码的质量，开发速度提高代码的复用率降低模块之间的耦合度高内聚低耦合思维模式的转换从操作的思维模式切换到以数据为主概述是一个渐进式的构建前端知识点总结——VUE（持续更新中） 1.框架和库的区别：框架：framework 有着自己的语法特点、都有对应的各个模块库 library ...

big_cat 2019-08-22 14:50 评论0 收藏0