2025年php算法面试题及答案

2025年php算法面试题及答案1.环形数组的最大子数组和给定一个长度为n的环形整数数组nums（即数组首尾相连），求其所有可能的连续子数组的最大和。环形数组意味着子数组可以跨越数组末尾和开头（例如，nums=[5,-3,5]的环形子数组可以是[5,5]）。解题思路：环形数组的最大子数组和存在两种情况：子数组不跨越环的末尾，此时问题等价于普通数组的最大子数组和（可通过Kadane算法求解）。子数组跨越环的末尾，此时子数组由数组前缀和后缀组成，其和等于数组总和减去数组中间最小子数组和（因为总和最小子数组和=前缀和+后缀和）。需要注意特殊情况：若所有元素均为负数，最大子数组和应为数组中的最大元素（此时无法通过跨越环得到更大和）。PHP实现：```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];//计算普通最大子数组和（Kadane算法）$maxCurrent=max($nums[$i],$maxCurrent+$nums[$i]);$maxGlobal=max($maxGlobal,$maxCurrent);//计算最小子数组和（用于环形情况）$minCurrent=min($nums[$i],$minCurrent+$nums[$i]);$minGlobal=min($minGlobal,$minCurrent);}//处理全负数情况：若总和等于最小子数组和（即所有数都是负数），返回最大单个元素if($total==$minGlobal){return$maxGlobal;}//环形情况的最大和为总和减去最小子数组和，与普通情况取较大值returnmax($maxGlobal,$total$minGlobal);}```2.字符串变形问题给定一个由字母、数字和标点组成的字符串s，要求按以下规则变形：单词内部字符顺序反转（单词由连续字母组成，标点和数字视为非单词字符，不参与反转）。非单词字符的位置保持不变（例如，s="Hello!world2025"，变形后应为"olleH!dlrow2025"）。解题思路：遍历字符串，标记每个字符是否为字母（确定单词边界）。按顺序收集单词的起始和结束位置，对每个单词的字符进行反转。非单词字符直接保留原位置。PHP实现：```phpfunctiontransformString($s){$n=strlen($s);$isLetter=array_fill(0,$n,false);//标记字母位置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){//单词结束，反转[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.二叉树的垂直遍历给定一个二叉树的根节点，返回其垂直遍历结果（按列分组，列号从左到右递增；同一列中的节点按从上到下的层序排列；若同一列同一层有多个节点，按数值升序排列）。例如，输入：```3/\920/\157```输出应为：[[9],[3,15],[20],[7]]（列号-1:9；列号0:3、15；列号1:20；列号2:7）。解题思路：使用广度优先搜索（BFS）遍历树，记录每个节点的列号和层号。用哈希表存储列号到节点列表的映射，列表中每个元素包含节点值、层号。对哈希表的列号排序，同一列的节点按层号升序排列，层号相同则按值升序排列。PHP实现（假设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]];//[节点,列号,层号]$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.任务调度器的最小间隔时间给定一个字符数组tasks表示需要执行的任务（每个字符代表一种任务，相同任务需间隔至少n个单位时间），返回完成所有任务的最短时间。例如，tasks=["A","A","A","B","B","B"],n=2，最短时间为8（顺序：A,B,_,A,B,_,A,B）。解题思路：统计每个任务的出现次数，找到最大次数maxCount（如示例中maxCount=3）。计算“冷却块”数量：(maxCount1)(n+1)（每个冷却块包含n个间隔和1个任务）。剩余任务数：总任务数maxCount。若剩余任务数超过冷却块的空闲位置（(maxCount1)n），则总时间为总任务数；否则为冷却块数+剩余任务中与maxCount次数相同的任务数（因为这些任务会在冷却块末尾追加）。PHP实现：```phpfunctionleastInterval($tasks,$n){$count=array_count_values($tasks);$maxCount=max($count);$maxNum=0;//出现maxCount次的任务数量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.数组中的最长山脉子数组给定一个整数数组arr，找到最长的“山脉”子数组长度。山脉定义为：子数组长度≥3，存在i（0<i<len-1）使得arr[0]<arr[1]<...<arr[i]>arr[i+1]>...>arr[len-1]。解题思路：预处理两个数组：left[i]表示以i结尾的递增序列长度，right[i]表示以i开头的递减序列长度。遍历每个可能的山顶i（需满足left[i]≥1且right[i]≥1），计算山脉长度为left[i]+right[i]+1（+1为山顶本身）。PHP实现：```phpfunctionlongestMountain($arr){$n=count($arr);if($n<3)return0;$left=array_fill(0,$n,0);$right=array_fill(0,$n,0);//计算left数组for($i=1;$i<$n;$i++){if($arr[$i]>$arr[$i1]){$left[$i]=$left[$i1]+1;}}//计算right数组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缓存实现设计一个LRU（最近最少使用）缓存，支持put（插入）和get（获取）操作，要求时间复杂度O(1)。解题思路：使用双向链表维护访问顺序（头部为最近访问，尾部为最久未访问）。使用哈希表（关联数组）存储键到链表节点的映射，实现O(1)时间查找。插入时，若键存在则更新值并移动节点到头部；若不存在则创建新节点，若容量已满则删除尾部节点并更新哈希表。获取时，若键存在则移动节点到头部，否则返回-1。PHP实现：```phpclassLRUCache{private$capacity;private$cache=[];//键=>节点private$head;//双向链表头（虚拟节点）private$tail;//双向链表尾（虚拟节点）publicfunction__construct($capacity){$this->capacity=$capacity;//初始化虚拟头尾节点$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