人工智能編程挑戰(zhàn)賽測(cè)試題目及參考答案第一部分：編程基礎(chǔ)（共5題，每題10分，總分50分）題目1（10分）：編寫一個(gè)Python函數(shù)，接收一個(gè)整數(shù)列表作為輸入，返回該列表中所有奇數(shù)的平方和。例如，輸入`[1,2,3,4,5]`，輸出應(yīng)為`12+32+52=35`。題目2（10分）：實(shí)現(xiàn)一個(gè)簡(jiǎn)單的文本編輯器功能，接收兩個(gè)字符串`s1`和`s2`，以及一個(gè)操作類型`op`（`"insert"`或`"delete"`）。若`op`為`"insert"`，將`s2`插入到`s1`的指定位置`index`（從0開始）；若`op`為`"delete"`，刪除`s1`中從`index`開始的`length`個(gè)字符。輸出操作后的字符串。題目3（10分）：給定一個(gè)字符串`s`，判斷其是否為回文串（忽略大小寫和空格）。若為回文串，返回`True`；否則返回`False`。例如，`s="Aman,aplan,acanal:Panama"`應(yīng)返回`True`。題目4（10分）：編寫一個(gè)函數(shù)，接收一個(gè)正整數(shù)`n`，返回一個(gè)列表，其中包含從1到`n`的所有斐波那契數(shù)列中的偶數(shù)（不包括大于`n`的數(shù)）。例如，`n=10`時(shí)，輸出`[2,8]`。題目5（10分）：實(shí)現(xiàn)一個(gè)簡(jiǎn)單的加密函數(shù)，接收一個(gè)字符串`s`和一個(gè)整數(shù)`key`，對(duì)字符串進(jìn)行凱撒密碼加密（字母循環(huán)移位，非字母字符不變）。例如，`s="Hello,World!"`，`key=3`，輸出`"Khoor,Zruog!"`。第二部分：算法與數(shù)據(jù)結(jié)構(gòu)（共5題，每題10分，總分50分）題目6（10分）：給定一個(gè)無(wú)重復(fù)元素的整數(shù)數(shù)組`nums`和一個(gè)目標(biāo)值`target`，編寫函數(shù)返回`target`在數(shù)組中的索引。若不存在，返回`-1`。例如，`nums=[5,7,2,9,4]`，`target=9`，輸出`3`。題目7（10分）：實(shí)現(xiàn)一個(gè)二叉樹的前序遍歷（根-左-右）的迭代版本，不使用遞歸。提供樹的節(jié)點(diǎn)定義：pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=right題目8（10分）：編寫一個(gè)函數(shù)，接收一個(gè)字符串列表`words`，返回其中最長(zhǎng)的“最長(zhǎng)公共前綴”。例如，`words=["flower","flow","flight"]`，輸出`"fl"`。題目9（10分）：實(shí)現(xiàn)一個(gè)LRU（最近最少使用）緩存，支持`get`和`put`操作。使用哈希表和雙向鏈表結(jié)合實(shí)現(xiàn)，要求`get`和`put`均為O(1)時(shí)間復(fù)雜度。題目10（10分）：給定一個(gè)字符串`s`，判斷其是否為有效括號(hào)字符串（只包含`()`、`[]`、`{}`，且括號(hào)正確配對(duì)）。例如，`s="{[()]}"`應(yīng)返回`True`。第三部分：實(shí)際應(yīng)用（共5題，每題10分，總分50分）題目11（10分）：假設(shè)你是一名電商平臺(tái)的開發(fā)者，需要實(shí)現(xiàn)一個(gè)推薦系統(tǒng)。給定用戶購(gòu)買歷史`history`（列表形式，如`["apple","banana","apple","orange"]`），返回用戶可能感興趣的商品列表（出現(xiàn)頻率最高的3個(gè)商品）。若多個(gè)商品頻率相同，按字母順序排列。題目12（10分）：編寫一個(gè)函數(shù)，接收一個(gè)字符串`s`，統(tǒng)計(jì)其中每個(gè)字母（區(qū)分大小寫）和數(shù)字的出現(xiàn)次數(shù)，返回一個(gè)字典。例如，`s="a1B2c3"`，輸出`{"a":1,"1":1,"B":1,"2":1,"c":1,"3":1}`。題目13（10分）：實(shí)現(xiàn)一個(gè)簡(jiǎn)單的文本分類器，給定文本`text`和分類標(biāo)簽`labels`（列表形式），返回每個(gè)標(biāo)簽的文檔頻率（即包含該標(biāo)簽的文檔數(shù)占總文檔數(shù)的比例）。例如，`labels=["spam","ham","spam","ham"]`，輸出`{"spam":0.5,"ham":0.5}`。題目14（10分）：假設(shè)你正在開發(fā)一個(gè)交通信號(hào)燈控制系統(tǒng)，需要根據(jù)車流量動(dòng)態(tài)調(diào)整信號(hào)燈時(shí)長(zhǎng)。編寫一個(gè)函數(shù)，接收當(dāng)前時(shí)間`current_time`（字符串，如`"14:30"`）和車流量數(shù)據(jù)`traffic`（字典形式，如`{"green":5,"yellow":2,"red":8}`），返回當(dāng)前信號(hào)燈狀態(tài)（`"green"`、`"yellow"`或`"red"`）。規(guī)則：若當(dāng)前時(shí)間在信號(hào)燈時(shí)長(zhǎng)內(nèi)，返回當(dāng)前狀態(tài)；否則根據(jù)車流量最高的狀態(tài)返回。題目15（10分）：編寫一個(gè)函數(shù)，接收一個(gè)包含多個(gè)子列表的二維列表`matrix`，返回其轉(zhuǎn)置矩陣。例如，`matrix=[[1,2,3],[4,5,6]]`，輸出`[[1,4],[2,5],[3,6]]`。參考答案及解析第一部分：編程基礎(chǔ)題目1（10分）：pythondefsum_of_odds_squared(nums):returnsum(x2forxinnumsifx%2!=0)解析：-列表推導(dǎo)式遍歷`nums`，篩選奇數(shù)`x`，計(jì)算其平方`x2`，最后用`sum`求和。-例如，`[1,2,3,4,5]`→`12+32+52=1+9+25=35`。題目2（10分）：pythondeftext_editor(s1,s2,op,index,length=None):ifop=="insert":returns1[:index]+s2+s1[index:]elifop=="delete":returns1[:index]+s1[index+length:]else:raiseValueError("Invalidoperation")解析：-`"insert"`：將`s2`插入`s1`的`index`位置，即`s1[:index]+s2+s1[index:]`。-`"delete"`：刪除`s1`中從`index`開始的`length`個(gè)字符，即`s1[:index]+s1[index+length:]`。-例如，`s1="Hello"`,`s2="World"`,`op="insert"`,`index=5`→`"HelloWorld"`。題目3（10分）：pythondefis_palindrome(s):s=''.join(c.lower()forcinsifc.isalnum())returns==s[::-1]解析：-去除空格和大小寫，轉(zhuǎn)換為小寫`s.lower()`，過(guò)濾非字母數(shù)字`c.isalnum()`，然后檢查是否為回文`s==s[::-1]`。-例如，`"Aman,aplan,acanal:Panama"`→`amanaplanacanalpanama`→回文。題目4（10分）：pythondefeven_fibonacci(n):a,b=0,1result=[]whileb<=n:ifb%2==0:result.append(b)a,b=b,a+breturnresult解析：-使用斐波那契數(shù)列迭代生成器，檢查偶數(shù)`b%2==0`，加入結(jié)果列表。-例如，`n=10`→`0,1,1,2,3,5,8`→`[2,8]`。題目5（10分）：pythondefcaesar_cipher(s,key):result=[]forcins:ifc.isalpha():offset=65ifc.isupper()else97new_char=chr((ord(c)-offset+key)%26+offset)result.append(new_char)else:result.append(c)return''.join(result)解析：-對(duì)字母字符循環(huán)移位，大寫字母`A-Z`（ASCII65-90），小寫字母`a-z`（ASCII97-122）。-例如，`"Hello,World!"`,`key=3`→`"Khoor,Zruog!"`。第二部分：算法與數(shù)據(jù)結(jié)構(gòu)題目6（10分）：pythondefsearch(nums,target):fori,numinenumerate(nums):ifnum==target:returnireturn-1解析：-遍歷列表`nums`，若找到`target`則返回索引`i`，否則返回`-1`。-例如，`nums=[5,7,2,9,4]`,`target=9`→`3`。題目7（10分）：pythondefpreorder_iterative(root):ifnotroot:return[]stack,result=[root],[]whilestack:node=stack.pop()result.append(node.val)ifnode.right:stack.append(node.right)ifnode.left:stack.append(node.left)returnresult解析：-使用棧模擬遞歸，先訪問(wèn)根節(jié)點(diǎn)，再右子樹后左子樹入棧。-例如，`root=[1,2,3]`→`[1,2,3]`。題目8（10分）：pythondeflongest_common_prefix(words):ifnotwords:return""prefix=words[0]forwordinwords[1:]:whilenotword.startswith(prefix):prefix=prefix[:-1]ifnotprefix:return""returnprefix解析：-初始前綴為第一個(gè)單詞，逐個(gè)單詞比較，縮短前綴直到匹配或?yàn)榭铡?例如，`["flower","flow","flight"]`→`"fl"`。題目9（10分）：pythonclassLRUCache:def__init__(self,capacity):self.capacity=capacityself.cache={}self.order=[]defget(self,key):ifkeyinself.cache:self.order.remove(key)self.order.append(key)returnself.cache[key]return-1defput(self,key,value):ifkeyinself.cache:self.order.remove(key)eliflen(self.cache)>=self.capacity:oldest=self.order.pop(0)delself.cache[oldest]self.cache[key]=valueself.order.append(key)解析：-使用哈希表`cache`存儲(chǔ)鍵值對(duì)，雙向列表`order`記錄訪問(wèn)順序。-`get`時(shí)移動(dòng)到末尾，`put`時(shí)先刪除最久未使用項(xiàng)（若超出容量）。題目10（10分）：pythondefvalid_parentheses(s):stack=[]mapping={')':'(','}':'{',']':'['}forcins:ifcinmapping.values():stack.append(c)elifcinmapping:ifnotstackorstack.pop()!=mapping[c]:returnFalseelse:returnFalsereturnnotstack解析：-使用棧匹配括號(hào)，左括號(hào)入棧，右括號(hào)與棧頂比較。若棧為空或匹配失敗返回`False`。-例如，`"{[()]}"`→`True`。第三部分：實(shí)際應(yīng)用題目11（10分）：pythonfromcollectionsimportCounterdeftop_n_items(history,n=3):counter=Counter(history)returncounter.most_common(n)解析：-使用`Counter`統(tǒng)計(jì)商品頻率，`most_common(n)`返回頻率最高的`n`個(gè)商品。-例如，`["apple","banana","apple","orange"]`→`[('apple',2),('banana',1),('orange',1)]`。題目12（10分）：pythondefcount_chars(s):return{c:s.count(c)forcinset(s)}解析：-使用字典推導(dǎo)式，對(duì)字符串中每個(gè)唯一字符`c`統(tǒng)計(jì)出現(xiàn)次數(shù)`s.count(c)`。-例如，`"a1B2c3"`→`{'a':1,'1':1,'B':1,'2':1,'c':1,'3':1}`。題目13（10分）：pythondefdoc_frequency(labels):total=len(labels)freq={}forlabelinset(labels):freq[label]=labels.count(label)/totalreturnfreq解析：-統(tǒng)計(jì)每個(gè)標(biāo)簽的出現(xiàn)次數(shù)，除以總文檔數(shù)`total`得到文檔頻率。-例如，`["spam","ham","spam","ham"]`→`{'spam':0.5,'ham':0.5}`。題目14（10分）：pythondeftraffic_l