2025年P(guān)ython高級編程沖刺押題試卷：核心算法實戰(zhàn)演練考試時間：______分鐘總分：______分姓名：______第一題請編寫一個Python函數(shù)，該函數(shù)接收一個字符串列表`words`作為輸入，并返回一個列表，列表中的元素是`words`中所有字符串的長度。要求使用生成器表達式來實現(xiàn)。第二題Python中裝飾器是強大的工具。請編寫一個裝飾器`@memoize`，用于自動為被裝飾的函數(shù)提供緩存功能。該裝飾器應(yīng)使用字典來存儲函數(shù)的參數(shù)和返回值。當(dāng)被裝飾的函數(shù)被調(diào)用時，首先檢查其參數(shù)是否已存在于緩存中，如果存在，則直接返回緩存中的值；如果不存在，則計算函數(shù)的返回值，將其存儲在緩存中，然后返回計算結(jié)果。假設(shè)被裝飾函數(shù)接受的參數(shù)都是可哈希的。第三題請實現(xiàn)一個函數(shù)`merge_sorted_lists`，該函數(shù)接收兩個已排序的整數(shù)列表`list1`和`list2`作為輸入，并返回一個新的列表，該列表包含`list1`和`list2`中的所有元素，且仍然是有序的。要求在合并過程中，只使用兩個指針分別遍歷`list1`和`list2`，不使用額外的排序算法，實現(xiàn)線性時間復(fù)雜度的合并。第四題給定一個由`'('`,`')'`,`{'}`,`'}'`,`'['`,`']'`六種括號組成的字符串`s`，請編寫一個函數(shù)`is_valid_parentheses`，判斷字符串中的括號是否有效。有效的括號字符串需要滿足：1.左括號必須與相同類型的右括號匹配。2.括號必須以正確的順序閉合。3.每個右括號都有一個對應(yīng)的相同類型的左括號。你可以使用棧這種數(shù)據(jù)結(jié)構(gòu)來輔助判斷。第五題請編寫一個函數(shù)`topological_sort`,實現(xiàn)有向無環(huán)圖（DAG）的拓?fù)渑判?。該函?shù)接收一個表示圖的字典`graph`，其中鍵是節(jié)點，值是該節(jié)點的鄰接節(jié)點列表。函數(shù)應(yīng)返回一個列表，包含圖中所有節(jié)點的拓?fù)渑判蛐蛄?。如果圖中存在環(huán)，則返回`None`。可以使用深度優(yōu)先搜索（DFS）算法來實現(xiàn)。第六題編寫一個函數(shù)`count_substrings`，接收一個字符串`s`作為輸入，返回`s`中所有不同子字符串的個數(shù)。子字符串是指字符串中連續(xù)的一段字符序列。注意：子字符串是原始字符串的一部分，順序與原字符串一致。例如，對于`s="abcabc"`，其子字符串包括"a","b","c","ab","bc","ca","abc","bca","abc","cabc"共10個。第七題請實現(xiàn)一個算法，找出數(shù)組中未排序的區(qū)間。給定一個整數(shù)數(shù)組`nums`，找出其中未排序的連續(xù)子數(shù)組的最小索引`start`和最大索引`end`，使得如果將`nums[start..end]`排序，那么整個數(shù)組也會變?yōu)橛行?。假設(shè)整個數(shù)組可能已經(jīng)排序，也可能完全未排序。第八題請編寫一個函數(shù)`four_sum`，找出數(shù)組中四數(shù)相加等于給定目標(biāo)值的所有不重復(fù)的四元組。你可以假設(shè)每個輸入都只對應(yīng)一個答案，但不允許重復(fù)的四元組。例如，給定數(shù)組`nums=[1,0,-1,0,-2,2]`，目標(biāo)值`target=0`，函數(shù)應(yīng)返回`[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]`。試卷答案第一題答案```pythondeflengths(words):return(len(word)forwordinwords)```解析思路：本題考察生成器表達式的使用。生成器表達式與列表推導(dǎo)式語法相似，但使用圓括號`()`而不是方括號`[]`。它不會立即計算并存儲所有結(jié)果，而是在迭代時按需生成每個元素。函數(shù)接收字符串列表`words`，通過`(len(word)forwordinwords)`創(chuàng)建一個生成器，當(dāng)?shù)鷃lengths`函數(shù)返回的結(jié)果時，會依次產(chǎn)生`words`中每個字符串的長度。第二題答案```pythondefmemoize(func):cache={}defwrapper(*args):ifargsincache:returncache[args]result=func(*args)cache[args]=resultreturnresultreturnwrapper@memoizedefsome_computation(a,b):#模擬復(fù)雜計算returna+b#示例：實際應(yīng)用中應(yīng)為更復(fù)雜的邏輯```解析思路：本題考察裝飾器的實現(xiàn)，特別是帶參數(shù)的裝飾器。裝飾器本質(zhì)上是一個返回函數(shù)的函數(shù)。`@memoize`裝飾器接收一個函數(shù)`func`作為參數(shù)。內(nèi)部定義了一個`wrapper`函數(shù)，它接收任意數(shù)量的參數(shù)`*args`。`wrapper`函數(shù)首先檢查`args`(函數(shù)調(diào)用時傳入的參數(shù)元組)是否存在于一個名為`cache`的字典中。如果存在，直接返回緩存的結(jié)果。如果不存在，調(diào)用原始函數(shù)`func(*args)`進行計算，將結(jié)果存入`cache`字典，并返回計算結(jié)果。最后，`memoize`函數(shù)返回`wrapper`函數(shù)。使用`@memoize`裝飾`some_computation`函數(shù)后，對該函數(shù)的調(diào)用會被`wrapper`函數(shù)攔截，從而實現(xiàn)緩存。第三題答案```pythondefmerge_sorted_lists(list1,list2):merged=[]i,j=0,0len1,len2=len(list1),len(list2)whilei<len1andj<len2:iflist1[i]<list2[j]:merged.append(list1[i])i+=1else:merged.append(list2[j])j+=1#將剩余元素添加到合并后的列表末尾merged.extend(list1[i:])merged.extend(list2[j:])returnmerged```解析思路：本題考察雙指針法在合并有序數(shù)組中的應(yīng)用。初始化一個空列表`merged`用于存儲結(jié)果，以及兩個指針`i`和`j`分別指向`list1`和`list2`的起始位置。循環(huán)進行，只要`list1`和`list2`中都有元素，就比較`list1[i]`和`list2[j]`。較小的元素被添加到`merged`的末尾，對應(yīng)的指針向前移動一位。當(dāng)其中一個列表遍歷完畢后（即`i`達到`len1`或`j`達到`len2`），將另一個列表的剩余部分直接擴展到`merged`的末尾。該方法確保每次比較和插入操作都是常數(shù)時間復(fù)雜度，總的時間復(fù)雜度為O(n+m)，其中n和m分別是`list1`和`list2`的長度。第四題答案```pythondefis_valid_parentheses(s):stack=[]matching={')':'(','}':'{',']':'['}forcharins:ifcharinmatching.values():#遇到左括號，壓入棧stack.append(char)elifcharinmatching.keys():#遇到右括號ifnotstackorstack[-1]!=matching[char]:returnFalse#棧為空或棧頂不匹配stack.pop()#彈出匹配的左括號else:#如果字符不是括號，根據(jù)題目要求忽略或處理錯誤pass#或returnFalsereturnnotstack#棧為空則有效```解析思路：本題考察使用棧來判斷括號匹配。創(chuàng)建一個空棧`stack`。遍歷字符串`s`中的每個字符。如果是左括號（`(`,`{`,`[`），將其壓入棧中。如果是右括號（`)`,`}`,`]`），執(zhí)行判斷：首先檢查棧是否為空，如果為空，說明沒有對應(yīng)的左括號，返回`False`。如果不為空，檢查棧頂元素是否是匹配的左括號（通過`matching`字典查找），如果不是，返回`False`。如果是匹配的左括號，則將棧頂元素彈出。遍歷結(jié)束后，如果棧為空，說明所有括號都正確匹配并出棧，返回`True`；如果棧不為空，說明有未匹配的左括號，返回`False`。第五題答案```pythondeftopological_sort(graph):visited=set()#記錄已訪問節(jié)點temp_marks=set()#記錄當(dāng)前遞歸棧中的節(jié)點result=[]#存儲拓?fù)渑判蚪Y(jié)果defdfs(node):ifnodeintemp_marks:#檢測到環(huán)returnFalseifnodeinvisited:#已訪問過，無需重復(fù)訪問returnTruetemp_marks.add(node)forneighboringraph.get(node,[]):ifnotdfs(neighbor):returnFalsetemp_marks.remove(node)visited.add(node)result.append(node)returnTrue#對每個節(jié)點進行DFSfornodeingraph:ifnodenotinvisited:ifnotdfs(node):returnNone#存在環(huán)，返回Nonereturnresult[::-1]#逆序返回得到正確的拓?fù)渑判騚``解析思路：本題考察基于深度優(yōu)先搜索（DFS）的拓?fù)渑判蛩惴?。拓?fù)渑判蜻m用于有向無環(huán)圖（DAG）。使用三個集合：`visited`記錄已經(jīng)完成DFS訪問并確認(rèn)無環(huán)的節(jié)點；`temp_marks`記錄當(dāng)前正在DFS遞歸棧中的節(jié)點；`result`用于存儲最終的拓?fù)渑判蛐蛄?。定義內(nèi)部函數(shù)`dfs(node)`，對節(jié)點`node`進行DFS。如果`node`正在`temp_marks`中，說明檢測到環(huán)，返回`False`。如果`node`已在`visited`中，說明其子節(jié)點已全部處理完畢，直接返回`True`。將`node`加入`temp_marks`，然后對其所有鄰接節(jié)點（`graph.get(node,[])`）遞歸調(diào)用`dfs`。如果任何遞歸調(diào)用返回`False`，則當(dāng)前路徑存在環(huán)，整個函數(shù)返回`False`。當(dāng)所有鄰接節(jié)點的DFS都成功完成（返回`True`）后，將`node`從`temp_marks`移除，加入`visited`，并將其添加到`result`列表的末尾。最后，遍歷所有節(jié)點，確保每個節(jié)點都被訪問到。由于DFS是后序遍歷，因此最終返回`result[::-1]`以獲得正確的拓?fù)漤樞颉５诹}答案```pythondefcount_substrings(s):n=len(s)ifn==0:return0count=set()foriinrange(n):forjinrange(i,n):count.add(s[i:j+1])#添加從i到j(luò)的子字符串returnlen(count)```解析思路：本題考察子字符串的統(tǒng)計。子字符串是原字符串中連續(xù)的一段字符序列?？梢酝ㄟ^兩層循環(huán)來生成所有可能的子字符串。外層循環(huán)變量`i`從0到`n-1`（`n`為字符串長度），表示子字符串的起始位置。內(nèi)層循環(huán)變量`j`從`i`到`n-1`，表示子字符串的結(jié)束位置。對于每一對`(i,j)`，`s[i:j+1]`提取從索引`i`到`j`（包含`j`）的子字符串。為了確保所有子字符串都是唯一的，使用一個集合`count`來存儲已發(fā)現(xiàn)的子字符串。由于集合自動去重，最終集合的大小`len(count)`即為不同子字符串的個數(shù)。第七題答案```pythondeffind_unsorted_subarray(nums):n=len(nums)ifn<=1:return0,0#從左向右找到第一個不滿足升序的位置start=0whilestart+1<nandnums[start]<=nums[start+1]:start+=1ifstart==n-1:#數(shù)組已經(jīng)完全有序return0,0#從右向左找到第一個不滿足升序的位置end=n-1whileend-1>=0andnums[end-1]<=nums[end]:end-=1#在start到end之間找到最小和最大值min_val=min(nums[start:end+1])max_val=max(nums[start:end+1])#擴展start和end，直到超出邊界且找到更小的數(shù)或更大的數(shù)whilestart>0andnums[start-1]>min_val:start-=1whileend<n-1andnums[end+1]<max_val:end+=1returnstart,end```解析思路：本題考察數(shù)組排序區(qū)間查找。首先，從左到右遍歷數(shù)組，找到第一個違反升序規(guī)則的元素，記為`start`。如果`start`達到`n-1`，說明數(shù)組已經(jīng)是升序的，返回`(0,0)`。然后，從右到左遍歷數(shù)組，找到第一個違反升序規(guī)則的元素，記為`end`。此時，`nums[start:end+1]`是當(dāng)前未排序的區(qū)間。接下來，在`nums[start:end+1]`中找到最小值`min_val`和最大值`max_val`。最后，需要將未排序區(qū)間擴展到包含所有小于`max_val`的元素（可能位于`start`左側(cè)）和所有大于`min_val`的元素（可能位于`end`右側(cè)）。通過向外移動`start`和`end`指針，直到無法再移動為止（即`start`左側(cè)元素不大于`min_val`，`end`右側(cè)元素不小于`max_val`）。最終`start`和`end`指向的就是需要排序的最小區(qū)間。第八題答案```pythondeffour_sum(nums,target):nums.sort()#先排序，便于跳過重復(fù)n=len(nums)result=[]foriinrange(n-3):#跳過重復(fù)元素ifi>0andnums[i]==nums[i-1]:continue#如果當(dāng)前數(shù)字大于目標(biāo)值的一半，后續(xù)不可能找到和為targetifnums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target:break#如果當(dāng)前數(shù)字加上最小的三個數(shù)還小于目標(biāo)值，i需要增大ifnums[i]+nums[n-3]+nums[n-2]+nums[n-1]<target:continue#固定第一個數(shù)字，使用雙指針法找后三個數(shù)forjinrange(i+1,n-2):#跳過重復(fù)元素ifj>i+1andnums[j]==nums[j-1]:continue#如果當(dāng)前兩數(shù)之和大于目標(biāo)值減去前兩數(shù)，j需要減小ifnums[i]+nums[j]+nums[j+1]+nums[j+2]>target:bre