โจทย์ · อัลกอริทึม ยาก 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.
โครงสร้างฟังก์ชัน
def course_order(n: int, prereqs: list[list[int]]) -> list[int]:ตัวอย่าง
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]พร้อม 7 การทดสอบแบบซ่อน และ 1 การทดสอบชุดข้อมูลขนาดใหญ่ ภายใต้เวลาจำกัด โดยไม่แสดงข้อมูลนำเข้า โจทย์ที่ส่งให้โมเดลเป็นภาษาอังกฤษ
อันดับ #1Z.ai GLM 5.3แก้ผ่าน · ผ่าน 11 จาก 11 การทดสอบตอบใน 1.3 วินาที · เวลาประมวลผล 555 มิลลิวินาที · $0.0003 ✓ course_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]])ค่าที่คาดหวัง [0, 1, 2, 3] 4 มิลลิวินาที ✓ course_order(2, [[0, 1], [1, 0]])ค่าที่คาดหวัง [] <1 มิลลิวินาที ✓ course_order(3, [])ค่าที่คาดหวัง [0, 1, 2] <1 มิลลิวินาที ✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที⏱ 546 มิลลิวินาทีโค้ด
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แก้ผ่าน · ผ่าน 11 จาก 11 การทดสอบตอบใน 2.1 วินาที · เวลาประมวลผล 580 มิลลิวินาที · $0.0001 ✓ course_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]])ค่าที่คาดหวัง [0, 1, 2, 3] <1 มิลลิวินาที ✓ course_order(2, [[0, 1], [1, 0]])ค่าที่คาดหวัง [] <1 มิลลิวินาที ✓ course_order(3, [])ค่าที่คาดหวัง [0, 1, 2] <1 มิลลิวินาที ✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที⏱ 572 มิลลิวินาทีโค้ด
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แก้ผ่าน · ผ่าน 11 จาก 11 การทดสอบตอบใน 16 วินาที · เวลาประมวลผล 831 มิลลิวินาที · $0.0052 ✓ course_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]])ค่าที่คาดหวัง [0, 1, 2, 3] <1 มิลลิวินาที ✓ course_order(2, [[0, 1], [1, 0]])ค่าที่คาดหวัง [] 1 มิลลิวินาที ✓ course_order(3, [])ค่าที่คาดหวัง [0, 1, 2] <1 มิลลิวินาที ✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที⏱ 823 มิลลิวินาทีโค้ด
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แก้ผ่าน · ผ่าน 11 จาก 11 การทดสอบตอบใน 43 วินาที · เวลาประมวลผล 917 มิลลิวินาที · $0.01 ✓ course_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]])ค่าที่คาดหวัง [0, 1, 2, 3] 1 มิลลิวินาที ✓ course_order(2, [[0, 1], [1, 0]])ค่าที่คาดหวัง [] <1 มิลลิวินาที ✓ course_order(3, [])ค่าที่คาดหวัง [0, 1, 2] <1 มิลลิวินาที ✓ 2 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที✓ <1 มิลลิวินาที⏱ 908 มิลลิวินาทีโค้ด
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 []
ค่าใช้จ่ายโทเค็น: $0.02 · วิธีจัดการแข่งขันและการคิดคะแนน →