2025年華為OD機(jī)試真題題庫(kù)及答案一、基礎(chǔ)算法題（共5題）1.最短路徑統(tǒng)計(jì)（簡(jiǎn)單）題目描述：給定一個(gè)無(wú)向圖，節(jié)點(diǎn)編號(hào)為1~N，邊權(quán)均為1。起點(diǎn)為S，終點(diǎn)為T(mén)。要求計(jì)算從S到T的最短路徑數(shù)量（路徑長(zhǎng)度為最短距離的路徑總數(shù)）。

輸入示例：

第一行輸入N（節(jié)點(diǎn)數(shù)，2≤N≤100）、M（邊數(shù)，1≤M≤200）、S、T；

后續(xù)M行每行輸入兩個(gè)整數(shù)u、v，表示u和v之間有一條無(wú)向邊。

輸出示例：

輸出一個(gè)整數(shù)，表示最短路徑數(shù)量。答案代碼（Python）：fromcollectionsimportdeque

defmain():

importsys

input=sys.stdin.read().split()

idx=0

N=int(input[idx]);idx+=1

M=int(input[idx]);idx+=1

S=int(input[idx]);idx+=1

T=int(input[idx]);idx+=1

adj=[[]for_inrange(N+1)]

for_inrange(M):

u=int(input[idx]);idx+=1

v=int(input[idx]);idx+=1

adj[u].append(v)

adj[v].append(u)

dist=[-1]*(N+1)

count=[0]*(N+1)

q=deque()

q.append(S)

dist[S]=0

count[S]=1

whileq:

u=q.popleft()

forvinadj[u]:

ifdist[v]==-1:

dist[v]=dist[u]+1

count[v]=count[u]

q.append(v)

elifdist[v]==dist[u]+1:

count[v]+=count[u]

print(count[T]ifdist[T]!=-1else0)

if__name__=="__main__":

main()解析：

-使用BFS計(jì)算最短路徑，同時(shí)維護(hù)每個(gè)節(jié)點(diǎn)的最短路徑數(shù)。

-dist數(shù)組記錄節(jié)點(diǎn)到S的最短距離，count數(shù)組記錄到達(dá)該節(jié)點(diǎn)的最短路徑數(shù)。

-當(dāng)首次訪問(wèn)節(jié)點(diǎn)v時(shí)（dist[v]==-1），更新距離并繼承前驅(qū)節(jié)點(diǎn)的路徑數(shù)；若再次訪問(wèn)且距離相同（dist[v]==dist[u]+1），則累加路徑數(shù)。

-最終輸出count[T]，若T不可達(dá)則輸出0。2.旋轉(zhuǎn)數(shù)組最小值（簡(jiǎn)單）題目描述：一個(gè)長(zhǎng)度為n的升序數(shù)組，在某個(gè)位置旋轉(zhuǎn)（如[1,2,3,4,5]旋轉(zhuǎn)后可能為[3,4,5,1,2]）。要求找出旋轉(zhuǎn)數(shù)組的最小元素。

輸入示例：[3,4,5,1,2]

輸出示例：1答案代碼（Python）：deffind_min(nums):

left,right=0,len(nums)-1

whileleft<right:

mid=(left+right)//2

ifnums[mid]>nums[right]:

left=mid+1

else:

right=mid

returnnums[left]解析：

-二分查找變種，利用旋轉(zhuǎn)數(shù)組特性：旋轉(zhuǎn)點(diǎn)左側(cè)元素≥右側(cè)元素。

-比較中間值與右邊界值：若中間值>右邊界，說(shuō)明旋轉(zhuǎn)點(diǎn)在右半部分；否則在左半部分（含中間點(diǎn)）。

-最終左指針指向最小值。3.字符串壓縮（中等）題目描述：將字符串按連續(xù)相同字符壓縮為“字符+次數(shù)”形式（次數(shù)為1時(shí)省略）。例如，“aabccc”壓縮為”a2bc3”。若壓縮后長(zhǎng)度不小于原長(zhǎng)度，返回原字符串。

輸入示例：“aabccc”

輸出示例：“a2bc3”答案代碼（Python）：defcompress(s):

ifnots:

return""

res=[]

count=1

prev=s[0]

forcins[1:]:

ifc==prev:

count+=1

else:

res.append(prev+(str(count)ifcount>1else""))

prev=c

count=1

res.append(prev+(str(count)ifcount>1else""))

compressed=''.join(res)

returncompressediflen(compressed)<len(s)elses解析：

-遍歷字符串，統(tǒng)計(jì)連續(xù)字符的出現(xiàn)次數(shù)。

-每次遇到不同字符時(shí)，將當(dāng)前字符和次數(shù)（次數(shù)>1時(shí)）加入結(jié)果。

-最后比較壓縮前后長(zhǎng)度，選擇更短的返回。4.子數(shù)組最大和（中等）題目描述：給定整數(shù)數(shù)組nums（可能含負(fù)數(shù)），找出和最大的連續(xù)子數(shù)組（至少含一個(gè)元素），返回其和。

輸入示例：[-2,1,-3,4,-1,2,1,-5,4]

輸出示例：6（對(duì)應(yīng)子數(shù)組[4,-1,2,1]）答案代碼（Python）：defmax_sub_array(nums):

max_sum=current_sum=nums[0]

fornuminnums[1:]:

current_sum=max(num,current_sum+num)

max_sum=max(max_sum,current_sum)

returnmax_sum解析：

-動(dòng)態(tài)規(guī)劃思想，current_sum表示以當(dāng)前元素結(jié)尾的子數(shù)組最大和。

-若current_sum+num小于num，則重新開(kāi)始計(jì)算子數(shù)組（從當(dāng)前元素開(kāi)始）。

-最終max_sum記錄全局最大值。5.進(jìn)制轉(zhuǎn)換（中等）題目描述：將十進(jìn)制數(shù)N轉(zhuǎn)換為base進(jìn)制（2≤base≤16），結(jié)果用字符串表示（1015用AF表示）。

輸入示例：N=255,base=16

輸出示例：“FF”答案代碼（Python）：defconvert_base(n,base):

ifn==0:

return"0"

chars="0123456789ABCDEF"

res=[]

is_negative=False

ifn<0:

is_negative=True

n=-n

whilen>0:

res.append(chars[n%base])

n=n//base

ifis_negative:

res.append('-')

return''.join(reversed(res))解析：

-處理0和負(fù)數(shù)特殊情況。

-用取模運(yùn)算獲取每一位的數(shù)值，對(duì)應(yīng)到字符表（0-9，A-F）。

-結(jié)果需反轉(zhuǎn)順序，因?yàn)槿∧５玫降氖堑臀坏礁呶?。二、?shù)據(jù)結(jié)構(gòu)應(yīng)用題（共5題）6.反轉(zhuǎn)鏈表（簡(jiǎn)單）題目描述：給定單鏈表頭節(jié)點(diǎn)head，反轉(zhuǎn)鏈表并返回新頭節(jié)點(diǎn)。

輸入示例：1->2->3->4->5->NULL

輸出示例：5->4->3->2->1->NULL答案代碼（Python）：classListNode:

def__init__(self,val=0,next=None):

self.val=val

self.next=next

defreverse_list(head):

prev=None

current=head

whilecurrent:

next_node=current.next

current.next=prev

prev=current

current=next_node

returnprev解析：

-迭代法，用prev保存前一個(gè)節(jié)點(diǎn)，current遍歷當(dāng)前節(jié)點(diǎn)。

-每次將當(dāng)前節(jié)點(diǎn)的next指向prev，完成反轉(zhuǎn)。

-最終prev成為新頭節(jié)點(diǎn)。7.二叉樹(shù)最近公共祖先（中等）題目描述：給定二叉樹(shù)的根節(jié)點(diǎn)root和兩個(gè)節(jié)點(diǎn)p、q，找出它們的最近公共祖先（LCA）。

輸入示例：root=[3,5,1,6,2,0,8,null,null,7,4],p=5,q=1

輸出示例：3（LCA為3）答案代碼（Python）：classTreeNode:

def__init__(self,x):

self.val=x

self.left=None

self.right=None

deflowest_common_ancestor(root,p,q):

ifnotrootorroot==porroot==q:

returnroot

left=lowest_common_ancestor(root.left,p,q)

right=lowest_common_ancestor(root.right,p,q)

ifnotleft:

returnright

ifnotright:

returnleft

returnroot解析：

-遞歸法，若當(dāng)前節(jié)點(diǎn)是p或q，直接返回。

-遞歸查找左右子樹(shù)：若左右子樹(shù)各找到一個(gè)節(jié)點(diǎn)，當(dāng)前節(jié)點(diǎn)是LCA；若僅左/右子樹(shù)找到，返回該結(jié)果。8.課程表（拓?fù)渑判颍械龋╊}目描述：總共有n門(mén)課需選修，編號(hào)0~n-1。有些課程需要先修課（如[1,0]表示修1前需先修0）。判斷是否可能完成所有課程學(xué)習(xí)。

輸入示例：n=2,prerequisites=[[1,0],[0,1]]

輸出示例：False（存在循環(huán)依賴）答案代碼（Python）：defcan_finish(num_courses,prerequisites):

adj=[[]for_inrange(num_courses)]

in_degree=[0]*num_courses

fora,binprerequisites:

adj[b].append(a)

in_degree[a]+=1

queue=[iforiinrange(num_courses)ifin_degree[i]==0]

count=0

whilequeue:

u=queue.pop(0)

count+=1

forvinadj[u]:

in_degree[v]-=1

ifin_degree[v]==0:

queue.append(v)

returncount==num_courses解析：

-拓?fù)渑判驒z測(cè)有向圖是否有環(huán)。

-統(tǒng)計(jì)每個(gè)節(jié)點(diǎn)的入度，入度為0的節(jié)點(diǎn)加入隊(duì)列。

-依次處理隊(duì)列中的節(jié)點(diǎn)，減少其鄰接節(jié)點(diǎn)的入度，若入度變?yōu)?則加入隊(duì)列。

-最終處理節(jié)點(diǎn)數(shù)等于總課程數(shù)則無(wú)環(huán)，否則存在循環(huán)依賴。9.兩數(shù)之和（哈希表，簡(jiǎn)單）題目描述：給定整數(shù)數(shù)組nums和目標(biāo)值target，找出和為target的兩個(gè)數(shù)的下標(biāo)（假設(shè)唯一解）。

輸入示例：nums=[2,7,11,15],target=9

輸出示例：[0,1]答案代碼（Python）：deftwo_sum(nums,target):

hash_map={}

foridx,numinenumerate(nums):

complement=target-num

ifcomplementinhash_map:

return[hash_map[complement],idx]

hash_map[num]=idx

return[]解析：

-使用哈希表存儲(chǔ)已遍歷元素的數(shù)值和下標(biāo)。

-對(duì)于當(dāng)前元素，計(jì)算補(bǔ)數(shù)（target-當(dāng)前數(shù)），若補(bǔ)數(shù)存在于哈希表中，返回對(duì)應(yīng)下標(biāo)。

-時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(n)。10.合并K個(gè)升序鏈表（困難）題目描述：給定K個(gè)升序鏈表的頭節(jié)點(diǎn)數(shù)組lists，合并成一個(gè)升序鏈表。

輸入示例：lists=[[1,4,5],[1,3,4],[2,6]]

輸出示例：[1,1,2,3,4,4,5,6]答案代碼（Python）：importheapq

defmerge_k_lists(lists):

dummy=ListNode(0)

current=dummy

heap=[]

fori,linenumerate(lists):

ifl:

heapq.heappush(heap,(l.val,i,l))

whileheap:

val,idx,node=heapq.heappop(heap)

current.next=node

current=current.next

ifnode.next:

heapq.heappush(heap,(node.next.val,idx,node.next))

returndummy.next解析：

-使用優(yōu)先隊(duì)列（最小堆）優(yōu)化合并過(guò)程。

-初始化時(shí)將所有鏈表的頭節(jié)點(diǎn)加入堆（按值排序）。

-每次取出堆頂元素（最小值節(jié)點(diǎn)），將其下一個(gè)節(jié)點(diǎn)（若存在）加入堆。

-時(shí)間復(fù)雜度O(NlogK)（N為總節(jié)點(diǎn)數(shù)，K為鏈表數(shù)），空間復(fù)雜度O(K)。三、綜合編程題（共5題）11.最長(zhǎng)遞增子序列（動(dòng)態(tài)規(guī)劃+二分，困難）題目描述：給定整數(shù)數(shù)組nums，找到最長(zhǎng)遞增子序列（LIS）的長(zhǎng)度（子序列不要求連續(xù)）。

輸入示例：nums=[10,9,2,5,3,7,101,18]

輸出示例：4（最長(zhǎng)子序列為[2,3,7,101]）答案代碼（Python）：deflength_of_lis(nums):

tails=[]

fornuminnums:

left,right=0,len(tails)

whileleft<right:

mid=(left+right)//2

iftails[mid]<num:

left=mid+1

else:

right=mid

ifleft==len(tails):

tails.append(num)

else:

tails[left]=num

returnlen(tails)解析：

-維護(hù)tails數(shù)組，tails[i]表示長(zhǎng)度為i+1的遞增子序列的最小末尾元素。

-遍歷nums，對(duì)每個(gè)num，用二分查找在tails中找到第一個(gè)≥num的位置，替換為num（保持tails遞增）。

-最終tails長(zhǎng)度即為L(zhǎng)IS長(zhǎng)度，時(shí)間復(fù)雜度O(nlogn)。12.任務(wù)調(diào)度器（貪心，中等）題目描述：任務(wù)列表tasks（如[‘A’,‘A’,‘A’,‘B’,‘B’,‘B’]），冷卻時(shí)間n（相同任務(wù)需間隔n個(gè)單位）。計(jì)算完成所有任務(wù)的最短時(shí)間。

輸入示例：tasks=[‘A’,‘A’,‘A’,‘B’,‘B’,‘B’],n=2

輸出示例：8（順序：A->B->空->A->B->空->A->B）答案代碼（Python）：defleast_interval(tasks,n):

fromcollectionsimportCounter

count=Counter(tasks)

max_freq=max(count.values())

max_count=sum(1forvincount.values()ifv==max_freq)

part=max_freq-1

part_len=n-(max_count-1)

empty_slots=part*part_len

available_tasks=len(tasks)-max_freq*max_count

idles=max(0,empty_slots-available_tasks)

returnlen(tasks)+idles解析：

-計(jì)算最高頻率任務(wù)的出現(xiàn)次數(shù)max_freq和有多少任務(wù)達(dá)到該頻率max_count。

-空閑槽位數(shù)=（max_freq-1）*(n-(max_count-1))，即每段間隔的空閑數(shù)。

-總時(shí)間=任務(wù)數(shù)+空閑數(shù)（空閑數(shù)可能為0）。13.接雨水（雙指針，困難）題目描述：給定n個(gè)非負(fù)整數(shù)表示高度圖，計(jì)算下雨后能接多少雨水。

輸入示例：height=[0,1,0,2,1,0,1,3,2,1,2,1]

輸出示例：6答案代碼（Python）：deftrap(height):

ifnotheight:

return0

left,right=0,len(height)-1

left_max,right_max=0,0

res=0

whileleft<right:

ifheight[left]<height[right]:

ifheight[left]>=left_max:

left_max=height[left]

else:

res+=left_max-height[left]

left+=1

else:

ifheight[right]>=right_max:

right_max=height[right]

else:

res+=right_max-height[right]

right-=1

returnres解析：

-雙指針?lè)?，維護(hù)左右兩側(cè)的最大高度。

-每次移動(dòng)較矮的一側(cè)指針（因?yàn)樗挥奢^矮側(cè)決定）。

-若當(dāng)前高度小于對(duì)應(yīng)側(cè)的最大高度，累加雨水量（最大高度-當(dāng)前高度）。14.全排列（回溯，中等）題目描述：給定不含重復(fù)數(shù)字的數(shù)組nums，返回所有可能的全排列。

輸入示例：nums=[1,2,3]

輸出示例：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]答案代碼（Python）：defpermute(nums):

res=[]

defbacktrack(path,used):

iflen(path)==len(nums):

res.appe