刷题笔记25——图论课程表

这篇具有很好参考价值的文章主要介绍了刷题笔记25——图论课程表。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

为了最终理解你所不理解的,你必须经历一条愚昧无知的道路。为了占有你从未占有的东西,你必须经历被剥夺的道路。为了达到你现在所不在的名位,你必须经历那条你不在其中的道路。——艾略特文章来源地址https://www.toymoban.com/news/detail-730625.html

797. 所有可能的路径(已经告知:是有向无环图,所以不需要设置visited)

  • 非常奇妙,我最初的错误是如下,在找到目标节点后直接加入到res中,但是发现结果输出的数量是对的,但是都是空的
  • 可能的原因是:path就算被加入到res中,但是只是加入了地址,后序path的修改还是会影响到res
  • 修改:在加入 res 的时候新建空间,问题解决
		if(n == sz-1){
            res.add(result);
        }
class Solution {
    List<Integer> path = new LinkedList<>();
    List<List<Integer>> res = new LinkedList<List<Integer>>();
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        traverse(graph,0);
        return res;
    }

    void traverse(int[][] graph,int n){
        path.add(n);
        int sz = graph.length;
        if(n == sz-1){
            List<Integer> result = new LinkedList<>(path);
            res.add(result);
        }
        else{
            for(int node:graph[n]){
                traverse(graph,node);
            }
        }
        path.remove(path.size()-1);
    }
}
  • 比如我们写代码 import 包也是一个例子,必须合理设计代码目录结构,否则会出现循环依赖,编译器会报错,所以编译器实际上也使用了类似算法来判断你的代码是否能够成功编译。看到依赖问题,首先想到的就是把问题转化成「有向图」这种数据结构,只要图中存在环,那就说明存在循环依赖。

207. 课程表

  • visited是以整个图为维度判断是否重复遍历,onPath是以路径为维度判断是否有环,区别在于后续遍历的处理。两者不能互相替代。
  • 目前感觉最大的问题就是对数据类型的定义,像graph要用什么类型来存,以及graph如果是两层的话,那么需要对下一层再进行new
  • arraylist和linkedlist都可以用,功能也相近,但是要看具体算法中,是更多索引操作还是增删操作
  • 其余的话就都是照抄板子
List<Integer>[] graph = new LinkedList[numCourses];
for(int i=0;i<numCourses;i++){
	graph[i] = new LinkedList<>();
}
class Solution {
    boolean[] visited;
    boolean[] path;
    boolean isCycle = false;

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Integer>[] graph = generateGraph(numCourses,prerequisites);
        visited = new boolean[numCourses];
        path = new boolean[numCourses];
        for(int i=0;i<numCourses;i++){
            traverse(graph,i);   
        }
        return !isCycle;
    }

    void traverse(List<Integer>[] graph,int n){
        if(path[n]){
            isCycle = true;
        }
        if(visited[n]||isCycle){
            return;
        }
        visited[n] = true;
        path[n] = true;
        for(int node:graph[n]){
            traverse(graph,node);
        }
        path[n] = false;
    }

    List<Integer>[] generateGraph(int numCourses, int[][] prerequisites){
        List<Integer>[] graph = new LinkedList[numCourses];
        for(int i=0;i<numCourses;i++){
            graph[i] = new LinkedList<>();
        }
        for(int i=0;i<prerequisites.length;i++){
            graph[prerequisites[i][1]].add(prerequisites[i][0]);
        }
        return graph;
    }
}

210. 课程表 II (有点像不明白为什么是在后序遍历那块记录路径,可能就是后序的时候,可以保证每个节点的前导节点已经遍历过了)

class Solution {
    boolean[] visited;
    boolean[] path;
    int[] res;
    boolean isCycle = false;
    int i=0;

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<Integer>[] graph = generateGraph(numCourses,prerequisites);
        visited = new boolean[numCourses];
        path = new boolean[numCourses];
        res = new int[numCourses];
        for(int i=0;i<numCourses;i++){
            traverse(graph,i);
        }

        if(!isCycle){
            int[] result = new int[numCourses];
            for(int i=0;i<numCourses;i++){
                result[i] = res[numCourses-i-1];
            }
            return result;
        }else{
            return new int[]{};
        }
        
    }

    void traverse(List<Integer>[] graph,int n){
        if(path[n]){
            isCycle = true;
        }
        if(path[n] || visited[n]){
            return;
        }

        visited[n] = true;
        path[n] = true;
        
        for(int node:graph[n]){
            traverse(graph,node);
        }
        path[n] = false;
        res[i] = n;
        i++;
    }

    List<Integer>[] generateGraph(int numCourses, int[][] prerequisites){
        List<Integer>[] graph = new LinkedList[numCourses];
        for(int i=0;i<numCourses;i++){
            graph[i] = new LinkedList();
        }

        for(int i=0;i<prerequisites.length;i++){
            graph[prerequisites[i][1]].add(prerequisites[i][0]);
        }
        return graph;
    }


}

到了这里,关于刷题笔记25——图论课程表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【LeetCode】210. 课程表 II——拓扑排序

    题目链接:210. 课程表 II 题目描述: 现在你总共有 numCourses 门课需要选,记为 0 到 numCourses - 1。给你一个数组 prerequisites ,其中 prerequisites[i] = [ai, bi] ,表示在选修课程 ai 前 必须 先选修 bi 。 例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示:[0,1] 。 返

    2024年02月09日
    浏览(35)
  • 2023-09-09 LeetCode每日一题(课程表)

    点击跳转到题目位置 你这个学期必须选修 numCourses 门课程,记为 0 到 numCourses - 1 。 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出,其中 prerequisites[i] = [ai, bi] ,表示如果要学习课程 ai 则 必须 先学习课程 bi 。 例如,先修课程对 [0, 1] 表示:想要学

    2024年02月09日
    浏览(51)
  • LeetCode 0630.课程表 III:贪心 + 优先队列

    力扣题目链接:https://leetcode.cn/problems/course-schedule-iii/ 这里有 n 门不同的在线课程,按从 1 到 n  编号。给你一个数组 courses ,其中 courses[i] = [duration i , lastDay i ] 表示第 i 门课将会 持续 上 duration i 天课,并且必须在不晚于 lastDay i 的时候完成。 你的学期从第 1 天开始。且不能

    2024年02月09日
    浏览(35)
  • 【LeetCode: 210. 课程表 II:拓扑排序+图】

    🚀 算法题 🚀 🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀 🌲 越难的东西,越要努力坚持,因为它具有很高的价值,算法就是这样✨ 🌲 作者简介:硕风和炜,CSDN-Java领域优质创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文

    2024年02月09日
    浏览(59)
  • 2023-09-10 LeetCode每日一题(课程表 II)

    点击跳转到题目位置 现在你总共有 numCourses 门课需要选,记为 0 到 numCourses - 1。给你一个数组 prerequisites ,其中 prerequisites[i] = [ai, bi] ,表示在选修课程 ai 前 必须 先选修 bi 。 例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示:[0,1] 。 返回你为了学完所

    2024年02月09日
    浏览(49)
  • 2023-09-11 LeetCode每日一题(课程表 III)

    点击跳转到题目位置 这里有 n 门不同的在线课程,按从 1 到 n 编号。给你一个数组 courses ,其中 courses[i] = [durationi, lastDayi] 表示第 i 门课将会 持续 上 durationi 天课,并且必须在不晚于 lastDayi 的时候完成。 你的学期从第 1 天开始。且不能同时修读两门及两门以上的课程。 返

    2024年02月09日
    浏览(38)
  • 【LeetCode热题100】打卡第38天:课程表&实现前缀树

    大家好,我是知识汲取者,欢迎来到我的LeetCode热题100刷题专栏! 精选 100 道力扣(LeetCode)上最热门的题目,适合初识算法与数据结构的新手和想要在短时间内高效提升的人,熟练掌握这 100 道题,你就已经具备了在代码世界通行的基本能力。在此专栏中,我们将会涵盖各种

    2024年02月17日
    浏览(52)
  • 自制课程表小程序

    微信开发者工具:稳定版 Stable Build 根据自己电脑的系统下载对应的版本 完整代码连接: https://pan.baidu.com/s/1VbgPOS6CUOae8vg2axhGIg?pwd=hk9e 提取码:hk9e 先把完整代码的压缩包解压,并记住这个路径,后面要用 1.打开下载好的微信开发工具, 注意不要用游客登录 ,我一开始就是游客

    2024年02月09日
    浏览(83)
  • java实现课程表 II

    题目: 现在你总共有  numCourses  门课需要选,记为  0  到  numCourses - 1 。给你一个数组  prerequisites  ,其中  prerequisites[i] = [ai, bi]  ,表示在选修课程  ai  前  必须  先选修  bi  。 例如,想要学习课程  0  ,你需要先完成课程  1  ,我们用一个匹配来表示: [0,1]  。

    2024年02月09日
    浏览(41)
  • 210. 课程表 II Python

    现在你总共有 numCourses 门课需要选,记为 0 到 numCourses - 1 。给你一个数组 prerequisites ,其中 prerequisites[i] = [ai, bi] ,表示在选修课程 ai 前 必须 先选修 bi 。 返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序,你只要返回 任意一种 就可以了。如果不可能完

    2024年02月14日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包