2025年php算法面試題及答案1.環(huán)形數(shù)組的最大子數(shù)組和給定一個長度為n的環(huán)形整數(shù)數(shù)組nums（即數(shù)組首尾相連），求其所有可能的連續(xù)子數(shù)組的最大和。環(huán)形數(shù)組意味著子數(shù)組可以跨越數(shù)組末尾和開頭（例如，nums=[5,-3,5]的環(huán)形子數(shù)組可以是[5,5]）。解題思路：環(huán)形數(shù)組的最大子數(shù)組和存在兩種情況：子數(shù)組不跨越環(huán)的末尾，此時問題等價于普通數(shù)組的最大子數(shù)組和（可通過Kadane算法求解）。子數(shù)組跨越環(huán)的末尾，此時子數(shù)組由數(shù)組前綴和后綴組成，其和等于數(shù)組總和減去數(shù)組中間最小子數(shù)組和（因?yàn)榭偤妥钚∽訑?shù)組和=前綴和+后綴和）。需要注意特殊情況：若所有元素均為負(fù)數(shù)，最大子數(shù)組和應(yīng)為數(shù)組中的最大元素（此時無法通過跨越環(huán)得到更大和）。PHP實(shí)現(xiàn)：```phpfunctionmaxSubarraySumCircular($nums){$n=count($nums);$maxCurrent=$maxGlobal=$nums[0];$minCurrent=$minGlobal=$nums[0];$total=$nums[0];for($i=1;$i<$n;$i++){$total+=$nums[$i];//計(jì)算普通最大子數(shù)組和（Kadane算法）$maxCurrent=max($nums[$i],$maxCurrent+$nums[$i]);$maxGlobal=max($maxGlobal,$maxCurrent);//計(jì)算最小子數(shù)組和（用于環(huán)形情況）$minCurrent=min($nums[$i],$minCurrent+$nums[$i]);$minGlobal=min($minGlobal,$minCurrent);}//處理全負(fù)數(shù)情況：若總和等于最小子數(shù)組和（即所有數(shù)都是負(fù)數(shù)），返回最大單個元素if($total==$minGlobal){return$maxGlobal;}//環(huán)形情況的最大和為總和減去最小子數(shù)組和，與普通情況取較大值returnmax($maxGlobal,$total$minGlobal);}```2.字符串變形問題給定一個由字母、數(shù)字和標(biāo)點(diǎn)組成的字符串s，要求按以下規(guī)則變形：單詞內(nèi)部字符順序反轉(zhuǎn)（單詞由連續(xù)字母組成，標(biāo)點(diǎn)和數(shù)字視為非單詞字符，不參與反轉(zhuǎn)）。非單詞字符的位置保持不變（例如，s="Hello!world2025"，變形后應(yīng)為"olleH!dlrow2025"）。解題思路：遍歷字符串，標(biāo)記每個字符是否為字母（確定單詞邊界）。按順序收集單詞的起始和結(jié)束位置，對每個單詞的字符進(jìn)行反轉(zhuǎn)。非單詞字符直接保留原位置。PHP實(shí)現(xiàn)：```phpfunctiontransformString($s){$n=strlen($s);$isLetter=array_fill(0,$n,false);//標(biāo)記字母位置for($i=0;$i<$n;$i++){$isLetter[$i]=ctype_alpha($s[$i]);}$result=str_split($s);$start=-1;for($i=0;$i<$n;$i++){if($isLetter[$i]&&$start==-1){$start=$i;//單詞起始位置}elseif(!$isLetter[$i]&&$start!=-1){//單詞結(jié)束，反轉(zhuǎn)[start,i-1]$end=$i1;$word=array_slice($result,$start,$end$start+1);$word=array_reverse($word);array_splice($result,$start,$end$start+1,$word);$start=-1;}}//處理末尾可能未閉合的單詞if($start!=-1){$end=$n1;$word=array_slice($result,$start,$end$start+1);$word=array_reverse($word);array_splice($result,$start,$end$start+1,$word);}returnimplode('',$result);}```3.二叉樹的垂直遍歷給定一個二叉樹的根節(jié)點(diǎn)，返回其垂直遍歷結(jié)果（按列分組，列號從左到右遞增；同一列中的節(jié)點(diǎn)按從上到下的層序排列；若同一列同一層有多個節(jié)點(diǎn)，按數(shù)值升序排列）。例如，輸入：```3/\920/\157```輸出應(yīng)為：[[9],[3,15],[20],[7]]（列號-1:9；列號0:3、15；列號1:20；列號2:7）。解題思路：使用廣度優(yōu)先搜索（BFS）遍歷樹，記錄每個節(jié)點(diǎn)的列號和層號。用哈希表存儲列號到節(jié)點(diǎn)列表的映射，列表中每個元素包含節(jié)點(diǎn)值、層號。對哈希表的列號排序，同一列的節(jié)點(diǎn)按層號升序排列，層號相同則按值升序排列。PHP實(shí)現(xiàn)（假設(shè)TreeNode類定義如下）：```phpclassTreeNode{public$val=0;public$left=null;public$right=null;publicfunction__construct($val=0,$left=null,$right=null){$this->val=$val;$this->left=$left;$this->right=$right;}}functionverticalTraversal($root){if($root===null)return[];$queue=[[$root,0,0]];//[節(jié)點(diǎn),列號,層號]$map=[];//列號=>[[值,層號]]while(!empty($queue)){$nodeInfo=array_shift($queue);$node=$nodeInfo[0];$col=$nodeInfo[1];$row=$nodeInfo[2];if(!isset($map[$col]))$map[$col]=[];$map[$col][]=[$node->val,$row];if($node->left!==null){array_push($queue,[$node->left,$col1,$row+1]);}if($node->right!==null){array_push($queue,[$node->right,$col+1,$row+1]);}}//按列號排序ksort($map);$result=[];foreach($mapas$col=>$nodes){//同一列排序：先按層號升序，再按值升序usort($nodes,function($a,$b){if($a[1]!=$b[1]){return$a[1]$b[1];}else{return$a[0]$b[0];}});$result[]=array_column($nodes,0);}return$result;}```4.任務(wù)調(diào)度器的最小間隔時間給定一個字符數(shù)組tasks表示需要執(zhí)行的任務(wù)（每個字符代表一種任務(wù)，相同任務(wù)需間隔至少n個單位時間），返回完成所有任務(wù)的最短時間。例如，tasks=["A","A","A","B","B","B"],n=2，最短時間為8（順序：A,B,_,A,B,_,A,B）。解題思路：統(tǒng)計(jì)每個任務(wù)的出現(xiàn)次數(shù)，找到最大次數(shù)maxCount（如示例中maxCount=3）。計(jì)算“冷卻塊”數(shù)量：(maxCount1)(n+1)（每個冷卻塊包含n個間隔和1個任務(wù)）。剩余任務(wù)數(shù)：總?cè)蝿?wù)數(shù)maxCount。若剩余任務(wù)數(shù)超過冷卻塊的空閑位置（(maxCount1)n），則總時間為總?cè)蝿?wù)數(shù)；否則為冷卻塊數(shù)+剩余任務(wù)中與maxCount次數(shù)相同的任務(wù)數(shù)（因?yàn)檫@些任務(wù)會在冷卻塊末尾追加）。PHP實(shí)現(xiàn)：```phpfunctionleastInterval($tasks,$n){$count=array_count_values($tasks);$maxCount=max($count);$maxNum=0;//出現(xiàn)maxCount次的任務(wù)數(shù)量foreach($countas$v){if($v==$maxCount)$maxNum++;}$partCount=$maxCount1;$partLength=$n+1;$emptySlots=$partCount($partLength$maxNum);//冷卻塊中的空閑位置$availableTasks=count($tasks)$maxCount$maxNum;$idles=max(0,$emptySlots$availableTasks);returncount($tasks)+$idles;}```5.數(shù)組中的最長山脈子數(shù)組給定一個整數(shù)數(shù)組arr，找到最長的“山脈”子數(shù)組長度。山脈定義為：子數(shù)組長度≥3，存在i（0<i<len-1）使得arr[0]<arr[1]<...<arr[i]>arr[i+1]>...>arr[len-1]。解題思路：預(yù)處理兩個數(shù)組：left[i]表示以i結(jié)尾的遞增序列長度，right[i]表示以i開頭的遞減序列長度。遍歷每個可能的山頂i（需滿足left[i]≥1且right[i]≥1），計(jì)算山脈長度為left[i]+right[i]+1（+1為山頂本身）。PHP實(shí)現(xiàn)：```phpfunctionlongestMountain($arr){$n=count($arr);if($n<3)return0;$left=array_fill(0,$n,0);$right=array_fill(0,$n,0);//計(jì)算left數(shù)組for($i=1;$i<$n;$i++){if($arr[$i]>$arr[$i1]){$left[$i]=$left[$i1]+1;}}//計(jì)算right數(shù)組for($i=$n2;$i>=0;$i--){if($arr[$i]>$arr[$i+1]){$right[$i]=$right[$i+1]+1;}}$maxLen=0;for($i=0;$i<$n;$i++){if($left[$i]>0&&$right[$i]>0){$current=$left[$i]+$right[$i]+1;if($current>$maxLen){$maxLen=$current;}}}return$maxLen>=3?$maxLen:0;}```6.基于PHP的LRU緩存實(shí)現(xiàn)設(shè)計(jì)一個LRU（最近最少使用）緩存，支持put（插入）和get（獲?。┎僮?，要求時間復(fù)雜度O(1)。解題思路：使用雙向鏈表維護(hù)訪問順序（頭部為最近訪問，尾部為最久未訪問）。使用哈希表（關(guān)聯(lián)數(shù)組）存儲鍵到鏈表節(jié)點(diǎn)的映射，實(shí)現(xiàn)O(1)時間查找。插入時，若鍵存在則更新值并移動節(jié)點(diǎn)到頭部；若不存在則創(chuàng)建新節(jié)點(diǎn)，若容量已滿則刪除尾部節(jié)點(diǎn)并更新哈希表。獲取時，若鍵存在則移動節(jié)點(diǎn)到頭部，否則返回-1。PHP實(shí)現(xiàn)：```phpclassLRUCache{private$capacity;private$cache=[];//鍵=>節(jié)點(diǎn)private$head;//雙向鏈表頭（虛擬節(jié)點(diǎn)）private$tail;//雙向鏈表尾（虛擬節(jié)點(diǎn)）publicfunction__construct($capacity){$this->capacity=$capacity;//初始化虛擬頭尾節(jié)點(diǎn)$this->head=newNode(0,0);$this->tail=newNode(0,0);$this->head->next=$this->tail;$this->tail->prev=$this->head;}publicfunctionget($key){if(!isset($this->cache[$key]))return-1;$node=$this->cache[$key];$this->moveToHead($node);//訪問后移到頭部return$node->value;}publicfunctionput($key,$value){if(isset($this->cache[$key])){$node=$this->cache[$key];$node->value=$value;$this->moveToHead($node);}else{$node=newNode($key,$value);$this->cache[$key]=$node;$this->addToHead($node);if(count($this->cache)>$this->capacity){$removed=$this->removeTail();unset($this->cache[$removed->key]);}}}privatefunction