2025年USACOSilver級模擬試卷（中等算法與問題解決）——深度解析中等難度算法題目一、算法設計與分析要求：設計并實現一個函數，該函數接受一個整數數組作為輸入，并返回數組中所有偶數的和。1.實現一個函數`sum_of_evens`，它接受一個整數數組`nums`作為參數。2.遍歷數組`nums`，對于每個元素，如果它是偶數，則將其添加到變量`sum`中。3.函數返回變量`sum`的值。二、動態規劃要求：實現一個函數，該函數接受一個整數數組作為輸入，并返回數組中所有連續子數組的最大子數組和。1.實現一個函數`max_subarray_sum`，它接受一個整數數組`nums`作為參數。2.初始化兩個變量`max_sum`和`current_sum`，將`max_sum`設置為`nums[0]`，`current_sum`也設置為`nums[0]`。3.遍歷數組`nums`從第二個元素開始，對于每個元素，計算`current_sum`為當前元素與`current_sum`的最大值。4.更新`max_sum`為`current_sum`與`max_sum`的最大值。5.函數返回`max_sum`。三、數據結構要求：實現一個棧，并實現以下方法：push、pop、isEmpty、peek。1.實現一個類`Stack`。2.在`Stack`類中實現以下方法：-`push(item)`：接受一個元素`item`作為參數，并將其添加到棧頂。-`pop()`：移除并返回棧頂元素。-`isEmpty()`：如果棧為空，返回`True`，否則返回`False`。-`peek()`：返回棧頂元素，但不移除它。3.測試`Stack`類的方法，確保它們按照預期工作。四、圖論要求：實現一個函數，該函數接受一個無向圖和兩個頂點作為輸入，并返回這兩個頂點之間最短路徑的長度。1.實現一個函數`shortest_path_length`，它接受一個字典`graph`作為參數，其中鍵是頂點，值是連接該頂點的相鄰頂點的列表。2.實現Dijkstra算法來找到兩個頂點之間的最短路徑。3.返回最短路徑的長度。五、字符串處理要求：實現一個函數，該函數接受一個字符串作為輸入，并返回該字符串中所有重復字符的最小重復次數。1.實現一個函數`min_repeated_char_count`，它接受一個字符串`str`作為參數。2.使用一個字典來跟蹤每個字符的出現次數。3.遍歷字符串，更新字典中字符的計數。4.遍歷字典，找到重復次數最多的字符，并返回它的重復次數。六、數論要求：實現一個函數，該函數接受兩個整數作為輸入，并返回它們之間所有質數的和。1.實現一個函數`sum_of_primes`，它接受兩個整數`a`和`b`作為參數。2.實現一個輔助函數`is_prime`，用于檢查一個整數是否是質數。3.在`sum_of_primes`函數中，遍歷從`a`到`b`之間的所有整數。4.對于每個整數，使用`is_prime`函數檢查它是否是質數。5.如果是質數，將其添加到變量`sum`中。6.函數返回變量`sum`的值。本次試卷答案如下：一、算法設計與分析1.實現一個函數`sum_of_evens`，它接受一個整數數組`nums`作為參數。```pythondefsum_of_evens(nums):sum=0fornuminnums:ifnum%2==0:sum+=numreturnsum```解析思路：遍歷數組中的每個元素，檢查是否為偶數（即元素除以2的余數為0），如果是，則將該元素加到總和變量`sum`中。二、動態規劃1.實現一個函數`max_subarray_sum`，它接受一個整數數組`nums`作為參數。```pythondefmax_subarray_sum(nums):max_sum=nums[0]current_sum=nums[0]fornuminnums[1:]:current_sum=max(num,current_sum+num)max_sum=max(max_sum,current_sum)returnmax_sum```解析思路：使用動態規劃的思想，維護兩個變量`max_sum`和`current_sum`。`max_sum`記錄到目前為止遇到的最大子數組和，而`current_sum`記錄以當前元素結尾的最大子數組和。對于每個元素，更新`current_sum`為當前元素和`current_sum+num`中的最大值，同時更新`max_sum`為`max_sum`和`current_sum`中的最大值。三、數據結構1.實現一個類`Stack`。```pythonclassStack:def__init__(self):self.items=[]defpush(self,item):self.items.append(item)defpop(self):ifnotself.isEmpty():returnself.items.pop()defisEmpty(self):returnlen(self.items)==0defpeek(self):ifnotself.isEmpty():returnself.items[-1]```解析思路：`Stack`類使用列表`items`作為內部存儲。`push`方法將元素添加到列表的末尾，`pop`方法從列表的末尾移除并返回元素，`isEmpty`方法檢查列表是否為空，`peek`方法返回列表的最后一個元素但不移除它。四、圖論1.實現一個函數`shortest_path_length`，它接受一個字典`graph`作為參數，其中鍵是頂點，值是連接該頂點的相鄰頂點的列表。```pythonimportheapqdefshortest_path_length(graph,start,end):visited=set()queue=[(0,start)]whilequeue:distance,current=heapq.heappop(queue)ifcurrent==end:returndistanceifcurrentnotinvisited:visited.add(current)forneighboringraph[current]:ifneighbornotinvisited:heapq.heappush(queue,(distance+1,neighbor))returnfloat('inf')```解析思路：使用優先隊列（最小堆）實現Dijkstra算法。初始化一個隊列，其中包含起始頂點的距離為0。在隊列不為空的情況下，從隊列中彈出具有最小距離的頂點。如果當前頂點是目標頂點，則返回其距離。如果當前頂點尚未訪問，則將其相鄰頂點的距離加1并加入隊列。五、字符串處理1.實現一個函數`min_repeated_char_count`，它接受一個字符串`str`作為參數。```pythondefmin_repeated_char_count(str):char_count={}forcharinstr:char_count[char]=char_count.get(char,0)+1max_count=max(char_count.values())returnmax_countifmax_count>1else0```解析思路：遍歷字符串，使用字典`char_count`跟蹤每個字符的出現次數。找到最大計數`max_count`，如果它大于1，則返回它，否則返回0。六、數論1.實現一個函數`sum_of_primes`，該函數接受兩個整數`a`和`b`作為參數。```pythondefis_prime(num):ifnum<=1:returnFalseforiinrange(2,int(num**0.5)+1):ifnum%i==0:returnFalsereturnTruedefsum_of_primes(a,b):sum=0fornuminrange(a