找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 7783|回复: 8
收起左侧

[基础刷题题目讨论] leetcode新题 Course Schedule

[复制链接]

38

主题

0

精华

299

积分

高级会员

Rank: 3Rank: 3

积分
299
发表于 5-6-2015 09:57 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
RT...  拓扑排序。。。我用的bfs

public boolean canFinish(int numCourses, int[][] prerequisites) {
        if(numCourses==0) {
                        return true;
                }
                int m = prerequisites.length;
                if(m==0) {
                        return true;
                }
               
                int[] count = new int[numCourses];
                for(int i=0;i<m;i++) {
                        count[prerequisites【i】[0]]++;
                }
                Queue<Integer> queue = new LinkedList<>();
                int res = 0;
                for(int i=0;i<numCourses;i++) {
                        if(count【i】==0) {
                                queue.offer(i);
                                res++;
                        }               
                }
                while(!queue.isEmpty()) {
                        int cur = queue.poll();
                        for(int i=0;i<m;i++) {
                                if(prerequisites【i】[1]==cur) {
                                        count[prerequisites【i】[0]]--;
                                        if(count[prerequisites【i】[0]]==0) {
                                            queue.offer(prerequisites【i】[0]);
                                            res++;
                                        }
                                }
                        }
                }
                return res==numCourses;
    }

21

主题

11

精华

368

积分

高级会员

Rank: 3Rank: 3

积分
368
发表于 5-6-2015 01:19 PM | 显示全部楼层
DFS拓扑排序解法
先建立graph,就是map里存 course和它所有的pre
对每个course 进行DFS,如果路径里存在重复course,就是有环,返回false,否则某course进行完DFS后标记为processed,进行剪枝。

  1. class Solution {
  2. public:
  3.     using MAP = unordered_map<int, unordered_set<int>>;
  4.     using SET = unordered_set<int>;
  5.     bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
  6.         MAP map;
  7.         for (auto& pair : prerequisites) {
  8.             if (map.find(pair[0]) == map.end())
  9.                 map[pair[0]] = {pair[1]};
  10.             else
  11.                 map[pair[0]].insert(pair[1]);
  12.         }

  13.         SET path, processed;
  14.         for (int i = 0; i < numCourses; ++i)
  15.             if (!DFS(map, path, i, processed)) return false;

  16.         return true;
  17.     }

  18.     bool DFS(MAP& map, SET& path, int course, SET& processed) {
  19.         // processed
  20.         if (processed.find(course) != processed.end()) return true;
  21.         // has cycle
  22.         if (path.find(course) != path.end()) return false;
  23.         // reach end
  24.         if (map.find(course) == map.end()) return true;

  25.         path.insert(course);
  26.         for (auto next : map[course])
  27.             if (!DFS(map, path, next, processed)) return false;
  28.         path.erase(course);

  29.         processed.insert(course);   // pruning
  30.         return true;
  31.     }
  32. };
复制代码
回复 支持 反对

使用道具 举报

50

主题

1

精华

303

积分

高级会员

Rank: 3Rank: 3

积分
303
发表于 5-14-2015 01:28 PM | 显示全部楼层
wgtmac 发表于 5-6-2015 01:19 PM
DFS拓扑排序解法
先建立graph,就是map里存 course和它所有的pre
对每个course 进行DFS,如果路径里存在 ...

我总觉得dfs难写
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表