【LeetCode】传递信息 Java 题解

关注

发布于: 2 小时前

题目描述

小朋友 A 在和 ta 的小伙伴们玩传信息游戏，游戏规则如下：

有 n 名玩家，所有玩家编号分别为 0 ～ n-1，其中小朋友 A 的编号为 0 每个玩家都有固定的若干个可传信息的其他玩家（也可能没有）。传信息的关系是单向的（比如 A 可以向 B 传信息，但 B 不能向 A 传信息）。每轮信息必须需要传递给另一个人，且信息可重复经过同一个人给定总玩家数 n，以及按 [玩家编号,对应可传递玩家编号] 关系组成的二维数组 relation。返回信息从小 A (编号 0 ) 经过 k 轮传递到编号为 n-1 的小伙伴处的方案数；若不能到达，返回 0。

示例 1：
输入：n = 5, relation = [[0,2],[2,1],[3,4],[2,3],[1,4],[2,0],[0,4]], k = 3
输出：3
解释：信息从小 A 编号 0 处开始，经 3 轮传递，到达编号 4。共有 3 种方案，分别是 0->2->0->4， 0->2->1->4， 0->2->3->4。
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/chuan-di-xin-xi著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

这个题目提干比较长，需要认真理解，提取核心信息。提取的关键点如下：求从位置 0 到位置 n - 1 需要 k 步骤的方案数。
理解清楚题目之后，可以用 dfs 的思想来求解。题目与位置有关，需要记录当前节点的位置和下一个节点的位置。

代码

class Solution {    int n, k, ans;    List<List<Integer>> edges;
    public int numWays(int n, int[][] relation, int k) {        ans = 0;        this.n = n;        this.k = k;        edges = new ArrayList<>();        for (int i = 0; i < n; i++) {            edges.add(new ArrayList<Integer>());        }        for (int[] edge : relation) {            int src = edge[0];            int dst = edge[1];            edges.get(src).add(dst);        }        dfs(0, 0);
        return ans;    }
    public void dfs(int index, int steps) {        if (steps == k) {            if (index == n - 1) {                ans++;            }            return;        }
        List<Integer> list = edges.get(index);
        for (int nextIndex : list) {            dfs(nextIndex, steps + 1);        }    }}

复制代码

总结

上述算法的时间复杂度是 O( n ^ k ), 空间复杂度是 O (m + n + k)
坚持每日一题，加油！

发布于: 2 小时前阅读数: 2

原文链接:【http://xie.infoq.cn/article/164696e9a4485629fb1ba29ae】。文章转载请联系作者。

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

【LeetCode】传递信息 Java 题解

题目描述

思路分析

代码

总结

HQ数字卡

评论