2025年考研計(jì)算機(jī)考研編程難題解析（含答案）考試時(shí)間：______分鐘總分：______分姓名：______一、編寫(xiě)一個(gè)函數(shù)`mergeIntervals(intervals[]Interval)`，合并所有重疊的區(qū)間。其中，`Interval`是一個(gè)結(jié)構(gòu)體，定義如下：```gotypeIntervalstruct{StartintEndint}```輸入一個(gè)區(qū)間列表`intervals`，其中的區(qū)間按照`Start`屬性升序排列。合并后的區(qū)間列表也應(yīng)該按照`Start`屬性升序排列，且不包含任何重疊的區(qū)間。請(qǐng)給出該函數(shù)的Go語(yǔ)言實(shí)現(xiàn)。在實(shí)現(xiàn)中，你需要清晰地描述你的算法思路，并說(shuō)明你的時(shí)間復(fù)雜度和空間復(fù)雜度。二、給定一個(gè)由`'a'`到`'z'`小寫(xiě)字母組成的字符串`s`，以及一個(gè)整數(shù)`k`。你需要找到`s`中長(zhǎng)度為`k`的子串，使得子串中`'a'`到`'z'`的字母各不相同的最多個(gè)數(shù)。請(qǐng)你返回這個(gè)最多的個(gè)數(shù)。例如，`s="abcabcbb"`,`k=3`?？赡艿淖哟?abc","bca","cab","abc","bcb","cbb"。其中"abc"和"cab"包含3個(gè)不同的字母，是最大的。返回`3`。請(qǐng)?jiān)O(shè)計(jì)一個(gè)高效算法解決這個(gè)問(wèn)題，并分析你的算法的時(shí)間復(fù)雜度。三、設(shè)計(jì)一個(gè)數(shù)據(jù)結(jié)構(gòu)`LRUCache`，用來(lái)模擬最近最少使用（LRU）緩存。緩存可以存儲(chǔ)最多`capacity`個(gè)鍵值對(duì)。實(shí)現(xiàn)`LRUCache`類(lèi)：*`LRUCache(intcapacity)`以正整數(shù)`capacity`初始化緩存。*`intget(intkey)`返回緩存中鍵`key`對(duì)應(yīng)的值（如果不存在，則返回`-1`）。*`voidput(intkey,intvalue)`如果鍵`key`已存在，則更新其值；如果鍵不存在，則添加該鍵值對(duì)。當(dāng)緩存容量達(dá)到上限時(shí)，應(yīng)該驅(qū)逐最久未使用（LRU）的緩存項(xiàng)。請(qǐng)給出該數(shù)據(jù)結(jié)構(gòu)的Python實(shí)現(xiàn)。你可以選擇使用哈希表和雙向鏈表相結(jié)合的方式來(lái)設(shè)計(jì)，并簡(jiǎn)要說(shuō)明你的設(shè)計(jì)思路。四、假設(shè)你要設(shè)計(jì)一個(gè)簡(jiǎn)單的文件系統(tǒng)，其中每個(gè)文件或目錄都可以表示為樹(shù)結(jié)構(gòu)，根節(jié)點(diǎn)為`'/'`。文件和目錄的名字由小寫(xiě)字母組成，且名字唯一。目錄下可以包含文件或其他目錄。你需要支持以下兩種操作：1.`cdpath`：更改當(dāng)前工作目錄。`path`是一個(gè)絕對(duì)路徑或相對(duì)路徑。如果是絕對(duì)路徑，它以`'/'`開(kāi)頭；如果是相對(duì)路徑，它以`'.'`或`'..'`開(kāi)頭。`'.'`表示當(dāng)前目錄，`'..'`表示上一級(jí)目錄。路徑中可能包含多個(gè)目錄名，由`'/'`分隔。如果`path`無(wú)效（例如，試圖訪問(wèn)一個(gè)不存在的目錄），則保持當(dāng)前目錄不變。2.`ls`：列出當(dāng)前工作目錄下的所有文件和目錄名，按照名稱(chēng)升序排列。請(qǐng)給出這兩種操作的Python實(shí)現(xiàn)。你可以設(shè)計(jì)合適的數(shù)據(jù)結(jié)構(gòu)來(lái)表示文件系統(tǒng)，并實(shí)現(xiàn)上述功能。五、編寫(xiě)一個(gè)函數(shù)`topKFrequent(nums[]int,kint)[]int`，返回`nums`數(shù)組中出現(xiàn)頻率最高的`k`個(gè)元素。你可以假設(shè)`nums`中的元素都是整數(shù)，且`k`始終有效，即`1<=k<=nums.length`。請(qǐng)給出該函數(shù)的Python實(shí)現(xiàn)。在實(shí)現(xiàn)中，你可以考慮使用哈希表來(lái)統(tǒng)計(jì)頻率，并使用合適的數(shù)據(jù)結(jié)構(gòu)（如堆）來(lái)找到頻率最高的`k`個(gè)元素。請(qǐng)分析你的算法的時(shí)間復(fù)雜度和空間復(fù)雜度。六、考慮一個(gè)有向無(wú)環(huán)圖（DAG），其中節(jié)點(diǎn)代表任務(wù)，有向邊代表任務(wù)之間的依賴(lài)關(guān)系（即箭頭指向的任務(wù)必須在箭頭源任務(wù)完成后才能執(zhí)行）。給定一個(gè)DAG和每個(gè)任務(wù)的執(zhí)行時(shí)間，你需要計(jì)算完成所有任務(wù)所需的最短時(shí)間。請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法來(lái)解決這個(gè)問(wèn)題。你需要明確你的輸入和輸出。假設(shè)輸入以鄰接列表的形式給出，其中每個(gè)節(jié)點(diǎn)的出邊信息已知。請(qǐng)給出算法的主要步驟，并分析其時(shí)間復(fù)雜度。試卷答案一、```gofuncmergeIntervals(intervals[]Interval)[]Interval{iflen(intervals)==0{returnnil}//首先按起點(diǎn)排序sort.Slice(intervals,func(i,jint)bool{returnintervals[i].Start<intervals[j].Start})merged:=make([]Interval,0)//初始化第一個(gè)區(qū)間current:=intervals[0]merged=append(merged,current)fori:=1;i<len(intervals);i++{//如果當(dāng)前區(qū)間的終點(diǎn)大于等于下一個(gè)區(qū)間的起點(diǎn)，發(fā)生重疊ifcurrent.End>=intervals[i].Start{//合并區(qū)間，更新當(dāng)前區(qū)間的終點(diǎn)為兩者終點(diǎn)最大值current.End=max(current.End,intervals[i].End)}else{//不重疊，將當(dāng)前區(qū)間加入結(jié)果，更新current為下一個(gè)區(qū)間current=intervals[i]merged=append(merged,current)}}returnmerged}funcmax(a,bint)int{ifa>b{returna}returnb}```解析思路：首先對(duì)區(qū)間列表按起點(diǎn)進(jìn)行排序。然后初始化一個(gè)空的結(jié)果列表`merged`。遍歷排序后的區(qū)間列表，使用一個(gè)`current`變量來(lái)跟蹤當(dāng)前正在合并的區(qū)間。對(duì)于每個(gè)新區(qū)間，如果它與`current`區(qū)間重疊（即`current.End>=intervals[i].Start`），則更新`current`的終點(diǎn)為兩者終點(diǎn)中的較大值。如果不重疊，則將`current`區(qū)間加入`merged`，并將新區(qū)間設(shè)為新的`current`。最后返回`merged`。時(shí)間復(fù)雜度O(nlogn)來(lái)自排序，空間復(fù)雜度O(n)用于存儲(chǔ)結(jié)果。二、```pythondefmaxUniqueLetters(s:str,k:int)->int:max_count=0left=0char_count={}forrightinrange(len(s)):#更新當(dāng)前右邊界字符的計(jì)數(shù)char_count[s[right]]=char_count.get(s[right],0)+1#如果窗口大小大于k，移動(dòng)左邊界whileright-left+1>k:char_count[s[left]]-=1ifchar_count[s[left]]==0:delchar_count[s[left]]left+=1#窗口大小為k時(shí)，計(jì)算不同字符的數(shù)量ifright-left+1==k:max_count=max(max_count,len(char_count))returnmax_count```解析思路：使用滑動(dòng)窗口技術(shù)。初始化左指針`left`為0，右指針`right`從0開(kāi)始遍歷字符串`s`。使用一個(gè)字典`char_count`來(lái)記錄當(dāng)前窗口中字符的頻率。對(duì)于每個(gè)`right`，將`s[right]`的頻率加一。如果窗口大?。╜right-left+1`）大于`k`，則移動(dòng)左指針`left`，并相應(yīng)減少`char_count`中`s[left]`的頻率，如果頻率為0則刪除該鍵值對(duì)。當(dāng)窗口大小等于`k`時(shí)，計(jì)算`char_count`的長(zhǎng)度（即不同字符的數(shù)量），并更新`max_count`。遍歷結(jié)束后返回`max_count`。時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)（因?yàn)樽帜钢坏?z'，字典大小有限）。三、```pythonclassNode:def__init__(self,key=None,value=None):self.key=keyself.value=valueself.prev=Noneself.next=NoneclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}#創(chuàng)建偽頭部和偽尾部self.head=Node()self.tail=Node()self.head.next=self.tailself.tail.prev=self.headdef_add_node(self,node):#將節(jié)點(diǎn)添加到頭部后面node.prev=self.headnode.next=self.head.nextself.head.next.prev=nodeself.head.next=nodedef_remove_node(self,node):#移除節(jié)點(diǎn)prev_node=node.prevnext_node=node.nextprev_node.next=next_nodenext_node.prev=prev_nodedef_move_to_head(self,node):#將節(jié)點(diǎn)移動(dòng)到頭部self._remove_node(node)self._add_node(node)def_pop_tail(self):#彈出尾部節(jié)點(diǎn)res=self.tail.prevself._remove_node(res)returnresdefget(self,key:int)->int:node=self.cache.get(key,None)ifnotnode:return-1#使用節(jié)點(diǎn)self._move_to_head(node)returnnode.valuedefput(self,key:int,value:int)->None:node=self.cache.get(key)ifnotnode:#創(chuàng)建新節(jié)點(diǎn)new_node=Node(key,value)self.cache[key]=new_nodeself._add_node(new_node)#如果超出容量，刪除尾部節(jié)點(diǎn)iflen(self.cache)>self.capacity:tail=self._pop_tail()delself.cache[tail.key]else:#更新節(jié)點(diǎn)node.value=valueself._move_to_head(node)```解析思路：使用哈希表`cache`存儲(chǔ)鍵到節(jié)點(diǎn)的映射，以便O(1)時(shí)間復(fù)雜度訪問(wèn)。使用雙向鏈表（DoublyLinkedList）維護(hù)節(jié)點(diǎn)的使用順序，最近使用的節(jié)點(diǎn)靠近頭部。鏈表包含一個(gè)偽頭部`head`和一個(gè)偽尾部`tail`，它們不存儲(chǔ)實(shí)際數(shù)據(jù)。`_add_node`將節(jié)點(diǎn)插入鏈表頭部，`_remove_node`從鏈表中移除節(jié)點(diǎn)，`_move_to_head`將節(jié)點(diǎn)移動(dòng)到鏈表頭部，`_pop_tail`移除鏈表尾部節(jié)點(diǎn)（即最久未使用節(jié)點(diǎn)）。`get`操作先從哈希表查找節(jié)點(diǎn)，如果找到則將其移動(dòng)到頭部并返回值，否則返回`-1`。`put`操作先嘗試從哈希表獲取節(jié)點(diǎn)，如果不存在則創(chuàng)建新節(jié)點(diǎn)并插入鏈表頭部，同時(shí)加入哈希表；如果節(jié)點(diǎn)存在，則更新值并將其移動(dòng)到頭部。如果插入后緩存大小超過(guò)`capacity`，則移除尾部節(jié)點(diǎn)并從哈希表中刪除對(duì)應(yīng)的鍵。時(shí)間復(fù)雜度均為O(1)。四、```pythonclassFileSystem:def__init__(self):self.current_path=['']#使用列表表示路徑，根目錄是空字符串defcd(self,path:str)->None:ifpath=='/':self.current_path=['']returnparts=path.split('/')i=0forpartinparts:ifpart=='.':continueelifpart=='..':i=max(0,i-1)else:i+=1self.current_path=self.current_path[:i]+[part]defls(self)->List[str]:#返回當(dāng)前路徑下的所有文件和目錄名，按字母序#這里簡(jiǎn)化為返回當(dāng)前路徑列表的排序版本returnsorted(self.current_path)```解析思路：使用一個(gè)列表`current_path`來(lái)表示當(dāng)前工作目錄的路徑，其中每個(gè)元素是一個(gè)目錄名，根目錄用一個(gè)空字符串表示。`cd`操作根據(jù)輸入的`path`更新`current_path`。如果`path`是`'/'`，則重置為根目錄。如果`path`是相對(duì)路徑，則遍歷`path`的每個(gè)部分：`'.'`忽略，`'..'`表示回到上一級(jí)（`i`減一，但不小于0），其他部分表示進(jìn)入下一級(jí)（`i`加一）。`ls`操作返回當(dāng)前路徑下的所有文件和目錄名，這里簡(jiǎn)化為返回`current_path`列表的排序版本。實(shí)際應(yīng)用中，`ls`可能需要從文件系統(tǒng)中獲取實(shí)際文件和目錄列表并排序。時(shí)間復(fù)雜度主要在排序上，為O(nlogn)，其中n是`current_path`的長(zhǎng)度。五、```pythonfromcollectionsimportCounteri