java数据结构与算法刷题-----LeetCode210. 课程表 II

java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完):https://blog.csdn.net/grd_java/article/details/123063846

文章目录

    • 深度优先遍历但不进行逆拓扑排序(不用栈)

在这里插入图片描述

这道题是207题的衍生题,代码完全一样,具体解析看207题即可,这里不做过多赘述了。

🏆LeetCode207. 课程表(拓扑排序)https://blog.csdn.net/grd_java/article/details/137561889

深度优先遍历但不进行逆拓扑排序(不用栈)

解题思路:时间复杂度O( m + n m+n m+n),空间复杂度O( m + n m+n m+n)n是顶点数,m是边的数量
  1. 有了207题的基础,我们知道,深度优先遍历的拓扑排序输出结果是逆拓扑排序
  2. 如果我们想要正着输出,目前经典的解决方法,是先将结果放入栈中,最后完成排序后,再次出栈完成输出,实现逆拓扑排序反转效果
  3. 但是我们不使用栈如何实现呢?那就是逆中逆的思路
  4. 我们保存所有顶点的直接前驱顶点(指向它的顶点),然后逆过了,从每个顶点向上深度优先遍历,将它所有的前驱顶点处理完成,当前顶点就是0入度顶点
  5. 这样就完成了深度优先遍历,直接按照正拓扑排序顺序输出的效果
  6. 具体可以看207题的解析,有详细案例
代码:这种算法比普通的深度优先和广度优先算法更快

在这里插入图片描述

class Solution {
    static class Node {//课程结点,用来抽象为图
        Node next;//当前结点指向的下一个结点
        int val;//值
        public Node(){
            this.val = -1;
        }
        public Node(int val){
            this.val = val;
        }
        public Node(int val,Node next){
            this.val = val;
            this.next = next;
        }
    }
    Node[] corses;//保存每个顶点的前驱结点(哪些顶点指向当前顶点)
    int[] visited;//0:未访问,1:已访问,2:已经拓扑遍历
    int[] ans;//保存拓扑排序结果
    int ansIndex;//下标
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        corses = new Node[numCourses];//初始化
        visited = new int[numCourses];//初始化
        ans = new int[numCourses];//初始化
        ansIndex = 0;//初始化
        for(int[] corse:prerequisites){
            //要完成corse[0],必须先完成corse[1],也就是corse[1]->corse[0].所以corse[0]的前驱需要添加一个corse[0]
            corses[corse[0]]=new Node(corse[1],corses[corse[0]]);//头插法将corse[1]插入到corse[0]顶点的前驱链表中
        }
        for(int i = 0; i < numCourses; i++){//依次试图从每个顶点进行深度优先遍历
            if(!dfs(i)) return new int[]{};//如果无法完成拓扑排序,就返回空数组
        }
        return ans;//完成拓扑排序,返回拓扑排序结果
    }
    private boolean dfs(int i){//深度优先遍历
        if(visited[i] == 2)return true;//如果当前顶点已经拓扑输出,直接跳过
        if(visited[i] == 1)return false;//如果当前顶点没有拓扑输出,但是再次访问,说明有环,不能完成拓扑排序
        visited[i] = 1;//标志为已经访问过
        Node node = corses[i];//获取当前顶点的所有直接前驱邻居
        while(node!=null){
            if(!dfs(node.val)) return false;//访问这些前驱,直到它们没有前驱为止,说明它是一个0入的顶点
            node = node.next;//处理当前顶点所有的直接前驱后
        }
        visited[i] = 2;//当前顶点就没有入度了(因为前驱全部被输出处理了)
        ans[ansIndex++] = i;//将其输出
        return true;//表示到目前位置,满足拓扑排序
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/533117.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

三年Android开发经验面试经历分享

最近&#xff0c;参加了多家公司的面试&#xff0c;下面是我所经历的一些面试问题及自己的回答思路。 一、京东面试 一面&#xff1a; 项目内容&#xff1a;主要讲述了在实习期间参与的项目&#xff0c;以及在项目中负责的工作和取得的成果。MVP模式&#xff1a;解释了MVP模…

特征融合篇 | YOLOv8改进之将Neck网络更换为多级特征融合金字塔HS-FPN | 助力小目标检测

前言:Hello大家好,我是小哥谈。HS-FPN(Hierarchical Scale Feature Pyramid Network)是一种用于目标检测任务的网络结构。它是在传统的Feature Pyramid Network(FPN)基础上进行改进的。HS-FPN的主要目标是解决目标检测中存在的多尺度问题。在传统的FPN中,通过在不同层级…

机器学习实训 Day1

线性回归练习 Day1 手搓线性回归 随机初始数据 import numpy as np x np.array([56, 72, 69, 88, 102, 86, 76, 79, 94, 74]) y np.array([92, 102, 86, 110, 130, 99, 96, 102, 105, 92])from matplotlib import pyplot as plt # 内嵌显示 %matplotlib inlineplt.scatter…

Android自定义控件ScrollView实现上下滑动功能

本文实例为大家分享了Android ScrollView实现上下滑动功能的具体代码&#xff0c;供大家参考&#xff0c;具体内容如下 package com.example.zhuang; import android.content.Context; import android.util.AttributeSet; import android.util.DisplayMetrics; import android…

什么是生成式AI?有哪些特征类型

生成式AI是人类一种人工智能技术&#xff0c;可以生成各种类型的内容&#xff0c;包括文本、图像、音频和合成数据。那么什么是人工智能&#xff1f;人工智能和机器学习之间的区别是什么&#xff1f;有哪些技术特征&#xff1f; 人工智能是一门学科&#xff0c;是计算机科学的一…

日志监控思路分享,只监控日志内容,不存储

有一个这样的需求&#xff0c;就是实时监控日志文件的内容&#xff0c;不需要存储&#xff0c;仅当某行日志内容触发某个规则时调用一段业务逻辑就行了。比如用户触发限流规则&#xff0c;就将其封禁并发送钉钉通知到运维群。 看到这个需求首先想到的就是日志采集工具&#xff…

【ARM 裸机】汇编 led 驱动之原理分析

1、我们为什么要学习汇编&#xff1f;&#xff1f;&#xff1f; 之前我们或许接触过 STM32 以及其他的 32 位的 MCU ,都是基于 C 语言环境进行编程的&#xff0c;都没怎么注意汇编&#xff0c;是因为 ST 公司早已将启动文件写好了&#xff0c;新建一个 STM32 工程的时候&#…

网站HTTP升级成为HTTPS的方法

将网站从HTTP免费升级为HTTPS&#xff0c;您可以按照以下步骤操作&#xff1a; 1. 选择证书颁发机构&#xff08;CA&#xff09;&#xff1a; - 为了免费升级&#xff0c;您可以选择使用JoySSL这样的公益项目。JoySSL提供免费、自动化的SSL/TLS证书颁发服务&#xff0c;适用于各…

HAL STM32F4内部温度读取+ADC阻塞式读取

HAL STM32F4内部温度读取ADC阻塞式读取 &#x1f4cd;相关篇《STM32F103VET6基于STM32CubeMX 配置非DMA方式获取内部温度》 &#x1f516;对于大多数stm32型号&#xff0c;基本上内部都集成了温度传感器。 ⛳不同型号的STM32单片机&#xff0c;计算温度的公式差异 &#x1f33f…

Vue2和Vue3组件通信:父子与兄弟间的桥梁

&#x1f31f; 前言 欢迎来到我的技术小宇宙&#xff01;&#x1f30c; 这里不仅是我记录技术点滴的后花园&#xff0c;也是我分享学习心得和项目经验的乐园。&#x1f4da; 无论你是技术小白还是资深大牛&#xff0c;这里总有一些内容能触动你的好奇心。&#x1f50d; &#x…

网盘——登录跳转

在界面设计这块&#xff0c;当登录界面上输入的账号和密码都正确的情况下&#xff0c;直接跳转到好友界面&#xff0c;否则不跳转 1、在opewidget.h里面定义一个单例模式 static OpeWidget &getInstance(); 2、添加定义 产生一个静态的操作界面的对象。操作界面这个对象他…

《零秒思考》像麦肯锡精英一样思考 - 三余书屋 3ysw.net

零秒思考&#xff1a;像麦肯锡精英一样思考 大家好&#xff0c;今天我们要深入探讨的著作是《零秒思考》。在领导提出问题时&#xff0c;我们常常会陷入沉思&#xff0c;却依然难以有所进展&#xff0c;仿佛原地踏步&#xff0c;但是身边的同事却能够立即给出清晰的回答。这种…

Rust面试宝典第1题:爬楼梯

题目 小乐爬楼梯&#xff0c;一次只能上1级或者2级台阶。楼梯一共有n级台阶&#xff0c;请问总共有多少种方法可以爬上楼&#xff1f; 解析 这道题虽然是一道编程题&#xff0c;但实际上更是一道数学题&#xff0c;着重考察应聘者的逻辑思维能力和分析解决问题的能力。 当楼梯只…

Web路径专题

文章目录 1.资源定位1.前置条件上下文路径设置 2.上下文路径介绍重点说明 3.资源定位方式资源路径 上下文路径 资源位置a.html定位C.java定位 4.浏览器和服务器解析的区别1.浏览器解析/&#xff08;地址变化&#xff09;2.服务器解析/&#xff08;地址不变&#xff09; 5.带/…

华为ensp中PPP(点对点协议)中的CHAP认证 原理和配置命令

作者主页&#xff1a;点击&#xff01; ENSP专栏&#xff1a;点击&#xff01; 创作时间&#xff1a;2024年4月11日6点00分 PPP协议&#xff08;Point-to-Point Protocol&#xff09;是点到点协议&#xff0c;是一种常用的串行链路层协议&#xff0c;用于在两个节点之间建立点…

结合 tensorflow.js 、opencv.js 与 Ant Design 创建美观且高性能的人脸动捕组件并发布到InsCode

系列文章目录 如何在前端项目中使用opencv.js | opencv.js入门如何使用tensorflow.js实现面部特征点检测tensorflow.js 如何从 public 路径加载人脸特征点检测模型tensorflow.js 如何使用opencv.js通过面部特征点估算脸部姿态并绘制示意图tensorflow.js 使用 opencv.js 将人脸…

PTA 2813:画家问题(熄灯问题)

有一个正方形的墙&#xff0c;由NN个正方形的砖组成&#xff0c;其中一些砖是白色的&#xff0c;另外一些砖是黄色的。Bob是个画家&#xff0c;想把全部的砖都涂成黄色。但他的画笔不好使。当他用画笔涂画第(i,j)个位置的砖时&#xff0c; 位置(i−1,j)、 (i1,j)、(i,j−1)、(i…

HJ13 句子逆序(句子反序,再把单词反序)

句子反序&#xff0c;再把单词反序 import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别String s sc.n…

本地化部署离线开源免费语音识别API,支持多模态AI能力引擎

思通数科作为一家专注于多模态AI能力开源引擎平台&#xff0c;其技术产品涵盖了自然语言处理、情感分析、实体识别、图像识别与分类、OCR识别以及语音识别等多个领域。在语音识别这一细分市场&#xff0c;思通数科的技术产品中的音频文件转写服务有着相似的应用场景和功能特点。…

如何将powerpoint(PPT)幻灯片嵌入网页中在线预览、编辑并保存到服务器?

猿大师办公助手不仅可以把微软Office、金山WPS和永中Office的Word文档、Excel表格内嵌到浏览器网页中实现在线预览、编辑保存等操作&#xff0c;还可以把微软Office、金山WPS和永中Office的PPT幻灯片实现网页中在线预览、编辑并保存到服务器。 猿大师办公助手把本机原生Office…