• 【LeetCode每日一题】——LCP 07.传递信息


    一【题目类别】

    二【题目难度】

    • 简单

    三【题目编号】

    • LCP 07.传递信息

    四【题目描述】

    • 小朋友 A 在和 ta 的小伙伴们玩传信息游戏,游戏规则如下:
      1. n 名玩家,所有玩家编号分别为 0 ~ n-1,其中小朋友 A 的编号为 0
      2. 每个玩家都有固定的若干个可传信息的其他玩家(也可能没有)。传信息的关系是单向的(比如 A 可以向 B 传信息,但 B 不能向 A 传信息)。
      3. 每轮信息必须需要传递给另一个人,且信息可重复经过同一个人
    • 给定总玩家数 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。
    • 示例 2

      • 输入:n = 3, relation = [[0,2],[2,1]], k = 2
      • 输出:0
      • 解释:信息不能从小 A 处经过 2 轮传递到编号 2

    六【题目限制】

    • 2 <= n <= 10
    • 1 <= k <= 5
    • 1 <= relation.length <= 90, 且 relation[i].length == 2
    • 0 <= relation[i][0],relation[i][1] < n 且 relation[i][0] != relation[i][1]

    七【解题思路】

    • 标准的深度优先搜索的思路,注意两点:
      • 以轮数作为结束的第一个条件,以是否到达目标作为结束的第二个条件
      • 因为题目说明每个节点可以多次访问,所以不需要“访问数组”
    • 不过邻接矩阵的构建需要注意,不同语言的构建方式不同,并且在深度优先搜索中使用邻接矩阵非常频繁,所以一定要掌握
    • 具体细节可以参考下面的代码
    • 最后返回结果即可

    八【时空频度】

    • 时间复杂度: O ( n k ) O(n^k) O(nk) n n n为传入数组的长度, k k k为允许的传递轮数
    • 空间复杂度: O ( n + k ) O(n + k) O(n+k) n n n为传入数组的长度, k k k为允许的传递轮数

    九【代码实现】

    1. Java语言版
    class Solution {
        public int numWays(int n, int[][] relation, int k) {
            // 源和目的
            int src = 0;
            int dest = n - 1;
            // 构建有向图的邻接矩阵
            List<Integer>[] graph = new ArrayList[n];
            for (int i = 0; i < n; i++) {
                graph[i] = new ArrayList<>();
            }
            for (int[] edge : relation) {
                int u = edge[0];
                int v = edge[1];
                graph[u].add(v);
            }
            // 返回结果
            return dfs(src, dest, graph, k);
        }
    
        // 深度优先搜索,计数传递轮次
        private static int dfs(int src, int dest, List<Integer>[] graph, int rounds) {
            if (rounds == 0) {
                return src == dest ? 1 : 0;
            }
            int count = 0;
            for (int neighbor : graph[src]) {
                count += dfs(neighbor, dest, graph, rounds - 1);
            }
            return count;
        }
    }
    
    1. Python语言版
    class Solution:
        def numWays(self, n: int, relation: List[List[int]], k: int) -> int:
            # 源和目的
            src = 0
            dest = n - 1
            # 构建有向图的邻接矩阵
            graph = defaultdict(list)
            for u, v in relation:
                graph[u].append(v)
            
            # 深度优先搜索,计数传递轮次
            def dfs(node, rounds):
                if rounds == 0:
                    return 1 if node == dest else 0
                count = 0
                for neighbor in graph[node]:
                    count += dfs(neighbor, rounds - 1)
                return count
            
            # 返回结果
            return dfs(src, k)
    
    1. C++语言版
    class Solution {
    public:
        int numWays(int n, vector<vector<int>>& relation, int k) {
            // 源和目的
            int src = 0;
            int dest = n - 1;
            // 构建有向图的邻接矩阵
            vector<vector<int>> graph(n);
            for (const auto& edge : relation) {
                int u = edge[0];
                int v = edge[1];
                graph[u].push_back(v);
            }
            // 返回结果
            return dfs(src, dest, graph, k);
        }
    
    private:
        // 深度优先搜索,计数传递轮次
        int dfs(int src, int dest, const vector<vector<int>>& graph, int rounds) {
            if (rounds == 0) {
                return src == dest ? 1 : 0;
            }
            int count = 0;
            for (int neighbor : graph[src]) {
                count += dfs(neighbor, dest, graph, rounds - 1);
            }
            return count;
        }
    };
    

    十【提交结果】

    1. Java语言版
      在这里插入图片描述

    2. Python语言
      在这里插入图片描述

    3. C++语言版
      在这里插入图片描述

  • 相关阅读:
    Spring的Factories机制介绍
    BOA服务器移植
    三、mysqld程序的运行原理及数据库结构
    vue 在beforeRouteEnter中获取 this 和操作 data 中的数据
    步步为营,如何将GOlang引用库的安全漏洞修干净
    138、★很经典的一道题目:LeetCode-42.接雨水
    【ACWing】274. 移动服务
    基于springboot的房屋租赁系统
    (免费分享)基于jsp的CRM客户管理-带论文
    Flutter 08 三棵树(Widgets、Elements和RenderObjects)
  • 原文地址:https://blog.csdn.net/IronmanJay/article/details/143358403