網(wǎng)站跳出率多少合適,鄭州網(wǎng)站優(yōu)化哪家好,東營,網(wǎng)站安全 重要性算法綜合訓練#xff1a;五類編程題深度解析與實踐 引言 算法是計算機科學的核心#xff0c;也是編程能力的重要體現(xiàn)。在實際編程和算法競賽中#xff0c;我們常常會遇到各種類型的題目#xff0c;它們考察不同的算法思想和編程技巧。本文將通過五類共十四道編程題的詳細解…算法綜合訓練五類編程題深度解析與實踐引言算法是計算機科學的核心也是編程能力的重要體現(xiàn)。在實際編程和算法競賽中我們常常會遇到各種類型的題目它們考察不同的算法思想和編程技巧。本文將通過五類共十四道編程題的詳細解析系統(tǒng)性地講解滑動窗口、動態(tài)規(guī)劃、排列枚舉、圖論和樹結構等核心算法知識。每道題目都配有完整的代碼實現(xiàn)和詳細的分析旨在幫助讀者從算法入門逐步進階到中級水平。核心總結本文涉及的編程題分為五類每類題目考察不同的算法重點A類 - 能源傳輸線路共四道變種題考察滑動窗口與雙端隊列的應用屬于偏易難度B類 - 工匠帝國共四道變種題以動態(tài)規(guī)劃01背包/完全背包為核心難度中等C類 - 才藝表演排列共四道變種題考察全排列枚舉與驗證邏輯屬于偏易難度D類 - 圓環(huán)館連通性判斷一道核心題綜合數(shù)學映射、并查集、LCA/線段樹難度中等偏上E類 - 隊列鏈判斷一道核心題考察樹結構隊列操作涉及多算法融合與大數(shù)據(jù)優(yōu)化這些題目整體適配算法入門至進階階段的學習者通過變種題的對比分析可以深入理解同一核心思想在不同約束條件下的應用。A - 能源傳輸線路題目概述能源傳輸線路問題是一個經(jīng)典的滑動窗口應用場景。問題描述給定一條能源傳輸線路上的多個節(jié)點每個節(jié)點有一定的能量值。我們需要判斷是否存在一個連續(xù)的子線路即連續(xù)的一段節(jié)點使得該子線路的總能量不低于某個閾值。不同變種在閾值、輸入輸出格式上略有差異。算法核心滑動窗口與雙端隊列滑動窗口算法是處理連續(xù)子數(shù)組/子區(qū)間問題的利器時間復雜度可以從暴力解的O(n2)優(yōu)化到O(n)。當需要維護窗口內的最大值/最小值時雙端隊列是高效的數(shù)據(jù)結構選擇?；瑒哟翱诨舅枷雂efsliding_window_basic(nums,k):基本滑動窗口示例計算大小為k的窗口的和ifnotnumsork0:return[]nlen(nums)ifkn:return[]result[]window_sumsum(nums[:k])result.append(window_sum)foriinrange(k,n):# 滑動窗口去掉左邊元素添加右邊元素window_sumwindow_sum-nums[i-k]nums[i]result.append(window_sum)returnresult雙端隊列維護滑動窗口最值fromcollectionsimportdequedefmax_sliding_window(nums,k):使用雙端隊列維護滑動窗口最大值ifnotnumsork0:return[]nlen(nums)ifkn:kn result[]dqdeque()# 存儲索引對應元素單調遞減foriinrange(n):# 移除隊列中不在窗口范圍內的索引whiledqanddq[0]i-k1:dq.popleft()# 保持隊列單調遞減移除所有小于當前元素的索引whiledqandnums[dq[-1]]nums[i]:dq.pop()# 添加當前索引dq.append(i)# 當窗口形成時記錄結果ifik-1:result.append(nums[dq[0]])returnresultA1 - 能源傳輸線路能量閾值600含輸出YES/NO問題描述給定一個整數(shù)數(shù)組表示能源節(jié)點的能量值和一個整數(shù)閾值K600。判斷是否存在長度至少為1的連續(xù)子數(shù)組其元素之和不小于K。如果存在輸出YES否則輸出NO。解題思路這是滑動窗口的典型應用。我們可以使用前綴和優(yōu)化或者直接使用滑動窗口使用雙指針維護一個窗口當窗口和小于K時右指針向右移動擴大窗口當窗口和大于等于K時記錄結果并左指針右移縮小窗口時間復雜度O(n)代碼實現(xiàn)defenergy_transmission_A1(energy_nodes,K600): A1變種判斷是否存在連續(xù)子數(shù)組和≥K輸出YES/NO 使用滑動窗口解法 nlen(energy_nodes)ifn0:returnNOleft0current_sum0forrightinrange(n):current_sumenergy_nodes[right]# 當窗口和≥K時返回YESifcurrent_sumK:returnYES# 如果當前和變成負數(shù)重置窗口因為負數(shù)和會降低后續(xù)子數(shù)組的和ifcurrent_sum0:current_sum0leftright1# 如果所有元素都是負數(shù)需要單獨檢查ifmax(energy_nodes)0:returnYESifmax(energy_nodes)KelseNO# 嘗試以每個位置為起點的最大子數(shù)組和forleftinrange(n):current_sum0forrightinrange(left,n):current_sumenergy_nodes[right]ifcurrent_sumK:returnYESreturnNOdefenergy_transmission_A1_prefix(energy_nodes,K600): A1變種使用前綴和有序集合的解法 可以處理更大數(shù)據(jù)量和更復雜的情況 importbisect nlen(energy_nodes)ifn0:returnNO# 計算前綴和prefix_sum[0]*(n1)foriinrange(1,n1):prefix_sum[i]prefix_sum[i-1]energy_nodes[i-1]# 維護一個有序的前綴和列表sorted_prefix[0]# 初始前綴和為0foriinrange(1,n1):# 我們需要找到是否存在j i使得prefix_sum[i] - prefix_sum[j] K# 即prefix_sum[j] prefix_sum[i] - Ktargetprefix_sum[i]-K# 在有序列表中查找第一個≥target的位置posbisect.bisect_left(sorted_prefix,target)# 如果找到了這樣的位置說明存在符合條件的子數(shù)組ifposlen(sorted_prefix):returnYES# 將當前前綴和插入有序列表bisect.insort(sorted_prefix,prefix_sum[i])returnNO# 測試代碼deftest_A1():測試A1變種test_cases[([100,200,300,400],YES),# 100200300600([100,200,300],NO),# 最大和600但需要檢查具體組合([100,200,300,100],YES),# 200300100600([600],YES),# 單個元素等于600([599],NO),# 單個元素小于600([-100,700,-100],YES),# 700單獨就滿足([100,100,100,100,100,100],YES),# 6個100的和為600([100]*5,NO),# 5個100的和為500不夠]fori,(nodes,expected)inenumerate(test_cases):result1energy_transmission_A1(nodes)result2energy_transmission_A1_prefix(nodes)print(f測試用例{i1}:{nodes})print(f 滑動窗口結果:{result1}, 期望:{expected})print(f 前綴和結果:{result2}, 期望:{expected})print(f 測試{通過ifresult1expectedandresult2expectedelse失敗})print()A2 - 能源傳輸線路能量閾值500含輸出OK/-1問題描述給定能源節(jié)點能量值數(shù)組閾值K500。需要找到最短的連續(xù)子數(shù)組其元素之和不小于K。如果存在輸出最短長度OK否則輸出-1。解題思路這是A1的變種需要找到最短的滿足條件的子數(shù)組。可以使用滑動窗口的另一種形式右指針不斷向右移動擴大窗口當窗口和≥K時記錄窗口長度左指針向右移動嘗試縮小窗口同時保持窗口和≥K在移動過程中更新最短長度代碼實現(xiàn)defenergy_transmission_A2(energy_nodes,K500): A2變種找到最短的連續(xù)子數(shù)組其和≥K輸出長度或-1 使用滑動窗口求最短滿足條件的子數(shù)組 nlen(energy_nodes)ifn0:return-1left0current_sum0min_lengthfloat(inf)forrightinrange(n):current_sumenergy_nodes[right]# 當窗口滿足條件時嘗試縮小窗口whilecurrent_sumKandleftright:# 更新最小長度min_lengthmin(min_length,right-left1)# 嘗試縮小窗口左指針右移current_sum-energy_nodes[left]left1returnmin_lengthifmin_length!float(inf)else-1defenergy_transmission_A2_prefix_binary(energy_nodes,K500): A2變種使用前綴和二分查找的解法 對于每個位置i找到最小的j使得prefix_sum[i] - prefix_sum[j] K 時間復雜度O(n log n)適用于數(shù)據(jù)量大的情況 nlen(energy_nodes)ifn0:return-1# 計算前綴和prefix_sum[0]*(n1)foriinrange(1,n1):prefix_sum[i]prefix_sum[i-1]energy_nodes[i-1]min_lengthfloat(inf)# 對于每個結束位置i二分查找最小的開始位置jforiinrange(1,n1):# 我們需要找到最大的j使得prefix_sum[j] prefix_sum[i] - Ktargetprefix_sum[i]-K# 二分查找left,right0,iwhileleftright:mid(leftright1)//2ifprefix_sum[mid]target:leftmidelse:rightmid-1# 如果找到了合適的jifprefix_sum[left]target:min_lengthmin(min_length,i-left)returnmin_lengthifmin_length!float(inf)else-1# 測試代碼deftest_A2():測試A2變種test_cases[([100,200,300,400],2),# 300400700長度2([100,200,300],3),# 100200300600長度3([100,200,300,100],2),# 300100400不夠200300100600長度3300400700長度2([500],1),# 單個元素等于500([499],-1),# 單個元素小于500([100,400,100,100],2),# 400100500長度2([100]*6,5),# 需要5個100才能達到500([50]*20,10),# 需要10個50才能達到500]fori,(nodes,expected)inenumerate(test_cases):result1energy_transmission_A2(nodes)result2energy_transmission_A2_prefix_binary(nodes)print(f測試用例{i1}:{nodes})print(f 滑動窗口結果:{result1}, 期望:{expected})print(f 前綴和二分結果:{result2}, 期望:{expected})print(f 測試{通過ifresult1expectedandresult2expectedelse失敗})print()A3和A4變種A3和A4變種與A1和A2類似只是閾值不同A3閾值為500輸出YES/NOA4閾值為600輸出OK/-1。由于算法核心相同這里不再重復實現(xiàn)只展示通用解決方案defenergy_transmission_generic(energy_nodes,K,output_typeYES/NO): 通用能源傳輸線路解決方案 output_type: YES/NO 或 OK/-1 nlen(energy_nodes)ifoutput_typeYES/NO:# 類似A1/A3的邏輯# 這里使用前綴和有序集合的通用解法importbisectifn0:returnNOifK0elseYESprefix_sum[0]*(n1)foriinrange(1,n1):prefix_sum[i]prefix_sum[i-1]energy_nodes[i-1]sorted_prefix[0]foriinrange(1,n1):targetprefix_sum[i]-K posbisect.bisect_left(sorted_prefix,target)ifposlen(sorted_prefix):returnYESbisect.insort(sorted_prefix,prefix_sum[i])returnNOelse:# output_type OK/-1# 類似A2/A4的邏輯找最短長度ifn0:return-1ifK0else0left0current_sum0min_lengthfloat(inf)forrightinrange(n):current_sumenergy_nodes[right]whilecurrent_sumKandleftright:min_lengthmin(min_length,right-left1)current_sum-energy_nodes[left]left1returnmin_lengthifmin_length!float(inf)else-1B - 工匠帝國題目概述工匠帝國問題是一個典型的背包問題變種。問題描述工匠有n種材料每種材料有特定的價值需要判斷是否可以通過選擇材料組合達到目標價值。不同變種在目標價值、輸入輸出格式上略有差異。算法核心動態(tài)規(guī)劃01背包/完全背包背包問題是動態(tài)規(guī)劃的經(jīng)典問題分為01背包每種物品最多選一次和完全背包每種物品可以選多次。工匠帝國問題通?？梢越橥耆嘲鼏栴}。01背包基本解法defknapsack_01(weights,values,capacity):01背包問題基本解法nlen(weights)ifn0orcapacity0:return0# dp[i][w]表示前i個物品容量為w時的最大價值dp[[0]*(capacity1)for_inrange(n1)]foriinrange(1,n1):weightweights[i-1]valuevalues[i-1]forwinrange(1,capacity1):ifweightw:# 選擇放入或不放入dp[i][w]max(dp[i-1][w],dp[i-1][w-weight]value)else:# 不能放入dp[i][w]dp[i-1][w]returndp[n][capacity]defknapsack_01_optimized(weights,values,capacity):01背包問題空間優(yōu)化解法nlen(weights)ifn0orcapacity0:return0# 使用一維數(shù)組優(yōu)化空間dp[0]*(capacity1)foriinrange(n):weightweights[i]valuevalues[i]# 逆序遍歷確保每個物品只使用一次forwinrange(capacity,weight-1,-1):dp[w]max(dp[w],dp[w-weight]value)returndp[capacity]完全背包基本解法defknapsack_complete(weights,values,capacity):完全背包問題基本解法nlen(weights)ifn0orcapacity0:return0# dp[w]表示容量為w時的最大價值dp[0]*(capacity1)forwinrange(1,capacity1):foriinrange(n):ifweights[i]w:dp[w]max(dp[w],dp[w-weights[i]]values[i])returndp[capacity]defknapsack_complete_optimized(weights,values,capacity):完全背包問題優(yōu)化解法nlen(weights)ifn0orcapacity0:return0dp[0]*(capacity1)foriinrange(n):weightweights[i]valuevalues[i]# 正序遍歷允許重復使用物品forwinrange(weight,capacity1):dp[w]max(dp[w],dp[w-weight]value)returndp[capacity]B1 - 工匠帝國價格閾值5000含輸出YES/NO問題描述給定n種材料的價格判斷是否可以通過組合這些材料每種材料可以使用多次達到目標價格5000。如果可以輸出YES否則輸出NO。解題思路這是一個完全背包的變種問題但只需要判斷是否可以達到目標值而不是求最大價值。我們可以使用動態(tài)規(guī)劃dp[i]表示是否可以達到價格i初始化dp[0] True不選任何材料可以達到價格0對于每種材料更新dp數(shù)組最后返回dp[target]代碼實現(xiàn)defcraftsman_empire_B1(prices,target5000): B1變種判斷是否可以通過材料組合達到目標價格輸出YES/NO 使用完全背包的思路但只記錄可達性 iftarget0:returnYES# 使用動態(tài)規(guī)劃記錄可達價格dp[False]*(target1)dp[0]Trueforpriceinprices:ifpricetarget:# 完全背包正序遍歷foriinrange(price,target1):dp[i]dp[i]ordp[i-price]returnYESifdp[target]elseNOdefcraftsman_empire_B1_bfs(prices,target5000): B1變種使用BFS的解法 對于可達性問題BFS有時更直觀 iftarget0:returnYESfromcollectionsimportdeque visited[False]*(target1)visited[0]Truequeuedeque([0])whilequeue:currentqueue.popleft()forpriceinprices:next_pricecurrentpriceifnext_pricetarget:returnYESelifnext_pricetargetandnotvisited[next_price]:visited[next_price]Truequeue.append(next_price)returnNO# 測試代碼deftest_B1():測試B1變種test_cases[([1000,2000,3000],YES),# 10002000300060005000且1000*55000([1000,2000],YES),# 1000*55000([1001,2002],NO),# 無法組合出5000([5000],YES),# 直接達到5000([1],YES),# 5000個1可以組成5000([7,11,13],YES),# 需要找到組合比如7*71411*25000([10],YES),# 500個10可以組成5000([100,200,300],YES),# 可以組合出5000]fori,(prices,expected)inenumerate(test_cases):result1craftsman_empire_B1(prices)# BFS解法可能在大目標值時較慢這里僅對小目標值測試iftarget5000:result2craftsman_empire_B1_bfs(prices)print(f測試用例{i1}:{prices})print(f 動態(tài)規(guī)劃結果:{result1}, 期望:{expected})print(f BFS結果:{result2}, 期望:{expected})print(f 測試{通過ifresult1expectedandresult2expectedelse失敗})else:print(f測試用例{i1}:{prices})print(f 動態(tài)規(guī)劃結果:{result1}, 期望:{expected})print(f 測試{通過ifresult1expectedelse失敗})print()B2 - 工匠帝國價格閾值6000含輸出OK/-1問題描述給定n種材料的價格需要找到最少的材料數(shù)量使得總價格達到目標價格6000。如果可以輸出最少數(shù)量OK否則輸出-1。解題思路這是一個完全背包求最小物品數(shù)量的問題dp[i]表示達到價格i所需的最少材料數(shù)量初始化dp[0] 0其他為無窮大對于每種材料更新dp數(shù)組最后返回dp[target]如果不是無窮大代碼實現(xiàn)defcraftsman_empire_B2(prices,target6000): B2變種找到達到目標價格所需的最少材料數(shù)量輸出數(shù)量或-1 使用完全背包求最小數(shù)量 iftarget0:return0# dp[i]表示達到價格i所需的最少材料數(shù)量dp[float(inf)]*(target1)dp[0]0forpriceinprices:ifpricetarget:# 完全背包正序遍歷foriinrange(price,target1):ifdp[i-price]!float(inf):dp[i]min(dp[i],dp[i-price]1)returndp[target]ifdp[target]!float(inf)else-1defcraftsman_empire_B2_bfs(prices,target6000): B2變種使用BFS求最短路徑 將問題轉化為圖論問題節(jié)點表示價格邊表示使用一個材料 iftarget0:return0fromcollectionsimportdeque visited[False]*(target1)visited[0]Truequeuedeque([(0,0)])# (當前價格, 步數(shù))whilequeue:current,stepsqueue.popleft()forpriceinprices:next_pricecurrentpriceifnext_pricetarget:returnsteps1elifnext_pricetargetandnotvisited[next_price]:visited[next_price]Truequeue.append((next_price,steps1))return-1# 測試代碼deftest_B2():測試B2變種test_cases[([1000,2000,3000],2),# 300030006000需要2個([1000,2000],3),# 1000*66000需要6個2000*36000需要3個([1001,2002],-1),# 無法組合出6000([6000],1),# 直接達到6000([1],6000),# 需要6000個1([100,200,300],20),# 300*206000([10,20,50],120),# 50*1206000]fori,(prices,expected)inenumerate(test_cases):result1craftsman_empire_B2(prices)iftarget6000:result2craftsman_empire_B2_bfs(prices)print(f測試用例{i1}:{prices})print(f 動態(tài)規(guī)劃結果:{result1}, 期望:{expected})print(f BFS結果:{result2}, 期望:{expected})print(f 測試{通過ifresult1expectedandresult2expectedelse失敗})else:print(f測試用例{i1}:{prices})print(f 動態(tài)規(guī)劃結果:{result1}, 期望:{expected})print(f 測試{通過ifresult1expectedelse失敗})print()B3和B4變種B3和B4變種與B1和B2類似只是目標價格不同B3目標為6000輸出YES/NOB4目標為5000輸出OK/-1。我們可以使用通用解決方案defcraftsman_empire_generic(prices,target,output_typeYES/NO): 通用工匠帝國解決方案 output_type: YES/NO 或 OK/-1 ifoutput_typeYES/NO:# 可達性問題iftarget0:returnYESdp[False]*(target1)dp[0]Trueforpriceinprices:ifpricetarget:foriinrange(price,target1):dp[i]dp[i]ordp[i-price]returnYESifdp[target]elseNOelse:# output_type OK/-1# 最小數(shù)量問題iftarget0:return0dp[float(inf)]*(target1)dp[0]0forpriceinprices:ifpricetarget:foriinrange(price,target1):ifdp[i-price]!float(inf):dp[i]min(dp[i],dp[i-price]1)returndp[target]ifdp[target]!float(inf)else-1C - 才藝表演排列題目概述才藝表演排列問題考察全排列的生成與驗證。問題描述給定一組表演者和他們的表演類型如N、P等需要判斷是否存在某種排列方式滿足特定條件。不同變種在剔除類型、輸出格式上略有差異。算法核心全排列枚舉與驗證全排列問題可以通過回溯法解決。對于n個元素的排列總共有n!種可能。當n較大時直接枚舉所有排列可能不可行需要根據(jù)具體條件進行剪枝優(yōu)化。全排列基本解法defpermutations_basic(nums):全排列基本解法回溯法defbacktrack(path,used,result):iflen(path)len(nums):result.append(path[:])returnforiinrange(len(nums)):ifnotused[i]:used[i]Truepath.append(nums[i])backtrack(path,used,result)path.pop()used[i]Falseresult[]backtrack([],[False]*len(nums),result)returnresultdefpermutations_iterative(nums):全排列迭代解法使用字典序算法# 先排序numssorted(nums)result[nums[:]]whileTrue:# 1. 從右向左找到第一個遞減的元素ilen(nums)-2whilei0andnums[i]nums[i1]:i-1ifi0:break# 已經(jīng)是最后一個排列# 2. 從右向左找到第一個大于nums[i]的元素jlen(nums)-1whilenums[j]nums[i]:j-1# 3. 交換nums[i]和nums[j]nums[i],nums[j]nums[j],nums[i]# 4. 反轉i1到末尾的元素nums[i1:]reversed(nums[i1:])result.append(nums[:])returnresult帶限制條件的排列defpermutations_with_constraints(elements,constraints): 帶限制條件的全排列 constraints: 函數(shù)接受當前排列返回是否滿足條件 defbacktrack(path,used,result):iflen(path)len(elements):ifconstraints(path):result.append(path[:])returnforiinrange(len(elements)):ifnotused[i]:# 剪枝如果當前選擇不可能滿足條件跳過path.append(elements[i])# 這里可以添加更復雜的剪枝邏輯ifcan_continue(path,elements,used,constraints):used[i]Truebacktrack(path,used,result)used[i]Falsepath.pop()defcan_continue(path,elements,used,constraints):判斷當前部分排列是否還有可能滿足條件# 這里實現(xiàn)具體的剪枝邏輯# 例如檢查是否違反某些局部約束returnTrueresult[]backtrack([],[False]*len(elements),result)returnresultC1 - 才藝表演排列剔除類型N輸出YES/NO問題描述給定一個表演者列表每個表演者有一個類型N或P。需要判斷是否存在一種排列方式使得排列中不包含連續(xù)兩個類型為N的表演者。如果存在輸出YES否則輸出NO。解題思路這是一個典型的排列約束問題。我們可以使用貪心算法解決統(tǒng)計類型N和P的數(shù)量如果N的數(shù)量 P的數(shù)量 1則不可能滿足條件因為N不能相鄰否則我們可以構造一個排列將N插入P的間隔中更嚴謹?shù)慕夥ㄊ鞘褂没厮莘ㄋ阉鞔a實現(xiàn)deftalent_show_C1(performers): C1變種判斷是否存在排列使得沒有連續(xù)兩個N類型輸出YES/NO 使用貪心算法 # 統(tǒng)計N和P的數(shù)量count_Nperformers.count(N)count_Pperformers.count(P)# 如果N的數(shù)量比P的數(shù)量多1以上不可能滿足條件ifcount_Ncount_P1:returnNO# 特殊情況處理ifcount_N0:returnYES# 只有P類型肯定可以# 嘗試構造排列# 將N插入P的間隔中# P之間最多有count_P1個位置可以插入Nifcount_Ncount_P1:returnYESreturnNOdeftalent_show_C1_backtrack(performers): C1變種使用回溯法驗證是否存在滿足條件的排列 適用于小規(guī)模數(shù)據(jù) fromitertoolsimportpermutations# 如果表演者數(shù)量較多直接使用貪心算法的結果iflen(performers)10:returntalent_show_C1(performers)# 生成所有排列并檢查forperminpermutations(performers):validTrueforiinrange(1,len(perm)):ifperm[i]Nandperm[i-1]N:validFalsebreakifvalid:returnYESreturnNO# 測試代碼deftest_C1():測試C1變種test_cases[([N,P,P],YES),# 可以排列為P,N,P([N,N,P],YES),# 可以排列為N,P,N([N,N,N],NO),# 三個N不可能不連續(xù)([P,P,P],YES),# 只有P肯定可以([N,P],YES),# 可以排列為N,P或P,N([N,N,P,P],YES),# 可以排列為N,P,N,P([N,N,N,P],NO),# 三個N一個P不可能([N]*5[P]*4,NO),# 5個N4個P不可能([N]*3[P]*5,YES),# 3個N5個P可以]fori,(performers,expected)inenumerate(test_cases):result1talent_show_C1(performers)result2talent_show_C1_backtrack(performers)print(f測試用例{i1}:{performers})print(f 貪心算法結果:{result1}, 期望:{expected})print(f 回溯法結果:{result2}, 期望:{expected})print(f 測試{通過ifresult1expectedandresult2expectedelse失敗})print()C2 - 才藝表演排列剔除類型P輸出OK/-1問題描述給定表演者列表需要找到一種排列使得排列中不包含連續(xù)兩個類型為P的表演者。如果存在輸出一個滿足條件的排列OK否則輸出-1。解題思路與C1類似但需要輸出具體排列而不僅僅是判斷是否存在。我們可以使用構造法統(tǒng)計N和P的數(shù)量如果P的數(shù)量 N的數(shù)量 1則不可能否則我們可以構造排列將P插入N的間隔中或者交替排列代碼實現(xiàn)deftalent_show_C2(performers): C2變種找到一個排列使得沒有連續(xù)兩個P類型輸出排列或-1 使用構造法 # 分離N和P類型的表演者N_list[pforpinperformersifpN]P_list[pforpinperformersifpP]count_Nlen(N_list)count_Plen(P_list)# 如果P的數(shù)量比N的數(shù)量多1以上不可能ifcount_Pcount_N1:return-1# 構造排列result[]ifcount_Pcount_N:# P比N多1必須以P開始和結束result.append(P)foriinrange(count_N):result.append(N)result.append(P)elifcount_Pcount_N:# P和N數(shù)量相等可以交替排列foriinrange(count_N):result.append(P)result.append(N)else:# N比P多用N包圍P# 先放置所有P用N隔開foriinrange(count_P):result.append(N)result.append(P)# 添加剩余的Nresult.extend([N]*(count_N-count_P))# 驗證構造的排列foriinrange(1,len(result)):ifresult[i]Pandresult[i-1]P:# 構造失敗返回-1return-1return.join(result)ifresultelse-1deftalent_show_C2_backtrack(performers): C2變種使用回溯法找到一個滿足條件的排列 適用于小規(guī)模數(shù)據(jù) fromitertoolsimportpermutations# 如果表演者數(shù)量較多直接使用構造法的結果iflen(performers)10:returntalent_show_C2(performers)# 生成所有排列并檢查forperminpermutations(performers):validTrueforiinrange(1,len(perm)):ifperm[i]Pandperm[i-1]P:validFalsebreakifvalid:return.join(perm)return-1# 測試代碼deftest_C2():測試C2變種test_cases[([P,N,N],NPN),# 可以排列為N,P,N([P,P,N],PNP),# 可以排列為P,N,P([P,P,P],-1),# 三個P不可能不連續(xù)([N,N,N],NNN),# 只有N肯定可以([P,N],PN),# 可以排列為P,N([P,P,N,N],PNPN),# 可以排列為P,N,P,N([P,P,P,N],-1),# 三個P一個N不可能([P]*5[N]*4,-1),# 5個P4個N不可能([P]*3[N]*5,NPNPNNN),# 3個P5個N可以]fori,(performers,expected)inenumerate(test_cases):result1talent_show_C2(performers)result2talent_show_C2_backtrack(performers)print(f測試用例{i1}:{performers})print(f 構造法結果:{result1}, 期望:{expected})print(f 回溯法結果:{result2}, 期望:{expected})# 驗證結果ifexpected-1:successresult1-1andresult2-1else:# 檢查結果是否有效defis_valid(arrangement):ifarrangement-1:returnFalseforjinrange(1,len(arrangement)):ifarrangement[j]Pandarrangement[j-1]P:returnFalsereturnTruesuccessis_valid(result1)andis_valid(result2)print(f 測試{通過ifsuccesselse失敗})print()C3和C4變種C3和C4變種與C1和C2類似只是剔除的類型不同C3剔除P輸出YES/NOC4剔除N輸出OK/-1。我們可以使用通用解決方案deftalent_show_generic(performers,exclude_type,output_typeYES/NO): 通用才藝表演排列解決方案 exclude_type: N 或 P表示不能連續(xù)的類型 output_type: YES/NO 或 OK/-1 # 統(tǒng)計兩種類型的數(shù)量count_excludeperformers.count(exclude_type)count_otherlen(performers)-count_excludeifexclude_typeN:# 不能連續(xù)Nifcount_excludecount_other1:ifoutput_typeYES/NO:returnNOelse:return-1else:# 不能連續(xù)Pifcount_excludecount_other1:ifoutput_typeYES/NO:returnNOelse:return-1ifoutput_typeYES/NO:returnYESelse:# 需要構造具體排列ifexclude_typeN:# 構造不連續(xù)N的排列N_list[N]*count_exclude other_list[P]*count_otherifcount_excludecount_other:result[N]foriinrange(count_other):result.append(P)result.append(N)elifcount_excludecount_other:result[]foriinrange(count_exclude):result.append(N)result.append(P)else:result[]foriinrange(count_exclude):result.append(P)result.append(N)result.extend([P]*(count_other-count_exclude))else:# 構造不連續(xù)P的排列P_list[P]*count_exclude other_list[N]*count_otherifcount_excludecount_other:result[P]foriinrange(count_other):result.append(N)result.append(P)elifcount_excludecount_other:result[]foriinrange(count_exclude):result.append(P)result.append(N)else:result[]foriinrange(count_exclude):result.append(N)result.append(P)result.extend([N]*(count_other-count_exclude))# 驗證構造的排列foriinrange(1,len(result)):ifresult[i]exclude_typeandresult[i-1]exclude_type:return-1return.join(result)D - 圓環(huán)館連通性判斷題目概述圓環(huán)館連通性判斷是一個綜合性的圖論問題。問題描述有n個圓環(huán)館呈環(huán)狀排列每個館與相鄰館有通道連接。某些通道可能被關閉需要判斷任意兩個館是否連通。這個問題涉及數(shù)學映射、并查集、LCA最近公共祖先和線段樹等多種算法。算法核心并查集與環(huán)狀結構處理并查集基本實現(xiàn)classUnionFind:并查集實現(xiàn)def__init__(self,n):self.parentlist(range(n))self.rank[0]*ndeffind(self,x):查找根節(jié)點帶路徑壓縮ifself.parent[x]!x:self.parent[x]self.find(self.parent[x])returnself.parent[x]defunion(self,x,y):合并兩個集合root_xself.find(x)root_yself.find(y)ifroot_xroot_y:returnFalse# 按秩合并ifself.rank[root_x]self.rank[root_y]:self.parent[root_x]root_yelifself.rank[root_x]self.rank[root_y]:self.parent[root_y]root_xelse:self.parent[root_y]root_x self.rank[root_x]1returnTruedefconnected(self,x,y):判斷兩個元素是否連通returnself.find(x)self.find(y)環(huán)狀結構處理技巧defcircular_array_handling(n):環(huán)狀數(shù)組處理技巧# 對于環(huán)狀結構索引i的下一個位置是(i1)%n# 前一個位置是(i-1n)%n# 示例判斷環(huán)上兩點是否連通defis_connected_circular(connections,start,end): connections: 連接狀態(tài)列表True表示通道開放 start, end: 起點和終點索引 返回是否連通 # 方法1順時針檢查currentstartwhileTrue:ifcurrentend:returnTrueifconnections[current]:# 如果通道開放current(current1)%nelse:breakifcurrentstart:# 回到起點break# 方法2逆時針檢查currentstartwhileTrue:ifcurrentend:returnTrueprev(current-1n)%nifconnections[prev]:# 如果通道開放currentprevelse:breakifcurrentstart:# 回到起點breakreturnFalsereturnis_connected_circularD - 圓環(huán)館連通性判斷完整實現(xiàn)問題描述有n個圓環(huán)館編號0到n-1呈環(huán)狀排列初始時所有相鄰館之間的通道都是開放的。會有一系列操作關閉通道關閉館i和館(i1)%n之間的通道打開通道打開館i和館(i1)%n之間的通道查詢連通性查詢館a和館b是否連通需要高效處理這些操作。解題思路這個問題可以有多種解法簡單方法每次查詢時BFS/DFS遍歷時間復雜度O(n)每次查詢不適用于頻繁查詢并查集方法使用并查集維護連通分量但環(huán)狀結構需要特殊處理線段樹方法將環(huán)展開為線段使用線段樹維護區(qū)間連通性LCA方法將環(huán)視為樹斷開一條邊使用LCA判斷連通性這里我們實現(xiàn)并查集和線段樹兩種方法。方法1并查集實現(xiàn)classCircularMuseumUF:圓環(huán)館連通性判斷 - 并查集實現(xiàn)def__init__(self,n):self.nn# 通道狀態(tài)True表示開放False表示關閉self.channels[True]*n# 并查集self.ufUnionFind(n)# 初始時所有通道開放所有館連通# 實際上不需要特殊初始化因為查詢時會根據(jù)通道狀態(tài)動態(tài)判斷defclose_channel(self,i):關閉館i和館(i1)%n之間的通道if0iself.n:self.channels[i]Falsedefopen_channel(self,i):打開館i和館(i1)%n之間的通道if0iself.n:self.channels[i]Truedefis_connected(self,a,b):判斷館a和館b是否連通ifab:returnTrue# 使用BFS判斷連通性fromcollectionsimportdeque visited[False]*self.n queuedeque([a])visited[a]Truewhilequeue:currentqueue.popleft()ifcurrentb:returnTrue# 檢查兩個方向# 順時針方向next_idx(current1)%self.nifself.channels[current]andnotvisited[next_idx]:visited[next_idx]Truequeue.append(next_idx)# 逆時針方向prev_idx(current-1self.n)%self.nifself.channels[prev_idx]andnotvisited[prev_idx]:visited[prev_idx]Truequeue.append(prev_idx)returnFalseclassCircularMuseumUFOptimized:圓環(huán)館連通性判斷 - 優(yōu)化的并查集實現(xiàn)def__init__(self,n):self.nn# 通道狀態(tài)self.channels[True]*n# 使用并查集但需要處理環(huán)狀結構# 我們將環(huán)斷開為線段來處理self.ufUnionFind(n)self.update_connectivity()defupdate_connectivity(self):更新連通性基于當前通道狀態(tài)重建并查集# 重置并查集self.ufUnionFind(self.n)# 根據(jù)通道狀態(tài)合并連通分量foriinrange(self.n):ifself.channels[i]:# 如果通道開放self.uf.union(i,(i1)%self.n)defclose_channel(self,i):關閉通道并更新連通性if0iself.n:self.channels[i]Falseself.update_connectivity()defopen_channel(self,i):打開通道并更新連通性if0iself.n:self.channels[i]Trueself.update_connectivity()defis_connected(self,a,b):判斷是否連通returnself.uf.connected(a,b)方法2線段樹實現(xiàn)classSegmentTreeCircular:圓環(huán)館連通性判斷 - 線段樹實現(xiàn)classNode:def__init__(self,left_connected,right_connected,full_connected):self.left_connectedleft_connected# 左端點是否與右端點連通通過區(qū)間內部self.right_connectedright_connected# 右端點是否與左端點連通通過區(qū)間內部self.full_connectedfull_connected# 區(qū)間是否完全連通def__init__(self,n):self.nn self.tree[self.Node(False,False,False)for_inrange(4*n)]self.channels[True]*n self.build(1,0,n-1)defbuild(self,node,l,r):構建線段樹iflr:# 單個節(jié)點自然是連通的self.tree[node]self.Node(True,True,True)returnmid(lr)//2self.build(node*2,l,mid)self.build(node*21,mid1,r)self.push_up(node,l,r)defpush_up(self,node,l,r):向上更新節(jié)點信息iflr:returnmid(lr)//2left_nodeself.tree[node*2]right_nodeself.tree[node*21]# 獲取中間通道狀態(tài)channel_openself.channels[mid]# 計算當前節(jié)點的信息new_nodeself.Node(False,False,False)# 左端點連通性new_node.left_connectedleft_node.left_connectedifleft_node.full_connectedandchannel_open:new_node.left_connectednew_node.left_connectedorright_node.left_connected# 右端點連通性new_node.right_connectedright_node.right_connectedifright_node.full_connectedandchannel_open:new_node.right_connectednew_node.right_connectedorleft_node.right_connected# 完全連通性new_node.full_connectedleft_node.full_connectedandright_node.full_connectedandchannel_open self.tree[node]new_nodedefupdate(self,idx,is_open):更新通道狀態(tài)ifidx0oridxself.n:returnself.channels[idx]is_open self._update(1,0,self.n-1,idx)def_update(self,node,l,r,idx):內部更新函數(shù)iflr:returnmid(lr)//2ifidxmid:self._update(node*2,l,mid,idx)else:self._update(node*21,mid1,r,idx)self.push_up(node,l,r)defquery(self,a,b):查詢a和b是否連通ifab:returnTrue# 確保a bifab:a,bb,a# 查詢區(qū)間[a, b]的連通性resultself._query(1,0,self.n-1,a,b)returnresult.left_connecteddef_query(self,node,l,r,ql,qr):內部查詢函數(shù)ifqllandrqr:returnself.tree[node]mid(lr)//2ifqrmid:returnself._query(node*2,l,mid,ql,qr)elifqlmid:returnself._query(node*21,mid1,r,ql,qr)else:# 跨越左右子區(qū)間left_resultself._query(node*2,l,mid,ql,qr)right_resultself._query(node*21,mid1,r,ql,qr)# 合并結果mergedself.Node(False,False,False)# 獲取中間通道狀態(tài)channel_openself.channels[mid]ifmidqlandmid1qrelseTrue# 計算合并后的連通性merged.left_connectedleft_result.left_connectedifleft_result.full_connectedandchannel_open:merged.left_connectedmerged.left_connectedorright_result.left_connected merged.right_connectedright_result.right_connectedifright_result.full_connectedandchannel_open:merged.right_connectedmerged.right_connectedorleft_result.right_connected merged.full_connectedleft_result.full_connectedandright_result.full_connectedandchannel_openreturnmergeddefis_connected_circular(self,a,b):環(huán)狀查詢考慮環(huán)狀特性ifab:returnTrue# 嘗試兩個方向# 方向1從a到b順時針ifab:result1self.query(a,b-1)else:result1self.query(a,self.n-1)andself.query(0,b-1)# 方向2從a到b逆時針ifab:result2self.query(b,a-1)else:result2self.query(b,self.n-1)andself.query(0,a-1)returnresult1orresult2完整測試代碼deftest_circular_museum():測試圓環(huán)館連通性判斷print(測試圓環(huán)館連通性判斷)print(*50)# 測試用例1簡單情況n5museum_ufCircularMuseumUF(n)museum_stSegmentTreeCircular(n)# 初始狀態(tài)所有館應該連通print(測試用例1初始狀態(tài))foriinrange(n):forjinrange(n):uf_resultmuseum_uf.is_connected(i,j)st_resultmuseum_st.is_connected_circular(i,j)ifij:assertuf_resultTrueassertst_resultTrueelse:assertuf_resultTrueassertst_resultTrueprint( 初始狀態(tài)測試通過)# 測試用例2關閉一個通道print( 測試用例2關閉通道0)museum_uf.close_channel(0)museum_st.update(0,False)# 檢查連通性test_pairs[(0,1),(0,2),(1,4)]expected[False,True,True]# 通道0關閉0和1不連通for(a,b),expinzip(test_pairs,expected):uf_resultmuseum_uf.is_connected(a,b)st_resultmuseum_st.is_connected_circular(a,b)print(f 館{a}和館: UF{uf_result}, ST{st_result}, 期望{exp})assertuf_resultexpassertst_resultexp# 測試用例3再關閉一個通道print( 測試用例3關閉通道2)museum_uf.close_channel(2)museum_st.update(2,False)test_pairs[(0,3),(1,3),(2,4)]expected[True,False,True]for(a,b),expinzip(test_pairs,expected):uf_resultmuseum_uf.is_connected(a,b)st_resultmuseum_st.is_connected_circular(a,b)print(f 館{a}和館: UF{uf_result}, ST{st_result}, 期望{exp})assertuf_resultexpassertst_resultexp# 測試用例4打開一個通道print( 測試用例4打開通道0)museum_uf.open_channel(0)museum_st.update(0,True)test_pairs[(0,1),(0,4),(1,3)]expected[True,True,False]# 通道2仍然關閉for(a,b),expinzip(test_pairs,expected):uf_resultmuseum_uf.is_connected(a,b)st_resultmuseum_st.is_connected_circular(a,b)print(f 館{a}和館: UF{uf_result}, ST{st_result}, 期望{exp})assertuf_resultexpassertst_resultexpprint( 所有測試用例通過)E - 隊列鏈判斷樹結構隊列操作題目概述隊列鏈判斷問題涉及樹結構的操作。問題描述有一棵樹每個節(jié)點有一個隊列。支持兩種操作向某個節(jié)點的隊列中添加元素查詢從節(jié)點u到節(jié)點v的路徑上所有隊列中第k小的元素這是一個綜合性的數(shù)據(jù)結構問題需要結合樹路徑查詢和區(qū)間第k小查詢。算法核心樹鏈剖分與主席樹樹鏈剖分基本概念樹鏈剖分是將樹分解為多條鏈使得樹上的路徑可以由O(log n)條鏈表示。結合線段樹等數(shù)據(jù)結構可以高效處理樹上的路徑查詢。主席樹可持久化線段樹主席樹用于解決區(qū)間第k小問題。對于樹上的每個節(jié)點我們可以建立從根到該節(jié)點路徑的主席樹然后通過差分思想得到任意路徑的信息。算法設計樹鏈剖分將樹分解為重鏈DFS序獲得樹的歐拉序主席樹為每個節(jié)點建立權值線段樹路徑查詢對于路徑(u, v)通過LCA和主席樹差分查詢第k小E - 隊列鏈判斷完整實現(xiàn)classQueueChainTree:隊列鏈判斷 - 樹結構隊列操作def__init__(self,n,valuesNone): 初始化 n: 節(jié)點數(shù)量 values: 每個節(jié)點的初始值列表 self.nn self.adj[[]for_inrange(n1)]# 鄰接表節(jié)點從1開始編號self.valuesvaluesifvalueselse[0]*(n1)# 樹鏈剖分相關數(shù)組self.parent[0]*(n1)# 父節(jié)點self.depth[0]*(n1)# 深度self.size[0]*(n1)# 子樹大小self.heavy[-1]*(n1)# 重兒子self.head[0]*(n1)# 鏈頭self.pos[0]*(n1)# DFS序位置self.cur_pos0# 主席樹相關self.roots[0]*(n1)# 每個DFS序位置的主席樹根self.sorted_values[]# 所有值的排序去重列表self.value_to_idx{}# 值到索引的映射# 初始化主席樹的值域self.init_value_mapping()definit_value_mapping(self):初始化值域映射all_valuesset()foriinrange(1,self.n1):all_values.add(self.values[i])self.sorted_valuessorted(all_values)foridx,valinenumerate(self.sorted_values):self.value_to_idx[val]idx1# 索引從1開始defadd_edge(self,u,v):添加邊self.adj[u].append(v)self.adj[v].append(u)defdfs_size(self,u,p):第一次DFS計算子樹大小和重兒子self.size[u]1self.parent[u]p max_size0forvinself.adj[u]:ifv!p:self.depth[v]self.depth[u]1self.dfs_size(v,u)self.size[u]self.size[v]ifself.size[v]max_size:max_sizeself.size[v]self.heavy[u]vdefdfs_decompose(self,u,h):第二次DFS樹鏈剖分self.head[u]h self.pos[u]self.cur_pos self.cur_pos1ifself.heavy[u]!-1:self.dfs_decompose(self.heavy[u],h)forvinself.adj[u]:ifv!self.parent[u]andv!self.heavy[u]:self.dfs_decompose(v,v)defbuild_hld(self,root1):構建樹鏈剖分self.depth[root]0self.dfs_size(root,0)self.cur_pos0self.dfs_decompose(root,root)# 主席樹實現(xiàn)classPersistentSegmentTree:可持久化線段樹主席樹classNode:def__init__(self,left0,right0,count0):self.leftleft# 左兒子索引self.rightright# 右兒子索引self.countcount# 值出現(xiàn)次數(shù)def__init__(self,values):self.valuesvalues self.nlen(values)self.nodes[self.Node()]self.roots[0]defupdate(self,prev_root,l,r,idx,val):更新在prev_root的基礎上將idx位置的值增加val返回新根# 創(chuàng)建新節(jié)點new_nodeself.Node()new_rootlen(self.nodes)self.nodes.append(new_node)iflr:self.nodes[new_root].countself.nodes[prev_root].countvalreturnnew_root mid(lr)//2ifidxmid:# 左子樹更新self.nodes[new_root].leftself.update(self.nodes[prev_root].left,l,mid,idx,val)self.nodes[new_root].rightself.nodes[prev_root].rightelse:# 右子樹更新self.nodes[new_root].leftself.nodes[prev_root].left self.nodes[new_root].rightself.update(self.nodes[prev_root].right,mid1,r,idx,val)# 更新計數(shù)self.nodes[new_root].count(self.nodes[self.nodes[new_root].left].countself.nodes[self.nodes[new_root].right].count)returnnew_rootdefquery_kth(self,root1,root2,root_lca,root_parent_lca,l,r,k):查詢第k小的值iflr:returnl left_count(self.nodes[self.nodes[root1].left].countself.nodes[self.nodes[root2].left].count-self.nodes[self.nodes[root_lca].left].count-self.nodes[self.nodes[root_parent_lca].left].count)mid(lr)//2ifkleft_count:returnself.query_kth(self.nodes[root1].left,self.nodes[root2].left,self.nodes[root_lca].left,self.nodes[root_parent_lca].left,l,mid,k)else:returnself.query_kth(self.nodes[root1].right,self.nodes[root2].right,self.nodes[root_lca].right,self.nodes[root_parent_lca].right,mid1,r,k-left_count)defbuild_persistent_segment_tree(self):構建主席樹# 初始化主席樹self.pstself.PersistentSegmentTree(self.sorted_values)# 按照DFS序構建主席樹dfs_order[0]*(self.n1)foriinrange(1,self.n1):dfs_order[self.pos[i]]i# 構建主席樹foriinrange(self.n):nodedfs_order[i]value_idxself.value_to_idx[self.values[node]]prev_rootself.roots[i-1]ifi0else0self.roots[i]self.pst.update(prev_root,1,len(self.sorted_values),value_idx,1)deflca(self,u,v):求最近公共祖先使用樹鏈剖分whileself.head[u]!self.head[v]:ifself.depth[self.head[u]]self.depth[self.head[v]]:uself.parent[self.head[u]]else:vself.parent[self.head[v]]returnuifself.depth[u]self.depth[v]elsevdefquery_path_kth(self,u,v,k):查詢路徑u-v上的第k小值ifk0orkself.depth[u]self.depth[v]-2*self.depth[self.lca(u,v)]1:return-1# k超出范圍lca_nodeself.lca(u,v)parent_lcaself.parent[lca_node]# 獲取四個根節(jié)點root_uself.roots[self.pos[u]]root_vself.roots[self.pos[v]]root_lcaself.roots[self.pos[lca_node]]root_parent_lcaself.roots[self.pos[parent_lca]]ifparent_lca!0else0# 查詢第k小idxself.pst.query_kth(root_u,root_v,root_lca,root_parent_lca,1,len(self.sorted_values),k)# 將索引轉換回原始值returnself.sorted_values[idx-1]defadd_value_to_node(self,u,value):向節(jié)點u的隊列添加值簡化版更新節(jié)點值# 在實際問題中每個節(jié)點可能有一個隊列這里簡化為更新節(jié)點值# 完整實現(xiàn)需要支持動態(tài)添加值這需要更復雜的數(shù)據(jù)結構self.values[u]value# 重新構建值域映射和主席樹self.init_value_mapping()self.build_persistent_segment_tree()defsolve_queries(self,queries):處理查詢results[]forqueryinqueries:ifquery[0]1:# 添加值u,valuequery[1],query[2]self.add_value_to_node(u,value)elifquery[0]2:# 查詢第k小u,v,kquery[1],query[2],query[3]resultself.query_path_kth(u,v,k)results.append(result)returnresultsdeftest_queue_chain_tree():測試隊列鏈判斷print(測試隊列鏈判斷樹結構隊列操作)print(*50)# 構建一棵樹n7values[0,5,3,7,1,6,4,2]# 節(jié)點1~7的值treeQueueChainTree(n,values)# 添加邊edges[(1,2),(1,3),(2,4),(2,5),(3,6),(3,7)]foru,vinedges:tree.add_edge(u,v)# 構建樹鏈剖分和主席樹tree.build_hld(1)tree.build_persistent_segment_tree()# 測試查詢test_queries[(2,4,5,2),# 查詢路徑4-5的第2小值(2,6,7,1),# 查詢路徑6-7的第1小值(2,1,7,4),# 查詢路徑1-7的第4小值]expected_results[3,2,5]# 根據(jù)樹的值計算fori,(query_type,u,v,k)inenumerate(test_queries):ifquery_type2:resulttree.query_path_kth(u,v,k)print(f查詢路徑{u}-{v}的第{k}小值:{result}, 期望:{expected_results[i]})assertresultexpected_results[i]print( 基本查詢測試通過)# 測試添加值后查詢print( 測試添加值后查詢)# 向節(jié)點4添加值8tree.add_value_to_node(4,8)# 重新查詢resulttree.query_path_kth(4,5,2)print(f添加值后查詢路徑4-5的第2小值:{result})# 路徑4-5上的值4(8), 2(3), 5(6) - 排序后3,6,8 - 第2小是6assertresult6print(添加值測試通過)print( 所有測試用例通過)總結與拓展通過以上五類十四道編程題的詳細解析我們系統(tǒng)性地學習了多種重要算法和數(shù)據(jù)結構算法思想總結滑動窗口與雙端隊列用于解決連續(xù)子數(shù)組/子區(qū)間問題特別是需要維護窗口內最值的情況動態(tài)規(guī)劃背包問題解決最優(yōu)化問題特別是資源分配和組合優(yōu)化問題排列枚舉與回溯解決排列組合和約束滿足問題并查集高效處理連通性問題和集合合并問題樹鏈剖分與主席樹解決樹上的路徑查詢問題特別是區(qū)間統(tǒng)計類查詢學習建議從簡單到復雜先掌握基礎算法思想再學習高級數(shù)據(jù)結構和算法理解變種通過同一問題的不同變種深入理解算法的核心思想實踐編碼多寫代碼理解算法的實現(xiàn)細節(jié)和邊界條件分析復雜度理解算法的時間復雜度和空間復雜度選擇合適的數(shù)據(jù)結構進一步學習方向高級圖論算法網(wǎng)絡流、匹配問題、強連通分量等字符串算法KMP、AC自動機、后綴數(shù)組等計算幾何凸包、最近點對、線段交等數(shù)學與數(shù)論快速冪、矩陣快速冪、組合數(shù)學等算法學習是一個循序漸進的過程需要不斷練習和思考。希望本文能夠幫助你在算法學習的道路上更進一步附錄完整代碼整合本文所有代碼已經(jīng)整合可以直接運行測試。建議讀者在學習時先理解算法思想嘗試自己實現(xiàn)代碼對比本文的實現(xiàn)優(yōu)化自己的代碼嘗試解決更多變種和類似問題祝你在算法學習的道路上越走越遠