2025年華為od筆試題+答案算法題1：任務(wù)調(diào)度的最大收益某項(xiàng)目組有n個(gè)待處理任務(wù)，每個(gè)任務(wù)i的開(kāi)始時(shí)間為s_i（分鐘級(jí)時(shí)間戳），結(jié)束時(shí)間為e_i（s_i<e_i），完成后可獲得收益p_i。同一時(shí)間只能執(zhí)行一個(gè)任務(wù)（任務(wù)執(zhí)行期間不能中斷或重疊）。要求選擇若干不重疊的任務(wù)，使得總收益最大。輸入格式：第一行整數(shù)n（1≤n≤100），隨后n行每行三個(gè)整數(shù)s_i,e_i,p_i（0≤s_i<e_i≤1e4，1≤p_i≤1e3）。輸出格式：一個(gè)整數(shù)，表示最大總收益。答案：思路分析：這是典型的區(qū)間調(diào)度問(wèn)題，可用動(dòng)態(tài)規(guī)劃解決。關(guān)鍵在于按結(jié)束時(shí)間排序，便于快速找到前一個(gè)不重疊的任務(wù)。具體步驟：1.將任務(wù)按結(jié)束時(shí)間e_i升序排序。2.定義dp[i]為前i個(gè)任務(wù)的最大收益。對(duì)于第i個(gè)任務(wù)，有兩種選擇：-不選第i個(gè)任務(wù)，dp[i]=dp[i-1]。-選第i個(gè)任務(wù)，需找到最后一個(gè)結(jié)束時(shí)間≤s_i的任務(wù)j（可用二分查找），則dp[i]=dp[j]+p_i。3.最終dp[n]即為最大收益。代碼實(shí)現(xiàn)（Python）：```pythonimportbisectn=int(input())tasks=[]for_inrange(n):s,e,p=map(int,input().split())tasks.append((e,s,p))按結(jié)束時(shí)間排序，存儲(chǔ)為(e,s,p)tasks.sort()按e升序排序end_times=[task[0]fortaskintasks]提取結(jié)束時(shí)間用于二分dp=[0](n+1)foriinrange(1,n+1):e_i,s_i,p_i=tasks[i-1]二分查找最大的j，使得end_times[j]<=s_ij=bisect.bisect_right(end_times,s_i)-1dp[i]=max(dp[i-1],dp[j+1]+p_i)j+1對(duì)應(yīng)前j個(gè)任務(wù)的dp索引print(dp[n])```復(fù)雜度分析：排序時(shí)間O(nlogn)，動(dòng)態(tài)規(guī)劃遍歷O(n)，每次二分查找O(logn)，總時(shí)間復(fù)雜度O(nlogn)，空間復(fù)雜度O(n)。算法題2：二維網(wǎng)格中的最短路徑（帶加速道具）給定一個(gè)m×n的網(wǎng)格，每個(gè)格子為0（空地）、1（障礙物）、2（加速道具）。起點(diǎn)為(0,0)，終點(diǎn)為(m-1,n-1)。移動(dòng)規(guī)則：-每次可向上下左右移動(dòng)一格，耗時(shí)1分鐘。-若當(dāng)前在加速道具格（值為2），可選擇拾取道具（僅能持有1個(gè)），之后下一步移動(dòng)可跨越兩格（如從(x,y)直接到(x+2,y)，耗時(shí)仍為1分鐘），但跨越時(shí)中間格子不能是障礙物。-道具使用后消失，拾取新道具可替換當(dāng)前持有狀態(tài)。求從起點(diǎn)到終點(diǎn)的最短時(shí)間（無(wú)法到達(dá)返回-1）。輸入格式：第一行m,n（2≤m,n≤100），隨后m行每行n個(gè)整數(shù)表示網(wǎng)格。答案：思路分析：需用BFS處理狀態(tài)，狀態(tài)包括坐標(biāo)(x,y)、是否持有加速道具（0或1）。隊(duì)列中存儲(chǔ)(時(shí)間,x,y,has_prop)。訪(fǎng)問(wèn)數(shù)組需記錄每個(gè)位置在是否持有道具時(shí)的最短時(shí)間，避免重復(fù)處理。關(guān)鍵步驟：1.初始化隊(duì)列，起點(diǎn)(0,0)初始未持有道具，時(shí)間0。2.對(duì)于每個(gè)狀態(tài)，嘗試普通移動(dòng)（上下左右一格）和可能的加速移動(dòng)（若持有道具）。3.加速移動(dòng)時(shí)，檢查跨越的兩格是否合法（不越界、中間無(wú)障礙物）。4.到達(dá)終點(diǎn)時(shí)返回當(dāng)前時(shí)間。代碼實(shí)現(xiàn)（Python）：```pythonfromcollectionsimportdequem,n=map(int,input().split())grid=[list(map(int,input().split()))for_inrange(m)]方向數(shù)組：上下左右dirs=[(-1,0),(1,0),(0,-1),(0,1)]訪(fǎng)問(wèn)數(shù)組：visited[x][y][0/1]表示在(x,y)位置是否持有道具的最短時(shí)間visited=[[[float('inf')]2for_inrange(n)]for__inrange(m)]visited[0][0][0]=0q=deque()q.append((0,0,0,0))(時(shí)間,x,y,has_prop)found=Falseres=-1whileq:time,x,y,prop=q.popleft()ifx==m-1andy==n-1:res=timefound=Truebreak普通移動(dòng)：上下左右一格fordx,dyindirs:nx,ny=x+dx,y+dyif0<=nx<mand0<=ny<nandgrid[nx][ny]!=1:new_prop=prop若當(dāng)前格子是道具且未持有，拾取后new_prop=1ifgrid[x][y]==2andprop==0:new_prop=1iftime+1<visited[nx][ny][new_prop]:visited[nx][ny][new_prop]=time+1q.append((time+1,nx,ny,new_prop))加速移動(dòng)：若持有道具，嘗試跨越兩格ifprop:fordx,dyindirs:nx,ny=x+2dx,y+2dymid_x,mid_y=x+dx,y+dy中間格子if0<=nx<mand0<=ny<nand0<=mid_x<mand0<=mid_y<n:ifgrid[mid_x][mid_y]!=1andgrid[nx][ny]!=1:new_time=time+1new_prop=0使用后道具消失ifnew_time<visited[nx][ny][new_prop]:visited[nx][ny][new_prop]=new_timeq.append((new_time,nx,ny,new_prop))print(resiffoundelse-1)```復(fù)雜度分析：每個(gè)格子有2種狀態(tài)（是否持有道具），總狀態(tài)數(shù)O(mn×2)。每個(gè)狀態(tài)最多處理4（普通移動(dòng)）+4（加速移動(dòng)）=8次，總時(shí)間復(fù)雜度O(mn)，空間復(fù)雜度O(mn)。編程題1：字符串壓縮與解壓實(shí)現(xiàn)一個(gè)字符串壓縮和解壓函數(shù)：-壓縮規(guī)則：將連續(xù)重復(fù)的字符壓縮為"字符+次數(shù)"，如"aaabcc"→"a3b1c2"（單個(gè)字符次數(shù)為1時(shí)必須顯式寫(xiě)出）。-解壓規(guī)則：將壓縮字符串還原，如"a3b1c2"→"aaabcc"。-需處理次數(shù)超過(guò)9的情況（如"a12"表示12個(gè)a），并驗(yàn)證壓縮字符串的合法性（非法情況包括：非字母開(kāi)頭、字母后無(wú)數(shù)字、數(shù)字以0開(kāi)頭（如"a01"）、次數(shù)為0（如"a0"））。輸入格式：第一行選操作類(lèi)型（1壓縮/2解壓），第二行輸入字符串。輸出格式：壓縮或解壓后的字符串，若解壓時(shí)輸入非法則輸出"invalid"。答案：思路分析：壓縮：遍歷字符串，統(tǒng)計(jì)連續(xù)字符的次數(shù)，拼接"字符+次數(shù)"。解壓：遍歷壓縮字符串，提取字符和后續(xù)數(shù)字，驗(yàn)證合法性后提供重復(fù)字符。代碼實(shí)現(xiàn)（Python）：```pythondefcompress(s):ifnots:return""res=[]current_char=s[0]count=1forcins[1:]:ifc==current_char:count+=1else:res.append(f"{current_char}{count}")current_char=ccount=1res.append(f"{current_char}{count}")return''.join(res)defdecompress(s):ifnots:return""res=[]i=0n=len(s)whilei<n:檢查字符是否合法（字母）ifnots[i].isalpha():return"invalid"char=s[i]i+=1提取數(shù)字部分num_str=""whilei<nands[i].isdigit():num_str+=s[i]i+=1ifnotnum_str:無(wú)數(shù)字return"invalid"ifnum_str[0]=='0'andlen(num_str)>1:前導(dǎo)零return"invalid"num=int(num_str)ifnum==0:次數(shù)為0return"invalid"res.append(charnum)return''.join(res)主程序op=int(input())s=input().strip()ifop==1:print(compress(s))elifop==2:print(decompress(s))```測(cè)試用例：-輸入1和"aaabcc"，輸出"a3b1c2"。-輸入2和"a3b1c2"，輸出"aaabcc"。-輸入2和"a01"，輸出"invalid"（前導(dǎo)零）。編程題2：數(shù)組中的眾數(shù)分組給定整數(shù)數(shù)組nums，將出現(xiàn)次數(shù)相同的元素分為同一組，要求：-按出現(xiàn)次數(shù)從大到小排序組。-次數(shù)相同的組內(nèi)元素按升序排列。-結(jié)果中每組元素順序按升序排列。輸入格式：第一行整數(shù)n（1≤n≤1e4），第二行n個(gè)整數(shù)nums[i]（-1e9≤nums[i]≤1e9）。輸出格式：一個(gè)二維數(shù)組，如[[3],[2],[1]]。答案：思路分析：1.統(tǒng)計(jì)每個(gè)元素的出現(xiàn)次數(shù)（用字典）。2.按次數(shù)分組（次數(shù)為鍵，元素列表為值）。3.對(duì)次數(shù)降序排序，每組內(nèi)元素升序排序。代碼實(shí)現(xiàn)（Python）：```pythonn=int(input())nums=list(map(int,input().split()))fromcollectionsimportdefaultdict統(tǒng)計(jì)次數(shù)count=defaultdict(int)fornuminnums:count[num]+=1按次數(shù)分組group=defaultdict(list)fornum,cntincount.items():group[cnt].append(num)處理每組排序sorted_groups=[]次數(shù)從大到小排序forcntinsorted(group.keys(),reverse=True):組內(nèi)元素升序排列sorted_nums=sorted(group[cnt])sorted_groups.append(sorted_nums)print(sorted_groups)```測(cè)試用例：輸入：6312233→輸出：[[3],[2],[1]]（3出現(xiàn)3次，2出現(xiàn)2次，1出現(xiàn)1次）。輸入：533221→輸出：[[2,3],[1]]（3和2各出現(xiàn)2次，組內(nèi)升序排列為[2,3]）。綜合題：日志分析系統(tǒng)設(shè)計(jì)某公司需設(shè)計(jì)一個(gè)日志分析系統(tǒng)，處理海量服務(wù)器日志（日均10億條），每條日志格式為：時(shí)間戳（秒級(jí)，如1717986918）、用戶(hù)ID（字符串）、操作類(lèi)型（"login"登錄、"logout"退出、"pay"支付）、操作結(jié)果（僅支付操作有，"success"/"fail"，其他操作為空）。需實(shí)現(xiàn)以下統(tǒng)計(jì)：1.每個(gè)用戶(hù)當(dāng)天的在線(xiàn)時(shí)長(zhǎng)（登錄到退出的時(shí)間差之和，多次登錄取最后一次登錄和最早退出？不，需按時(shí)間順序配對(duì)：每次login后最近的logout為一次會(huì)話(huà)）。2.全局支付操作的成功率（支付成功次數(shù)/總支付次數(shù)）。3.高并發(fā)時(shí)間段：找出當(dāng)天中連續(xù)10分鐘（600秒）內(nèi)請(qǐng)求數(shù)超過(guò)閾值T（如1e5）的所有時(shí)間段（起始和結(jié)束時(shí)間戳）。答案：設(shè)計(jì)思路與實(shí)現(xiàn)步驟：1.數(shù)據(jù)預(yù)處理：-按天劃分日志（時(shí)間戳轉(zhuǎn)日期，過(guò)濾非當(dāng)日日志）。-對(duì)每個(gè)用戶(hù)的日志按時(shí)間戳排序（處理登錄退出配對(duì)）。2.在線(xiàn)時(shí)長(zhǎng)統(tǒng)計(jì)：-為每個(gè)用戶(hù)維護(hù)一個(gè)棧：遇到login壓入時(shí)間戳；遇到logout時(shí)，若棧非空則彈出最近的login時(shí)間，計(jì)算時(shí)長(zhǎng)（logout_time-login_time）并累加。未匹配的login不計(jì)入（用戶(hù)未退出）。3.支付成功率統(tǒng)計(jì)：-遍歷所有支付操作日志，統(tǒng)計(jì)成功次數(shù)（結(jié)果為"success"）和總次數(shù)，最后計(jì)算成功率=成功次數(shù)/總次數(shù)。4.高并發(fā)時(shí)間段檢測(cè)：-使用滑動(dòng)窗口（雙指針）：按時(shí)間戳排序所有日志，窗口左邊界l，右邊界r，維護(hù)窗口內(nèi)的請(qǐng)求數(shù)。-當(dāng)窗口內(nèi)時(shí)間差≤600秒時(shí)，移動(dòng)r并增加計(jì)數(shù)；若超過(guò)600秒，移動(dòng)l并減少計(jì)數(shù)。-當(dāng)計(jì)數(shù)超過(guò)閾值T時(shí)，記錄當(dāng)前窗口的起始（l時(shí)間戳）和結(jié)束（r時(shí)間戳）。關(guān)鍵優(yōu)化點(diǎn)：-海量數(shù)據(jù)處理：使用分布式計(jì)算框架（如Spark）分批次處理，按用戶(hù)ID或時(shí)間分區(qū)。-時(shí)間戳排序：日志按時(shí)間戳預(yù)排序，減少滑動(dòng)窗口的時(shí)間復(fù)雜度（O(n)）。-內(nèi)存優(yōu)化：統(tǒng)計(jì)用戶(hù)在線(xiàn)時(shí)長(zhǎng)時(shí)，使用哈希表存儲(chǔ)用戶(hù)會(huì)話(huà)棧，避免全量日志駐留內(nèi)存。示例實(shí)現(xiàn)偽代碼（關(guān)鍵部分）：```python在線(xiàn)時(shí)長(zhǎng)統(tǒng)計(jì)（單用戶(hù)處理）defcalculate_online_time(logs):logs.sort(key=lambdax:x['timestamp'])按時(shí)間排序