計算機程序設計員練習題含答案（附解析）1.數(shù)組旋轉(zhuǎn)題目：給定一個整數(shù)數(shù)組nums和一個整數(shù)k，將數(shù)組中的元素向右旋轉(zhuǎn)k個位置，要求原地修改數(shù)組（即不使用額外空間）。示例：輸入nums=[1,2,3,4,5,6,7]，k=3，輸出[5,6,7,1,2,3,4]。答案：```pythondefrotate(nums,k):n=len(nums)k=k%n處理k超過數(shù)組長度的情況defreverse(arr,start,end):whilestart<end:arr[start],arr[end]=arr[end],arr[start]start+=1end=1reverse(nums,0,n1)反轉(zhuǎn)整個數(shù)組reverse(nums,0,k1)反轉(zhuǎn)前k個元素reverse(nums,k,n1)反轉(zhuǎn)剩余元素```解析：向右旋轉(zhuǎn)k步等價于將數(shù)組分為兩部分：后k個元素和前nk個元素。通過三次反轉(zhuǎn)可以高效實現(xiàn)原地旋轉(zhuǎn)：1.反轉(zhuǎn)整個數(shù)組，使后k個元素移到前面，但順序是逆的；2.反轉(zhuǎn)前k個元素，恢復這部分的正確順序；3.反轉(zhuǎn)剩余nk個元素，恢復這部分的正確順序。k需要先取模n，因為旋轉(zhuǎn)n次相當于不旋轉(zhuǎn)。時間復雜度O(n)，空間復雜度O(1)。2.反轉(zhuǎn)單鏈表題目：定義單鏈表節(jié)點結(jié)構(gòu)（val,next），實現(xiàn)函數(shù)反轉(zhuǎn)一個單鏈表，要求分別用迭代法和遞歸法實現(xiàn)。答案（迭代法）：```pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefreverse_list_iter(head):prev=Nonecurr=headwhilecurr:next_node=curr.next保存下一個節(jié)點curr.next=prev反轉(zhuǎn)指針prev=curr前驅(qū)后移curr=next_node當前節(jié)點后移returnprev最終prev是原鏈表尾，新鏈表頭```答案（遞歸法）：```pythondefreverse_list_recur(head):ifnotheadornothead.next:空或只有一個節(jié)點，直接返回returnheadnew_head=reverse_list_recur(head.next)遞歸反轉(zhuǎn)后續(xù)節(jié)點head.next.next=head原h(huán)ead.next的next指向head（反轉(zhuǎn)）head.next=None原h(huán)ead成為新鏈表的尾節(jié)點returnnew_head新鏈表頭始終是原鏈表尾```解析：迭代法通過三個指針（prev、curr、next_node）逐個反轉(zhuǎn)節(jié)點的next指針，時間復雜度O(n)，空間復雜度O(1)。遞歸法的核心是假設后續(xù)子鏈表已反轉(zhuǎn)，將當前節(jié)點插入到子鏈表尾部。例如，鏈表1→2→3→4，遞歸處理2→3→4得到4→3→2，然后將1插入到2的next（即2.next=1），并將1.next置空。時間復雜度O(n)，空間復雜度O(n)（遞歸棧深度）。3.二叉樹的最近公共祖先（LCA）題目：給定二叉樹的根節(jié)點root和兩個節(jié)點p、q，找出它們的最近公共祖先（即同時是p和q祖先的最深節(jié)點）。答案：```pythonclassTreeNode:def__init__(self,x):self.val=xself.left=Noneself.right=Nonedeflowest_common_ancestor(root,p,q):ifnotrootorroot==porroot==q:returnroot終止條件：當前節(jié)點為空或等于p/q，返回自身left=lowest_common_ancestor(root.left,p,q)right=lowest_common_ancestor(root.right,p,q)ifnotleft:returnright左子樹無結(jié)果，結(jié)果在右子樹ifnotright:returnleft右子樹無結(jié)果，結(jié)果在左子樹returnroot左右子樹都有結(jié)果，當前節(jié)點是LCA```解析：遞歸遍歷二叉樹，對每個節(jié)點判斷：若當前節(jié)點是p或q，直接返回（因為p/q的祖先包括自身）；遞歸左子樹和右子樹，若左右子樹均返回非空節(jié)點，說明p和q分別在左右子樹中，當前節(jié)點是LCA；若只有左子樹返回結(jié)果，說明p/q都在左子樹中，結(jié)果為左子樹的返回值（同理右子樹）。時間復雜度O(n)，空間復雜度O(n)（遞歸棧最壞情況）。4.最長遞增子序列（LIS）題目：給定一個整數(shù)數(shù)組nums，找到其中最長遞增子序列的長度（子序列元素順序必須遞增，但不需要連續(xù)）。答案（動態(tài)規(guī)劃）：```pythondeflength_of_lis_dp(nums):n=len(nums)ifn==0:return0dp=[1]ndp[i]表示以nums[i]結(jié)尾的最長遞增子序列長度max_len=1foriinrange(n):forjinrange(i):ifnums[j]<nums[i]:dp[i]=max(dp[i],dp[j]+1)max_len=max(max_len,dp[i])returnmax_len```答案（貪心+二分優(yōu)化）：```pythondeflength_of_lis_greedy(nums):tails=[]tails[i]表示長度為i+1的遞增子序列的最小末尾元素fornuminnums:left,right=0,len(tails)whileleft<right:二分查找第一個>=num的位置mid=(left+right)//2iftails[mid]<num:left=mid+1else:right=midifleft==len(tails):tails.append(num)所有元素都小于num，擴展長度else:tails[left]=num替換為更小的末尾元素，優(yōu)化后續(xù)可能的增長returnlen(tails)```解析：動態(tài)規(guī)劃解法中，dp[i]的值依賴于所有j<i且nums[j]<nums[i]的dp[j]，時間復雜度O(n2)，空間復雜度O(n)。貪心+二分法通過維護tails數(shù)組，盡可能讓每個長度的子序列末尾元素最小（這樣后續(xù)更容易擴展）。例如，nums=[3,6,2,5]，tails變化為：[3]→[3,6]→[2,6]→[2,5]，最終長度為2。時間復雜度O(nlogn)，空間復雜度O(n)。5.Dijkstra算法求單源最短路徑題目：給定一個無向圖（用鄰接表表示）和源點src，計算源點到所有其他節(jié)點的最短路徑長度。答案：```pythonimportheapqdefdijkstra(graph,src):n=len(graph)dist=[float('inf')]n距離數(shù)組，初始為無窮大dist[src]=0heap=[]heapq.heappush(heap,(0,src))優(yōu)先隊列存儲（距離，節(jié)點）visited=[False]nwhileheap:current_dist,u=heapq.heappop(heap)ifvisited[u]:continue已處理過，跳過visited[u]=Trueforv,weightingraph[u]:遍歷u的所有鄰接節(jié)點ifdist[v]>dist[u]+weight:dist[v]=dist[u]+weightheapq.heappush(heap,(dist[v],v))新距離入堆returndist```解析：Dijkstra算法適用于帶非負權(quán)邊的圖。核心步驟：1.初始化距離數(shù)組dist，源點距離為0，其他為無窮大；2.使用優(yōu)先隊列（最小堆）選擇當前距離最小的節(jié)點u；3.遍歷u的鄰接節(jié)點v，若通過u到v的路徑更短（dist[u]+weight<dist[v]），則更新dist[v]，并將新距離入堆；4.標記u為已訪問，避免重復處理。時間復雜度O(m+nlogn)（m為邊數(shù)，堆操作O(logn)），空間復雜度O(n)。6.多線程順序打印ABC題目：三個線程分別打印A、B、C，要求按順序打印ABC，循環(huán)n次（如n=3時輸出ABCABCABC）。答案（Python，使用Condition）：```pythonimportthreadingclassPrinter:def__init__(self,n):self.n=nself.current=00:A,1:B,2:Cself.cond=threading.Condition()defprint_a(self):withself.cond:for_inrange(self.n):whileself.current!=0:self.cond.wait()print('A',end='')self.current=1self.cond.notify_all()defprint_b(self):withself.cond:for_inrange(self.n):whileself.current!=1:self.cond.wait()print('B',end='')self.current=2self.cond.notify_all()defprint_c(self):withself.cond:for_inrange(self.n):whileself.current!=2:self.cond.wait()print('C',end='')self.current=0self.cond.notify_all()測試n=3printer=Printer(n)t1=threading.Thread(target=printer.print_a)t2=threading.Thread(target=printer.print_b)t3=threading.Thread(target=printer.print_c)t1.start()t2.start()t3.start()t1.join()t2.join()t3.join()```解析：使用Condition（條件變量）實現(xiàn)線程同步。共享變量current表示當前應打印的線程（0→A，1→B，2→C）。每個線程循環(huán)n次，每次檢查current是否等于自己的標識，若否，則調(diào)用wait()釋放鎖并阻塞；若是，打印字符后更新current并調(diào)用notify_all()喚醒其他線程。通過這種方式確保順序執(zhí)行。7.Python提供器實現(xiàn)斐波那契數(shù)列題目：用Python提供器實現(xiàn)斐波那契數(shù)列，按需提供前m項。答案：```pythondeffibonacci(m):a,b=0,1count=0whilecount<m:yielda提供當前值a,b=b,a+bcount+=1測試：提供前10項fib=fibonacci(10)print(list(fib))輸出[0,1,1,2,3,5,8,13,21,34]```解析：提供器使用yield語句暫停執(zhí)行并返回當前值，下次迭代時從暫停處繼續(xù)。斐波那契數(shù)列的前兩項為0和1，后續(xù)每項是前兩項之和。提供器的優(yōu)勢在于惰性計算（僅在需要時提供下一項），節(jié)省內(nèi)存，尤其適用于提供大量數(shù)據(jù)的場景。8.KMP算法實現(xiàn)字符串匹配題目：實現(xiàn)KMP算法，找到模式串pattern在文本串text中的首次出現(xiàn)位置（若不存在返回1）。答案：```pythondefkmp_search(text,pattern):n,m=len(text),len(pattern)ifm==0:return0構(gòu)建部分匹配表（前綴函數(shù)）lps=[0]mlps[i]表示pattern[0..i]的最長相等前綴后綴長度length=0最長前綴后綴的長度i=1whilei<m:ifpattern[i]==pattern[length]:length+=1lps[i]=lengthi+=1else:iflength!=0:length=lps[length1]回退到前一個位置else:lps[i]=0i+=1匹配過程i=j=0i:text的指針，j:pattern的指針whilei<n:iftext[i]==pattern[j]:i+=1j+=1ifj==m:returnij匹配成功，返回起始位置else:ifj!=0:j=lps[j1]根據(jù)lps回退jelse:i+=1return1未找到```解析：KMP算法通過預處理模式串提供部分匹配表（LPS），避免暴力匹配中的重復比較。LPS數(shù)組記錄每個位置的最長相等前綴后綴長度，用于在不匹配時回退模式串指針j。例如，模式串"ABABC"的LPS數(shù)組為[0,0,1,2,0]。匹配時，若text[i]≠pattern[j]，j回退到LPS[j1]，直到j=0或匹配成功。時間復雜度O(n+m)，空間復雜度O(m)。9.設計LRU緩存題目：設計一個LRU（最近最少使用）緩存，支持get和put操作，要求時間復雜度O(1)。答案：```pythonclassNode:def__init__(self,key=0,val=0):self.key=keyself.val=valself.prev=Noneself.next=NoneclassLRUCache:def__init__(self,capacity):self.cap=capacityself.cache={}哈希表：key→Node雙向鏈表（偽頭尾節(jié)點簡化操作）self.head=Node()self.tail=Node()self.head.next=self.tailself.tail.prev=self.headdef_add_to_head(self,node):將節(jié)點插入頭部（最近訪問）node.prev=self.headnode.next=self.head.nextself.head.next.prev=nodeself.head.next=nodedef_remove_node(self,node):移除任意節(jié)點node.prev.next=node.nextnode.next.prev=node.prevdefget(self,key):ifkeynotinself.