?Python算法題集_課程表
- 題207：課程表
- 1. 示例說明
- 2. 題目解析
- - 題意分解
- - 優化思路
- - 測量工具
- 3. 代碼展開
- 1) 標準求解【循環+遞歸+全算】
- 2) 改進版一【循環+遞歸+緩存】
- 3) 改進版二【循環+遞歸+緩存+反向計算】
- 4) 改進版三【迭代剝離+計數器檢測】
- 4. 最優算法
- 5. 相關資源
本文為Python算法題集之一的代碼示例
題207：課程表
1. 示例說明
你這個學期必須選修 numCourses 門課程，記為 0 到 numCourses - 1 。
在選修某些課程之前需要一些先修課程。 先修課程按數組 prerequisites 給出，其中 prerequisites[i] = [ai, bi] ，表示如果要學習課程 ai 則 必須 先學習課程 bi 。
- 例如，先修課程對
[0, 1]表示：想要學習課程0，你需要先完成課程1。
請你判斷是否可能完成所有課程的學習？如果可以，返回 true ；否則，返回 false 。
示例 1：
輸入：numCourses = 2, prerequisites = [[1,0]]
輸出：true
解釋：總共有 2 門課程。學習課程 1 之前，你需要完成課程 0 。這是可能的。
示例 2：
輸入：numCourses = 2, prerequisites = [[1,0],[0,1]]
輸出：false
解釋：總共有 2 門課程。學習課程 1 之前，你需要先完成課程 0 ；并且學習課程 0 之前，你還應先完成課程 1 。這是不可能的。
提示：
1 <= numCourses <= 20000 <= prerequisites.length <= 5000prerequisites[i].length == 20 <= ai, bi < numCoursesprerequisites[i]中的所有課程對 互不相同
2. 題目解析
- 題意分解
- 本題是計算是否會出現無法學習的課程，這種課程的特點是前置課程出現環路，比如A課程的前置課程B的前置課程為A課程
- 本題必須進行課程遍歷，每個課程都需要檢測是否出現環路
- 基本的設計思路是循環+遞歸，循環遍歷課程，遞歸檢測環路
- 優化思路
-
通常優化：減少循環層次
-
通常優化：增加分支，減少計算集
-
通常優化：采用內置算法來提升計算速度
-
分析題目特點，分析最優解
-
如果一個課程已經檢測沒有出現環路，則前置課程檢測到此課程就不用繼續檢測下去，減少計算量
-
可以研究迭代法實現科目檢測
-
- 測量工具
- 本地化測試說明：LeetCode網站測試運行時數據波動很大【可把頁面視為功能測試】，因此需要本地化測試解決數據波動問題
CheckFuncPerf（本地化函數用時和內存占用測試模塊）已上傳到CSDN，地址：Python算法題集_檢測函數用時和內存占用的模塊- 本題超時測試用例較難生成，已經保存為文本文件，本次測試結果詳見章節【最優算法】，測試用例文件包含在【相關資源】中
3. 代碼展開
1) 標準求解【循環+遞歸+全算】
循環遍歷課程，遞歸檢測環路，能算盡算，不出所料，功能測試就已超時
頁面功能測試，未能通關，超時失敗
import CheckFuncPerf as cfpclass Solution:def canFinish_base(self, numCourses, prerequisites):list_graph = [[] for x in range(numCourses)]for a, b in prerequisites:list_graph[a].append(b)def dfs_checkring(visited, pres):if not pres:return Trueresult = Truefor course in pres:if course in visited:return Falseresult &= dfs_checkring(visited + [course], list_graph[course])return resultreturn all(dfs_checkring([i], pres) for i, pres in enumerate(list_graph))print(f'prerequisites count of the Courses = {len(check_prerequisites)}')
result = cfp.getTimeMemoryStr(Solution.canFinish_base, aSolution, 50000, check_prerequisites)
print(result['msg'], '執行結果 = {}'.format(result['result']))# 運行結果
prerequisites count of the Courses = 49999
函數 canFinish_base 的運行時間為 50813.51 ms；內存使用量為 7264.00 KB 執行結果 = True
2) 改進版一【循環+遞歸+緩存】
循環遍歷課程，遞歸檢測環路，緩存已經計算的課程環路結果
頁面功能測試，勉強通過，超過11%
import CheckFuncPerf as cfpclass Solution:def canFinish_ext1(self, numCourses: int, prerequisites):list_graph = [[] for x in range(numCourses)]for a, b in prerequisites:list_graph[a].append(b)learned = [0] * numCoursesdef dfs_checkring(visited, pres):if not pres:return Trueresult = Truefor course in pres:if course in visited:return Falseif learned[course] > 0:continuelearned[course] = 1result &= dfs_checkring(visited + [course], list_graph[course])return resultfor iIdx, pres in enumerate(list_graph):if learned[iIdx] > 0:continueresult = dfs_checkring([iIdx], pres)if not result:return Falselearned[iIdx] = 1return Trueprint(f'prerequisites count of the Courses = {len(check_prerequisites)}')
result = cfp.getTimeMemoryStr(Solution.canFinish_base, aSolution, 50000, check_prerequisites)
print(result['msg'], '執行結果 = {}'.format(result['result']))# 運行結果
prerequisites count of the Courses = 49999
函數 canFinish_ext1 的運行時間為 66.02 ms；內存使用量為 6112.00 KB 執行結果 = True
3) 改進版二【循環+遞歸+緩存+反向計算】
循環遍歷課程，遞歸檢測環路，但是檢測環路修改為從前置科目開始計算此科目的后置科目是否出現環路
頁面功能測試，性能良好，超過88%
import CheckFuncPerf as cfpclass Solution:def canFinish_ext2(self, numCourses, prerequisites):def dfs_checkring(iIdx, list_graph, ringflags):if ringflags[iIdx] == -1:return Trueif ringflags[iIdx] == 1:return Falseringflags[iIdx] = 1for jIdx in list_graph[iIdx]:if not dfs_checkring(jIdx, list_graph, ringflags):return Falseringflags[iIdx] = -1return Truelist_graph = [[] for x in range(numCourses) ]list_flags = [0 for x in range(numCourses)]for a, b in prerequisites:list_graph[b].append(a)for iIdx in range(numCourses):if not dfs_checkring(iIdx, list_graph, list_flags):return Falsereturn Trueprint(f'prerequisites count of the Courses = {len(check_prerequisites)}')
result = cfp.getTimeMemoryStr(Solution.canFinish_ext2, aSolution, 50000, check_prerequisites)
print(result['msg'], '執行結果 = {}'.format(result['result']))# 運行結果
prerequisites count of the Courses = 49999
函數 canFinish_ext2 的運行時間為 80.01 ms；內存使用量為 520.00 KB 執行結果 = True
4) 改進版三【迭代剝離+計數器檢測】
特殊的迭代思路
- 首先必須存在沒有任何前置的科目，否則第一門科目都沒有辦法學習，直接返回False；由此可建立沒有前置科目的隊列
- 迭代沒有前置科目的隊列，逐步剝離此科目后置科目的計數器，如果后置科目的前置計數器清零，則作為無前置科目放入隊列
- 迭代完畢后檢測有效科目數量是否達標
頁面功能測試，馬馬虎虎，超過55%
import CheckFuncPerf as cfpclass Solution:def canFinish_ext3(self, numCourses, prerequisites):from collections import deque, defaultdictdeque_graph = defaultdict(list)learned = [0] * numCoursesfor course, visited in prerequisites:deque_graph[visited].append(course)learned[course] += 1queue = deque([x for x in range(numCourses) if learned[x] == 0])processed_courses = 0while queue:visited = queue.popleft()processed_courses += 1for course in deque_graph[visited]:learned[course] -= 1if learned[course] == 0:queue.append(course)return processed_courses >= numCoursesprint(f'prerequisites count of the Courses = {len(check_prerequisites)}')
result = cfp.getTimeMemoryStr(Solution.canFinish_ext3, aSolution, 50000, check_prerequisites)
print(result['msg'], '執行結果 = {}'.format(result['result']))# 運行結果
prerequisites count of the Courses = 49999
函數 canFinish_ext3 的運行時間為 84.02 ms；內存使用量為 584.00 KB 執行結果 = True
4. 最優算法
根據本地日志分析，最優算法為第2種方式【循環+遞歸+緩存】canFinish_ext1
由于四段代碼思路一致，主要是使用的數據結構不同，因此經驗推出以下結論：
- 在作為隊列使用時【先進先出】，
deque性能遠遠高于list - 迭代器循環優于循環中進行異常檢測
- 下標循環和枚舉循環性能基本一致
inumCourses = 50000
aSolution = Solution()
testcase_big = open(r'testcase/hot53_big5W.txt', mode='r', encoding='utf-8').read()
testcase_big = testcase_big.replace('[', '')
tmpItems = testcase_big.split(']')
check_pre = []
for aItem in tmpItems:tmpcurpre = aItem.split(',')if len(tmpcurpre) == 2:check_pre.append([int(tmpcurpre[0]), int(tmpcurpre[1])])
check_prerequisites = check_pre
print(f'prerequisites count of the Courses = {len(check_prerequisites)}')
result = cfp.getTimeMemoryStr(Solution.canFinish_base, aSolution, inumCourses, check_prerequisites)
print(result['msg'], '執行結果 = {}'.format(result['result']))
result = cfp.getTimeMemoryStr(Solution.canFinish_ext1, aSolution, inumCourses, check_prerequisites)
print(result['msg'], '執行結果 = {}'.format(result['result']))
result = cfp.getTimeMemoryStr(Solution.canFinish_ext2, aSolution, inumCourses, check_prerequisites)
print(result['msg'], '執行結果 = {}'.format(result['result']))
result = cfp.getTimeMemoryStr(Solution.canFinish_ext3, aSolution, inumCourses, check_prerequisites)
print(result['msg'], '執行結果 = {}'.format(result['result']))# 算法本地速度實測比較
prerequisites count of the Courses = 49999
函數 canFinish_base 的運行時間為 50813.51 ms；內存使用量為 7264.00 KB 執行結果 = True
函數 canFinish_ext1 的運行時間為 66.02 ms；內存使用量為 6112.00 KB 執行結果 = True
函數 canFinish_ext2 的運行時間為 80.01 ms；內存使用量為 520.00 KB 執行結果 = True
函數 canFinish_ext3 的運行時間為 84.02 ms；內存使用量為 584.00 KB 執行結果 = True
5. 相關資源
本文代碼已上傳到CSDN，地址：Python算法題源代碼_LeetCode(力扣)_課程表
一日練，一日功，一日不練十日空
may the odds be ever in your favor ~
）之setUp 線程組)
