专栏首页前端小书童一天一大 lee(课程表)难度:中等-Day20200804

一天一大 lee(课程表)难度:中等-Day20200804

题目:

你这个学期必须选修 numCourse 门课程,记为 0 到 numCourse-1 。

在选修某些课程之前需要一些先修课程。 例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示他们:[0,1]

给定课程总量以及它们的先决条件,请你判断是否可能完成所有课程的学习?

示例

  1. 示例 1
输入: 2, [[1,0]]
输出: true
解释: 总共有 2 门课程。学习课程 1 之前,你需要完成课程 0。所以这是可能的。
  1. 示例 2
输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前,你需要先完成课程 0;并且学习课程 0 之前,你还应先完成课程 1。这是不可能的。

提示

  1. 输入的先决条件是由 边缘列表 表示的图形,而不是 邻接矩阵
  2. 可以假定输入的先决条件中没有重复的边。
  3. 1 <= numCourses <=
10^5

抛砖引玉

抛砖引玉

思路

  • 之前考虑prerequisites是依赖关系的集合可能包含多个子集,
  • 这样一个prerequisites子集中不相邻的子集即[1,0,2]中1,2的出度入度就不好统计了

看了官方的题解,prerequisites多了限制条件只有两个元素,那统计出度入度就简便了:

  • 对numCourses中任意一门课其包含依赖它的(入度),其依赖的(出度)
  • 统计每个元素入度数量及出度子集
  • 当一个元素的入度数量为0时,则说明可以选择这个元素作为入口,即选修它
  • 遍历(选修)其出度子集,子集入度均减一,即枚举选修他们
  • 遇到入度为0,则继续上面的逻辑,知道枚举出最后一个入度数量为0元素,每尝试一次枚举即表示选修了一门课
  • 如果所有的课都选修了则返回true
/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
var canFinish = function (numCourses, prerequisites) {
  let mapItem = new Map(), // 出度子集
    mapNum = new Map(),   // 入度连接数
    _result = numCourses,
    startList = [],
    len = prerequisites.length;

  // 初始化入度连接数 与 出度子集
  for (let i = 0; i < numCourses; i++) {
    mapItem.set(i, []);
    mapNum.set(i, 0);
  }

  // 填充入度、出度数据
  for (let i = 0; i < len; i++) {

    // prerequisites[1]  需要在  prerequisites[0] 之前
    //   before -> after
    //   before(出度) -> after (入度)
    let after = prerequisites[i][0],
      before = prerequisites[i][1],
      afterValue = mapNum.get(after),
      beforeValue = mapItem.get(before);

    mapItem.set(before, [...beforeValue, after])
    mapNum.set(after, afterValue + 1)

  }

  // 取出不依赖其他课的元素
  for (let [key, value] of mapNum) {
    if (value === 0) startList.push(key);
  }

  while (startList.length) {
    // 枚举选修不依赖未学习的课的元素
    let item = startList.shift(),
      nextItem = mapItem.get(item);
      // 枚举一轮带选课减一
    _result--;

    if (nextItem && nextItem.length) {
      // 尝试本轮所有选课可能,遇到选择后存在入度为0的元素,
      // 则推进枚举list,之后尝试按照这种路线选课
      for (let i = 0; i < nextItem.length; i++) {
        let nextNum = mapNum.get(nextItem[i]) - 1;
        mapNum.set(nextItem[i], nextNum);
        if (nextNum === 0) {
          startList.push(nextItem[i]);
        }
      }
    }
  }
  // 是否选择了所有课程
  return _result === 0;
}

深度优先搜索

  • 记录每个课程的前置课程
  • 遍历选择课程,选择一门课标记1, 再遍历其依赖的课程:
    • 如果前置课程未被选择,则转换成选择这门前置课程
    • 如果前置课程存在可以被选择且不再有依赖的课程则标记2
    • 如果前置课程同样被标记1则说明:该门课的前置课程同样存在无法满足无依赖的前置课程及形成了无入度的闭环
/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
var canFinish = function(numCourses, prerequisites) {
  let map = new Map(),
    valid = true,
    visited = Array(numCourses).fill(0);

  for (let i = 0; i < numCourses; i++) {
    map.set(i, [])
  }
  // 查询每个课程的的前置课程 即可能的出度子集
  for (let i = 0; i < prerequisites.length; i++) {
    let after = prerequisites[i][0],
      before = prerequisites[i][1],
      beforeValue = map.get(before);
    map.set(before, [...beforeValue, after])
  }

  // 循环为被学习的课程检修是否存在 闭环
  for (let i = 0; (i < numCourses) && valid; i++) {
    if (visited[i] == 0) {
      dfs(i);
    }
  }

// 输入的课程标记选择1
  function dfs(u) {
    visited[u] = 1;
    for (let v of map.values) {
      // 如果前置课程未被选择过则先选择前置课程
      if (visited[v] === 0) {
        dfs(v);
        if (!valid) {
          return;
        }
      } else if (visited[v] === 1) {
        // 如果前置元素同样被标记1,则说明在找u的前置课程v是v的前置课程也同样依赖未选修的前置课程
        valid = false;
        return;
      }
    }
    // 完成前置课程查询标记该课程完成2
    visited[u] = 2;
  }

  // 默认成功,存在闭环则返回失败
  return valid;
};

本文分享自微信公众号 - 前端小书童(gaowenju_web),作者:坑人的小书童

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-08-05

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 一天一大 leet(地下城游戏)难度:困难-Day20200712

    一些恶魔抓住了公主(P)并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士(K)最初被安置在左上角的房间里,他必须穿过地下...

    前端小书童
  • 【一天一大 lee】数组中的最长山脉 (难度:中等) - Day20201025

    那么枚举数组中可能是交换节点的元素,再以次节点为中心左右遍历统计连续的长度,最终返回最大长度即题目要求的结果

    前端小书童
  • 【一天一大 lee】长按键入 (难度:简单) - Day20201021

    你的朋友正在使用键盘输入他的名字 name。偶尔,在键入字符 c 时,按键可能会被长按,而字符可能被输入 1 次或多次。

    前端小书童
  • 2020 程序员找工作指南

    offer,录取意向,offer 分为口头 offer 和书面 offer,一般书面 offer 才算是正式 offer,例句

    cnguu
  • 迪米特法则与重构

    在面向对象设计的世界里,有一个寻常却又常常为人所忽略的原则——“迪米特(Law of Demeter)”法则。这个原则认为,任何一个对象或者方法,它应该只能调用...

    张逸
  • 服务器资源池化技术发展趋势简介

    "鹅厂网事"由深圳市腾讯计算机系统有限公司技术工程事业群网络平台部运营,我们希望与业界各位志同道合的伙伴交流切磋最新的网络、服务器行业动态信息,同时分享腾讯在网...

    鹅厂网事
  • Android实现压缩字符串的方法示例

    Android端可以对字符串进行压缩,我们在进行大量简单文本传输时,可以先压缩字符串再发送。接收端接收后再解压。也可以将字符串压缩后存入数据库中,下面话不多说了...

    砸漏
  • 神经网络通俗指南:一文看懂神经网络工作原理

    【新智元导读】 本文带来对深度神经网络的通俗介绍,附动图展示。 现在谈人工智能已经绕不开“神经网络”这个词了。人造神经网络粗线条地模拟人脑,使得计算机能够从数据...

    新智元
  • 云计算对应用程序和架构设计的安全影响

    应用程序可以轻松地在属于自己隔离的云环境中运行,根据提供者的不同,可能是一个单独的虚拟网络(虚拟专有网络VPC),也可能是一个一个单独的账号/子账号。使用账户或...

    一只特立独行的兔先生
  • 【java基础】javaMail发送邮件设置发件人,重点设置中文昵称

    用户5640963

扫码关注云+社区

领取腾讯云代金券