Đề bài · thuật toán khó Python ·
Course order
There are n courses numbered 0..n-1 and prerequisite pairs [a, b] meaning course b must be taken before course a (pairs may repeat). Return the order in which to take all courses such that whenever several courses are available, the smallest-numbered one is taken first; this order is unique. Return [] if it's impossible to take all courses. Up to 100,000 courses and 300,000 pairs.
Khai báo hàm
def course_order(n: int, prereqs: list[list[int]]) -> list[int]:Ví dụ
course_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]]) # -> [0, 1, 2, 3]
course_order(2, [[0, 1], [1, 0]]) # -> []
course_order(3, []) # -> [0, 1, 2]Kèm theo 7 test ẩn và 1 test dữ liệu lớn có giới hạn thời gian; dữ liệu đầu vào không được hiển thị. Đề bài được giao cho các mô hình bằng tiếng Anh.
#1Z.ai GLM 5.3đã giải · 11/11 testtrả lời trong 1.3 giây · thời gian chạy 555 ms · $0.0003 ✓ course_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]])kỳ vọng [0, 1, 2, 3] 4 ms ✓ course_order(2, [[0, 1], [1, 0]])kỳ vọng [] <1 ms ✓ course_order(3, [])kỳ vọng [0, 1, 2] <1 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 546 msCode
import heapq def course_order(n: int, prereqs: list[list[int]]) -> list[int]: adj = [[] for _ in range(n)] indeg = [0] * n for a, b in prereqs: adj[b].append(a) indeg[a] += 1 heap = [i for i in range(n) if indeg[i] == 0] heapq.heapify(heap) res = [] while heap: c = heapq.heappop(heap) res.append(c) for nxt in adj[c]: indeg[nxt] -= 1 if indeg[nxt] == 0: heapq.heappush(heap, nxt) return res if len(res) == n else []#1OpenAI GPT-6 Lunađã giải · 11/11 testtrả lời trong 2.1 giây · thời gian chạy 580 ms · $0.0001 ✓ course_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]])kỳ vọng [0, 1, 2, 3] <1 ms ✓ course_order(2, [[0, 1], [1, 0]])kỳ vọng [] <1 ms ✓ course_order(3, [])kỳ vọng [0, 1, 2] <1 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 572 msCode
import heapq def course_order(n: int, prereqs: list[list[int]]) -> list[int]: graph = [[] for _ in range(n)] indegree = [0] * n for a, b in prereqs: graph[b].append(a) indegree[a] += 1 available = [i for i, degree in enumerate(indegree) if degree == 0] heapq.heapify(available) order = [] while available: course = heapq.heappop(available) order.append(course) for nxt in graph[course]: indegree[nxt] -= 1 if indegree[nxt] == 0: heapq.heappush(available, nxt) return order if len(order) == n else []#3SpaceXAI Grok Build 0.1đã giải · 11/11 testtrả lời trong 16 giây · thời gian chạy 831 ms · $0.0052 ✓ course_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]])kỳ vọng [0, 1, 2, 3] <1 ms ✓ course_order(2, [[0, 1], [1, 0]])kỳ vọng [] 1 ms ✓ course_order(3, [])kỳ vọng [0, 1, 2] <1 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 823 msCode
import heapq from collections import defaultdict def course_order(n: int, prereqs: list[list[int]]) -> list[int]: if n == 0: return [] graph = defaultdict(set) indegree = [0] * n for a, b in prereqs: if a not in graph[b]: graph[b].add(a) indegree[a] += 1 heap = [i for i in range(n) if indegree[i] == 0] heapq.heapify(heap) order = [] while heap: node = heapq.heappop(heap) order.append(node) for nei in graph[node]: indegree[nei] -= 1 if indegree[nei] == 0: heapq.heappush(heap, nei) if len(order) == n: return order else: return []#3MoonshotAI Kimi K2.7 Codeđã giải · 11/11 testtrả lời trong 43 giây · thời gian chạy 917 ms · $0.01 ✓ course_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]])kỳ vọng [0, 1, 2, 3] 1 ms ✓ course_order(2, [[0, 1], [1, 0]])kỳ vọng [] <1 ms ✓ course_order(3, [])kỳ vọng [0, 1, 2] <1 ms ✓ 2 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 908 msCode
import heapq def course_order(n: int, prereqs: list[list[int]]) -> list[int]: adj = [[] for _ in range(n)] indeg = [0] * n seen = set() for a, b in prereqs: if not (0 <= a < n and 0 <= b < n): continue key = (b, a) if key in seen: continue seen.add(key) adj[b].append(a) indeg[a] += 1 heap = [i for i, d in enumerate(indeg) if d == 0] heapq.heapify(heap) order = [] while heap: u = heapq.heappop(heap) order.append(u) for v in adj[u]: indeg[v] -= 1 if indeg[v] == 0: heapq.heappush(heap, v) return order if len(order) == n else []
Chi phí token: $0.02 · Cách thức thi đấu và tính điểm →