2025年大數(shù)據(jù)初級(jí)筆試算法題解析一、選擇題（共5題，每題2分，總計(jì)10分）題目1問(wèn)題描述：給定一個(gè)無(wú)重復(fù)元素的數(shù)組，請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法，找出數(shù)組中不重復(fù)的三元組，使得這三個(gè)數(shù)的和等于給定的目標(biāo)值。例如，給定數(shù)組`nums=[-1,0,1,2,-1,-4]`和目標(biāo)值`target=0`，不重復(fù)的三元組有`[[-1,-1,2],[-1,0,1]]`。要求：-輸出所有不重復(fù)的三元組-時(shí)間復(fù)雜度盡可能低答案：pythondefthree_sum(nums,target):nums.sort()n=len(nums)result=[]foriinrange(n-2):#去重ifi>0andnums[i]==nums[i-1]:continueleft,right=i+1,n-1whileleft<right:total=nums[i]+nums[left]+nums[right]iftotal==target:result.append([nums[i],nums[left],nums[right]])#去重whileleft<rightandnums[left]==nums[left+1]:left+=1whileleft<rightandnums[right]==nums[right-1]:right-=1left+=1right-=1eliftotal<target:left+=1else:right-=1returnresult題目2問(wèn)題描述：請(qǐng)實(shí)現(xiàn)一個(gè)算法，判斷一個(gè)字符串是否是另一個(gè)字符串的子串。例如，`s1="abc"`，`s2="ahbgdc"`，返回`False`；`s1="a"`，`s2="a"`，返回`True`。要求：-時(shí)間復(fù)雜度盡可能低-可以使用KMP算法或其他高效方法答案：pythondefis_substring(s1,s2):defbuild_next(s):next_arr=[0]*len(s)i,j=1,0whilei<len(s):ifs[i]==s[j]:next_arr[i]=j+1i+=1j+=1elifj>0:j=next_arr[j-1]else:next_arr[i]=0i+=1returnnext_arrifnots1:returnTrueiflen(s1)>len(s2):returnFalsenext_arr=build_next(s2)i,j=0,0whilei<len(s1)andj<len(s2):ifs1[i]==s2[j]:i+=1j+=1elifj>0:j=next_arr[j-1]else:i+=1returni==len(s1)題目3問(wèn)題描述：給定一個(gè)排序數(shù)組，請(qǐng)實(shí)現(xiàn)二分查找算法，找出數(shù)組中目標(biāo)值的索引。如果不存在，返回`-1`。例如，`nums=[1,2,3,4,5,6,7]`，`target=3`，返回`2`。要求：-時(shí)間復(fù)雜度為`O(logn)`答案：pythondefbinary_search(nums,target):left,right=0,len(nums)-1whileleft<=right:mid=left+(right-left)//2ifnums[mid]==target:returnmidelifnums[mid]<target:left=mid+1else:right=mid-1return-1題目4問(wèn)題描述：請(qǐng)實(shí)現(xiàn)一個(gè)算法，找出數(shù)組中重復(fù)次數(shù)超過(guò)`n/2`的元素。例如，`nums=[2,2,1,1,1,2,2]`，返回`2`。要求：-時(shí)間復(fù)雜度為`O(n)`-空間復(fù)雜度為`O(1)`答案：pythondefmajority_element(nums):count=0candidate=Nonefornuminnums:ifcount==0:candidate=numcount+=(1ifnum==candidateelse-1)returncandidate題目5問(wèn)題描述：請(qǐng)實(shí)現(xiàn)一個(gè)算法，將一個(gè)字符串中的所有空格替換為`%20`。例如，`s="Wearehappy."`，返回`"We%20are%20happy."`。要求：-時(shí)間復(fù)雜度為`O(n)`-空間復(fù)雜度為`O(n)`答案：pythondefreplace_spaces(s):returns.replace('','%20')二、填空題（共5題，每題2分，總計(jì)10分）題目6問(wèn)題描述：給定一個(gè)鏈表，請(qǐng)實(shí)現(xiàn)反轉(zhuǎn)鏈表的算法。例如，輸入`1->2->3->4->5`，輸出`5->4->3->2->1`。答案：pythondefreverse_linked_list(head):prev=Nonecurrent=headwhilecurrent:next_node=current.nextcurrent.next=prevprev=currentcurrent=next_nodereturnprev題目7問(wèn)題描述：請(qǐng)實(shí)現(xiàn)一個(gè)算法，找出數(shù)組中第三大的數(shù)。例如，`nums=[1,2,-2147483648,2,3]`，返回`2`。答案：pythondefthird_max(nums):first,second,third=float('-inf'),float('-inf'),float('-inf')fornuminnums:ifnum>first:first,second,third=num,first,secondeliffirst>num>second:second,third=num,secondelifsecond>num>third:third=numreturnthirdifthird!=float('-inf')elsefirst題目8問(wèn)題描述：請(qǐng)實(shí)現(xiàn)一個(gè)算法，判斷一個(gè)整數(shù)是否是回文數(shù)。例如，`x=121`，返回`True`；`x=-121`，返回`False`。答案：pythondefis_palindrome(x):ifx<0or(x%10==0andx!=0):returnFalsereverted_number=0whilex>reverted_number:reverted_number=reverted_number*10+x%10x//=10returnx==reverted_numberorx==reverted_number//10題目9問(wèn)題描述：請(qǐng)實(shí)現(xiàn)一個(gè)算法，找出數(shù)組中所有唯一出現(xiàn)兩次的數(shù)字。例如，`nums=[4,3,2,7,8,2,3,1]`，返回`[2,3]`。答案：pythondeffind_duplicates(nums):seen=set()duplicates=set()fornuminnums:ifnuminseen:duplicates.add(num)else:seen.add(num)returnlist(duplicates)題目10問(wèn)題描述：請(qǐng)實(shí)現(xiàn)一個(gè)算法，找出數(shù)組中所有唯一出現(xiàn)一次的數(shù)字。例如，`nums=[1,2,1,3,2,5]`，返回`[3,5]`。答案：pythondefsingle_numbers(nums):xor=0fornuminnums:xor^=numrightmost_bit=xor&-xora,b=0,0fornuminnums:ifnum&rightmost_bit:a^=numelse:b^=numreturn[a,b]三、簡(jiǎn)答題（共3題，每題5分，總計(jì)15分）題目11問(wèn)題描述：請(qǐng)解釋快速排序算法的原理，并說(shuō)明其時(shí)間復(fù)雜度和空間復(fù)雜度。答案：快速排序是一種分治算法，其原理如下：1.選擇一個(gè)基準(zhǔn)元素（pivot），通常選擇第一個(gè)或最后一個(gè)元素。2.將數(shù)組分成兩部分，左邊的元素都小于基準(zhǔn)，右邊的元素都大于基準(zhǔn)。3.遞歸地對(duì)左右兩部分進(jìn)行快速排序。時(shí)間復(fù)雜度：-最好和平均情況：`O(nlogn)`-最壞情況：`O(n^2)`（當(dāng)基準(zhǔn)選擇不均勻時(shí)）空間復(fù)雜度：-`O(logn)`（遞歸棧的深度）-最壞情況：`O(n)`題目12問(wèn)題描述：請(qǐng)解釋堆排序算法的原理，并說(shuō)明其時(shí)間復(fù)雜度和空間復(fù)雜度。答案：堆排序是一種基于堆數(shù)據(jù)結(jié)構(gòu)的排序算法，其原理如下：1.將數(shù)組構(gòu)建成一個(gè)最大堆（或最小堆）。2.交換堆頂元素與數(shù)組末尾元素，并調(diào)整堆。3.遞歸地對(duì)堆的大小減小的部分進(jìn)行堆調(diào)整。時(shí)間復(fù)雜度：-最好、平均和最壞情況：`O(nlogn)`空間復(fù)雜度：-`O(1)`（原地排序）題目13問(wèn)題描述：請(qǐng)解釋動(dòng)態(tài)規(guī)劃算法的原理，并舉例說(shuō)明其應(yīng)用場(chǎng)景。答案：動(dòng)態(tài)規(guī)劃是一種通過(guò)將問(wèn)題分解為子問(wèn)題并存儲(chǔ)子問(wèn)題的解來(lái)避免重復(fù)計(jì)算的分治算法。其原理如下：1.找到問(wèn)題的最優(yōu)子結(jié)構(gòu)和重疊子問(wèn)題。2.從底向上計(jì)算子問(wèn)題的解，并存儲(chǔ)在數(shù)組中。3.利用子問(wèn)題的解計(jì)算原問(wèn)題的解。應(yīng)用場(chǎng)景：-背包問(wèn)題：給定一組物品，每個(gè)物品有重量和價(jià)值，求在總重量不超過(guò)限制的情況下，能夠裝入背包的物品的最大價(jià)值。-最長(zhǎng)公共子序列：找出兩個(gè)序列的最長(zhǎng)子序列。-斐波那契數(shù)列：計(jì)算第`n`個(gè)斐波那契數(shù)。四、編程題（共2題，每題10分，總計(jì)20分）題目14問(wèn)題描述：請(qǐng)實(shí)現(xiàn)一個(gè)算法，找出字符串中的最長(zhǎng)回文子串。例如，`s="babad"`，返回`"bab"`或`"aba"`。答案：pythondeflongest_palindromic_substring(s):ifnots:return""start,end=0,0foriinrange(len(s)):len1=expand_around_center(s,i,i)len2=expand_around_center(s,i,i+1)max_len=max(len1,len2)ifmax_len>end-start:start=i-(max_len-1)//2end=i+max_len//2returns[start:end+1]defexpand_around_center(s,left,right):whileleft>=0andright<len(s)ands[left]==s[right]:left-=1right+=1returnright-left-1題目15問(wèn)題描述：請(qǐng)實(shí)現(xiàn)一個(gè)算法，找出無(wú)重復(fù)字符的最長(zhǎng)子串的長(zhǎng)度。例如，`s="abcabcbb"`，返回`3`（"abc"）。答案：pythondeflength_of_longest_substring(s):char_map={}left=0max_len=0forrightinrange(len(s)):ifs[right]inchar_map:left=max(left,char_map[s[right]]+1)char_map[s[right]]=rightmax_len=max(max_len,right-left+1)returnmax_len答案答案一、選擇題答案1.pythondefthree_sum(nums,target):nums.sort()n=len(nums)result=[]foriinrange(n-2):#去重ifi>0andnums[i]==nums[i-1]:continueleft,right=i+1,n-1whileleft<right:total=nums[i]+nums[left]+nums[right]iftotal==target:result.append([nums[i],nums[left],nums[right]])#去重whileleft<rightandnums[left]==nums[left+1]:left+=1whileleft<rightandnums[right]==nums[right-1]:right-=1left+=1right-=1eliftotal<target:left+=1else:right-=1returnresult2.pythondefis_substring(s1,s2):defbuild_next(s):next_arr=[0]*len(s)i,j=1,0whilei<len(s):ifs[i]==s[j]:next_arr[i]=j+1i+=1j+=1elifj>0:j=next_arr[j-1]else:next_arr[i]=0i+=1returnnext_arrifnots1:returnTrueiflen(s1)>len(s2):returnFalsenext_arr=build_next(s2)i,j=0,0whilei<len(s1)andj<len(s2):ifs1[i]==s2[j]:i+=1j+=1elifj>0:j=next_arr[j-1]else:i+=1returni==len(s1)3.pythondefbinary_search(nums,target):left,right=0,len(nums)-1whileleft<=right:mid=left+(right-left)//2ifnums[mid]==target:returnmidelifnums[mid]<target:left=mid+1else:right=mid-1return-14.pythondefmajority_element(nums):count=0candidate=Nonefornuminnums:ifcount==0:candidate=numcount+=(1ifnum==candidateelse-1)returncandidate5.pythondefreplace_spaces(s):returns.replace('','%20')二、填空題答案6.pythondefreverse_linked_list(head):prev=Nonecurrent=headwhilecurrent:next_node=current.nextcurrent.next=prevprev=currentcurrent=next_nodereturnprev7.pythondefthird_max(nums):first,second,third=float('-inf'),float('-inf'),float('-inf')fornuminnums:ifnum>first:first,second,third=num,first,secondeliffirst>num>second:second,third=num,secondelifsecond>num>third:third=numreturnthirdifthird!=float('-inf')elsefirst8.pythondefis_palindrome(x):ifx<0or(x%10==0andx!=0):returnFalsereverted_number=0whilex>reverted_number:reverted_number=reverted_number*10+x%10x//=10returnx==reverted_numberorx==reverted_number//109.pythondeffind_duplicates(nums):seen=set()duplicates=set()fornuminnums:ifnuminseen:duplicates.add(num)else:seen.add(num)returnlist(duplicates)10.pythondefsingle_numbers(nums):xor=0fornuminnums:xor^=numrightmost_bit=xor&-xora,b=0,0fornuminnums:ifnum&rightmost_bit:a^=numelse:b^=numreturn[a,b]三、簡(jiǎn)答題答案11.快速排序是一種分治算法，其原理如下：1.選擇一個(gè)基準(zhǔn)元素（pivot），通常選擇第一個(gè)或最后一個(gè)元素。2.將數(shù)組分成兩部分，左邊的元素都小于基準(zhǔn)，右邊的元素都大于基準(zhǔn)。3.遞歸地對(duì)左右兩部分進(jìn)行快速排序。時(shí)間復(fù)雜度：-最好和平均情況：`O(nlogn)`-最壞情況：`O(n^2)`（當(dāng)基準(zhǔn)選擇不均勻時(shí)）空間復(fù)雜度：-`O(logn)`（遞歸棧的深度）-最壞情況：`O(n)`12.堆排序是一種基于堆數(shù)據(jù)結(jié)構(gòu)的排序算法，其原理如下：1.將數(shù)組構(gòu)建成一個(gè)最大堆（或最小堆）。2.交換堆頂元素與數(shù)組末尾元素，并調(diào)整堆。3.遞歸地對(duì)堆的大小減小的部分進(jìn)行堆調(diào)整。時(shí)間復(fù)雜度：-最好、平均和最壞情況：`O(nlogn)`空間復(fù)雜度：-`O(1)`（原地排序）13.動(dòng)態(tài)規(guī)劃是一種通過(guò)將問(wèn)題分解為子問(wèn)題并存儲(chǔ)子問(wèn)題的解來(lái)避免重復(fù)計(jì)算的分治算