1494. 并行课程 II

给你一个整数 n 表示某所大学里课程的数目,编号为 1 到 n ,数组 dependencies 中, dependencies[i] = [xi, yi]  表示一个先修课的关系,也就是课程 xi 必须在课程 yi 之前上。同时你还有一个整数 k 。

在一个学期中,你 最多 可以同时上 k 门课,前提是这些课的先修课在之前的学期里已经上过了。

请你返回上完所有课最少需要多少个学期。题目保证一定存在一种上完所有课的方式。

输入:n = 4, dependencies = [[2,1],[3,1],[1,4]], k = 2
输出:3 
解释:上图展示了题目输入的图。在第一个学期中,我们可以上课程 2 和课程 3 。然后第二个学期上课程 1 ,第三个学期上课程 4 。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/parallel-courses-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

class Solution {
    int[] mask=new int[15];
    int[] dp=new int[1<<15];
    int[] cnt=new int[1<<15];
    //dp[state] 表示上完状态为state的课程需要多少学期 state第n位为1 则说明课程n已经上过了
   //state第n位为0 则说明课程n还没上过
    //mask[i]  表示课程i需要先修课程的掩码  mask[i]第j位为1说明 第j门课是i的先修课程 为0 则说明第j门课不是i的先修课程
    //cnt[state] 表示状态state中1的个数 也就是state下已完成课程的数目
    public int minNumberOfSemesters(int n, int[][] dependencies, int k) {
        int N=1<<n;
        for(int i=0;i<n;i++) mask[i]=0;
        //只需记录上一级的先修课程 先修课程的先修课程不需要记录
        //因为只有先修课程的先修课程上完 先修课程才能上
        for(int[] d:dependencies) mask[d[1]-1] |=1<<(d[0]-1);
        cnt[0]=0;
        for(int i=1;i<N;i++) cnt[i]=cnt[i>>1]+(i&1);
        for(int i=1;i<N;i++) dp[i]=16; //天数最多为15
        dp[0]=0;
        for(int i=0;i<N;i++)
        {
            if(dp[i]<=n) //上完所有课最多需要n学期 如果dp[i]>n 说明i状态无法达到
            {
                //System.out.print(i+" ");
              // i为所有课程的完成状态 j为课程序号  
              //(i>>j& 0x1)==0 表示i的第j位不是1说明 该课程还没有上
              //(mask[j] & i) == mask[j] 说明课程j的先修课程已经上完(i中对应mask[j]所有为1的bit也为1) 
              //上述条件满足的情况下 将cur的第j位置1 说明该课程可以在当前学期完成
              int cur=0;
              for(int j=0;j<n;j++)
              {
                  if( (i>>j& 0x1)==0 && (mask[j] & i) == mask[j] ) cur|=1<<j;
              }
              //l中包括了当前学期内所有可以完成的课程 其中的课程可以选择在本学期完成 也可以不在
             // j-1 & l 表示逐步将l中的1从低位开始 每次迭代减少一个(课程)
             //当前状态j中的课程数o[j]小于k 说明可以在本学期完成 因此将j中课程加入原始状态i( i|j )
             //dp[i]+1 表示学习天数增加一天
              for(int j=cur;j!=0;j=j-1&cur)
              {
                if(cnt[j]<=k) dp[i|j]=Math.min(dp[i|j],dp[i]+1);
              }
            }
        }
        return dp[N-1];
    }
}


已发布

分类

,

来自

标签: