Python每日一练(20230505) 课程表 Course Schedule III/IV

简介: Python每日一练(20230505) 课程表 Course Schedule III/IV
+关注继续查看

3. 课程表 Course Schedule III


这里有 n 门不同的在线课程,按从 1 到 n 编号。给你一个数组 courses ,其中 courses[i] = [durationi, lastDayi] 表示第 i 门课将会 持续 上 durationi 天课,并且必须在不晚于 lastDayi 的时候完成。


你的学期从第 1 天开始。且不能同时修读两门及两门以上的课程。

返回你最多可以修读的课程数目。


示例 1:

输入:courses = [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]

输出:3


解释:

这里一共有 4 门课程,但是你最多可以修 3 门:

首先,修第 1 门课,耗费 100 天,在第 100 天完成,在第 101 天开始下门课。

第二,修第 3 门课,耗费 1000 天,在第 1100 天完成,在第 1101 天开始下门课程。

第三,修第 2 门课,耗时 200 天,在第 1300 天完成。

第 4 门课现在不能修,因为将会在第 3300 天完成它,这已经超出了关闭日期。


示例 2:

输入:courses = [[1,2]]

输出:1


示例 3:

输入:courses = [[3,2],[4,3]]

输出:0


提示:

   1 <= courses.length <= 10^4

   1 <= durationi, lastDayi <= 10^4


代码: 贪心算法

package main
 
import (
    "fmt"
    "sort"
)
 
func scheduleCourse(courses [][]int) int {
    // 按照截止日期升序排序
    sort.Slice(courses, func(i, j int) bool {
        return courses[i][1] < courses[j][1]
    })
 
    time := 0
    selected := make([][]int, 0)
    for _, c := range courses {
        if time+c[0] <= c[1] {
            selected = append(selected, []int{c[0], c[1]})
            time += c[0]
            sort.Slice(selected, func(i, j int) bool {
                return selected[i][0] > selected[j][0]
            })
        } else if len(selected) > 0 && c[0] < selected[0][0] {
            time += c[0] - selected[0][0]
            selected[0] = []int{c[0], c[1]}
            sort.Slice(selected, func(i, j int) bool {
                return selected[i][0] > selected[j][0]
            })
        }
    }
 
    return len(selected)
}
 
func main() {
    courses := [][]int{{100, 200}, {200, 1300}, {1000, 1250}, {2000, 3200}}
    fmt.Println(scheduleCourse(courses))
    courses = [][]int{{1, 2}}
    fmt.Println(scheduleCourse(courses))
}

输出:

3

1


4. 课程表 Course Schedule IV


你总共需要上 numCourses 门课,课程编号依次为 0 到 numCourses-1 。你会得到一个数组 prerequisite ,其中 prerequisites[i] = [ai, bi] 表示如果你想选 bi 课程,你 必须 先选 ai 课程。


   有的课会有直接的先修课程,比如如果想上课程 1 ,你必须先上课程 0 ,那么会以 [0,1] 数对的形式给出先修课程数对。


先决条件也可以是 间接 的。如果课程 a 是课程 b 的先决条件,课程 b 是课程 c 的先决条件,那么课程 a 就是课程 c 的先决条件。


你也得到一个数组 queries ,其中 queries[j] = [uj, vj]。对于第 j 个查询,您应该回答课程 uj 是否是课程 vj 的先决条件。


返回一个布尔数组 answer ,其中 answer[j] 是第 j 个查询的答案。


示例 1:

ca29d5811100fc46f8ee9d40431f1426.jpeg

输入:numCourses = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]

输出:[false,true]


解释:课程 0 不是课程 1 的先修课程,但课程 1 是课程 0 的先修课程。


示例 2:

59ac1bcbf7e41e01ae8ed3a6862f3937.jpeg

输入:numCourses = 2, prerequisites = [], queries = [[1,0],[0,1]]

输出:[false,false]

解释:没有先修课程对,所以每门课程之间是独立的。


示例 3:

输入:numCourses = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]]

输出:[true,true]


提示:


   2 <= numCourses <= 100

   0 <= prerequisites.length <= (numCourses * (numCourses - 1) / 2)

   prerequisites[i].length == 2

   0 <= ai, bi <= n - 1

   ai != bi

   每一对 [ai, bi] 都 不同

   先修课程图中没有环。

   0 <= ui, vi <= n - 1

   ui != vi


代码:

package main
 
import "fmt"
 
func checkIfPrerequisite(numCourses int, prerequisites [][]int, queries [][]int) []bool {
    // 构建课程图
    n := numCourses
    graph := make([][]int, n)
    inDegree := make([]int, n)
    for _, p := range prerequisites {
        ai, bi := p[0], p[1]
        graph[ai] = append(graph[ai], bi)
        inDegree[bi]++
    }
 
    // BFS 拓扑排序
    queue := make([]int, 0)
    for i := 0; i < n; i++ {
        if inDegree[i] == 0 {
            queue = append(queue, i)
        }
    }
    successors := make([][]int, n)
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        for _, neighbor := range graph[node] {
            inDegree[neighbor]--
            if inDegree[neighbor] == 0 {
                queue = append(queue, neighbor)
            }
            // 记录 successor 节点
            successors[node] = append(successors[node], neighbor)
            for _, s := range successors[neighbor] {
                successors[node] = append(successors[node], s)
            }
        }
    }
 
    // 对每个查询进行检查
    result := make([]bool, len(queries))
    for i, q := range queries {
        ui, vi := q[0], q[1]
        for _, s := range successors[ui] {
            if s == vi {
                result[i] = true
                break
            }
        }
    }
    return result
}
 
func main() {
    numCourses := 2
    prerequisites := [][]int{{1, 0}}
    queries := [][]int{{0, 1}, {1, 0}}
    fmt.Println(checkIfPrerequisite(numCourses, prerequisites, queries))
    prerequisites = [][]int{}
    queries = [][]int{{1, 0}, {0, 1}}
    fmt.Println(checkIfPrerequisite(numCourses, prerequisites, queries))
}



输出:

[false true]

[false false]


目录
相关文章
|
4月前
|
Python
Python每日一练(20230518) 螺旋矩阵 I\II\III\IV Spiral Matrix
Python每日一练(20230518) 螺旋矩阵 I\II\III\IV Spiral Matrix
58 0
|
4月前
|
Python
Python每日一练(20230517) 最大连续1的个数 I\II\III
Python每日一练(20230517) 最大连续1的个数 I\II\III
67 0
|
4月前
|
Python
Python每日一练(20230516) 打家劫舍 I\II\III\IV HouseRobber
Python每日一练(20230516) 打家劫舍 I\II\III\IV HouseRobber
85 0
|
4月前
|
算法 Python
Python每日一练(20230515) 只出现一次的数字 I\II\III
Python每日一练(20230515) 只出现一次的数字 I\II\III
66 0
|
4月前
|
机器人 Python
Python每日一练(20230514) 不同路径 I\II\III UniquePaths
Python每日一练(20230514) 不同路径 I\II\III UniquePaths
61 0
|
4月前
|
Python
Python每日一练(20230513) 粉刷房子 I\II\III Paint House
Python每日一练(20230513) 粉刷房子 I\II\III Paint House
66 0
|
4月前
|
Python
Python每日一练(20230512) 跳跃游戏 V\VI\VII
Python每日一练(20230512) 跳跃游戏 V\VI\VII
45 0
|
4月前
|
算法 Python
Python每日一练(20230511) 跳跃游戏 I\II\III\IV
Python每日一练(20230511) 跳跃游戏 I\II\III\IV
55 0
|
4月前
|
Python
Python每日一练(20230510) 石子游戏 VII\VIII\IX
Python每日一练(20230510) 石子游戏 VII\VIII\IX
40 0
|
4月前
|
算法 Python
Python每日一练(20230509) 石子游戏 IV\V\VI
Python每日一练(20230509) 石子游戏 IV\V\VI
61 0
相关产品
机器翻译
推荐文章
更多