2026年计算机编程岗位面试编程题及答案详解

2026年计算机编程岗位面试编程题及答案详解一、算法设计题（共3题，每题20分）1.（20分）字符串匹配问题题目：给定两个字符串`text`和`pattern`，`text`的长度为`m`，`pattern`的长度为`n`。请实现一个函数`strStr(text,pattern)`，找到`pattern`在`text`中首次出现的位置（从0开始计数）。如果`pattern`不在`text`中，返回`-1`。要求：-可以使用KMP算法或暴力匹配算法实现。-请说明你的算法思路，并给出代码实现。示例：plaintext输入：text="helloworld",pattern="world"输出：62.（20分）最长有效括号题目：给定一个由`'('`和`')'`组成的字符串`s`，请计算其中最长的有效括号子串的长度。有效括号子串是指可以由完全匹配的括号组成的子串。要求：-可以使用动态规划或栈实现。-请说明你的算法思路，并给出代码实现。示例：plaintext输入：s="(()"输出：23.（20分）合并区间题目：给定一个区间的集合`intervals`，其中每个区间表示为`[start,end]`。请合并所有重叠的区间，并返回一个不重叠的区间集合。要求：-可以使用贪心算法实现。-请说明你的算法思路，并给出代码实现。示例：plaintext输入：intervals=[[1,3],[2,6],[8,10],[15,18]]输出：[[1,6],[8,10],[15,18]]二、数据结构题（共3题，每题20分）4.（20分）二叉树的最大深度题目：给定一个二叉树，请计算其最大深度（即根节点到最远叶子节点的最长路径上的节点数）。要求：-可以使用递归或迭代（BFS）实现。-请说明你的算法思路，并给出代码实现。示例：plaintext输入：root=[3,9,20,null,null,15,7]输出：35.（20分）LRU缓存机制题目：设计一个LRU（最近最少使用）缓存机制，支持以下操作：-`LRUCache(intcapacity)`：初始化缓存容量为`capacity`。-`get(intkey)`：如果键存在，返回其值；否则返回`-1`。-`put(intkey,intvalue)`：如果键存在，更新其值；如果键不存在，添加键值对。当缓存容量已满时，删除最近最少使用的键。要求：-可以使用哈希表+双向链表实现。-请说明你的数据结构和算法思路，并给出代码实现。6.（20分）二叉树的层序遍历题目：给定一个二叉树，请返回其层序遍历的结果（从上到下，每一层从左到右）。要求：-可以使用BFS实现。-请说明你的算法思路，并给出代码实现。示例：plaintext输入：root=[3,9,20,null,null,15,7]输出：[[3],[9,20],[15,7]]三、编程实现题（共3题，每题20分）7.（20分）快速排序的非递归实现题目：请实现快速排序的非递归版本。给定一个数组`nums`，使用循环代替递归，完成快速排序。要求：-可以使用栈来模拟递归过程。-请说明你的算法思路，并给出代码实现。示例：plaintext输入：nums=[4,5,6,7,3,2,1]输出：[1,2,3,4,5,6,7]8.（20分）二叉搜索树的最近公共祖先题目：给定一个二叉搜索树（BST）和两个节点`p`和`q`，请找到它们的最近公共祖先（LCA）。假设`p`和`q`均存在于BST中，且`p`不等于`q`。要求：-可以利用BST的性质实现。-请说明你的算法思路，并给出代码实现。示例：plaintext输入：root=[6,2,8,0,4,7,9,null,null,3,5],p=2,q=8输出：69.（20分）滑动窗口的最大值题目：给定一个数组`nums`和一个整数`k`，请找到所有长度为`k`的子数组的最大值。要求：-可以使用单调队列实现。-请说明你的算法思路，并给出代码实现。示例：plaintext输入：nums=[1,3,-1,-3,5,3,6,7],k=3输出：[3,3,5,5,6,7]答案及解析一、算法设计题1.字符串匹配问题（KMP算法）答案：pythondefstrStr(text:str,pattern:str)->int:ifnotpattern:return0n,m=len(text),len(pattern)lps=[0]m#最长公共前后缀数组构建lps数组j=0foriinrange(1,m):whilej>0andpattern[i]!=pattern[j]:j=lps[j-1]ifpattern[i]==pattern[j]:j+=1lps[i]=jKMP匹配i=0#text的指针j=0#pattern的指针whilei<n:iftext[i]==pattern[j]:i+=1j+=1ifj==m:returni-j#匹配成功elifi<nandtext[i]!=pattern[j]:ifj>0:j=lps[j-1]else:i+=1return-1解析：KMP算法的核心是通过构建`lps`数组（最长公共前后缀），避免重复比较。具体步骤如下：1.构建lps数组：-`lps[i]`表示`pattern[0..i]`中，最长相等的前后缀的长度。-使用双指针`i`和`j`，`j`表示当前匹配的位置，`i`遍历`pattern`。-当`pattern[i]==pattern[j]`时，`j++`，记录`lps[i]=j`。-否则，当`j>0`时，将`j`移动到`lps[j-1]`的位置，继续比较。-如果`j==0`，则`lps[i]=0`。2.KMP匹配：-使用两个指针`i`（`text`）和`j`（`pattern`），逐个字符比较。-当`text[i]==pattern[j]`时，`i++`和`j++`。-当`j==m`时，匹配成功，返回`i-j`。-当`text[i]!=pattern[j]`时，如果`j>0`，将`j`移动到`lps[j-1]`，继续比较；否则`i++`。-如果遍历完`text`仍未匹配，返回`-1`。时间复杂度：O(m+n)，其中`m`是`pattern`的长度，`n`是`text`的长度。2.最长有效括号（动态规划）答案：pythondeflongestValidParentheses(s:str)->int:n=len(s)dp=[0]nmax_len=0foriinrange(1,n):ifs[i]==')':ifs[i-1]=='(':dp[i]=(dp[i-2]ifi>=2else0)+2elifi-dp[i-1]>0ands[i-dp[i-1]-1]=='(':dp[i]=dp[i-1]+(dp[i-dp[i-1]-2]ifi-dp[i-1]>=2else0)+2max_len=max(max_len,dp[i])returnmax_len解析：动态规划解法使用数组`dp[i]`表示以`s[i]`结尾的最长有效括号长度。状态转移方程如下：1.当`s[i]==')'`且`s[i-1]=='('`时：-对应`"()"`，`dp[i]=dp[i-2]+2`（因为前面没有其他有效括号）。2.当`s[i]==')'`且`s[i-1]==')'`时：-检查`s[i-dp[i-1]-1]`是否为`'('`。如果是，则可以扩展有效括号，`dp[i]=dp[i-1]+2+dp[i-dp[i-1]-2]`。3.初始化：`dp`数组全为0，`max_len`记录最大值。时间复杂度：O(n)，空间复杂度：O(n)。3.合并区间（贪心算法）答案：pythondefmerge(intervals:List[List[int]])->List[List[int]]:ifnotintervals:return[]按起点排序intervals.sort(key=lambdax:x[0])merged=[]forintervalinintervals:如果列表为空，或当前区间与合并区间的最后一个区间不重叠ifnotmergedormerged[-1][1]<interval[0]:merged.append(interval)else:否则，合并区间merged[-1][1]=max(merged[-1][1],interval[1])returnmerged解析：贪心算法的思路是按起点排序，然后逐个合并：1.排序：按区间的起点升序排序。2.合并：-初始化一个空列表`merged`，用于存储合并后的区间。-遍历每个区间`interval`：-如果`merged`为空，或当前区间的起点`interval[0]`大于`merged`的最后一个区间的终点`merged[-1][1]`，说明不重叠，直接添加到`merged`。-否则，将当前区间的终点与`merged`的最后一个区间的终点取最大值，进行合并。时间复杂度：O(nlogn)，空间复杂度：O(n)。二、数据结构题4.二叉树的最大深度（递归）答案：pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefmaxDepth(root:TreeNode)->int:ifnotroot:return0return1+max(maxDepth(root.left),maxDepth(root.right))解析：递归解法利用二叉树的结构，定义`maxDepth`函数返回当前节点的最大深度：1.基本情况：如果节点为空，返回0。2.递归情况：返回左子树和右子树的最大深度加1。时间复杂度：O(n)，空间复杂度：O(h)，其中`h`是树的高度。5.LRU缓存机制（哈希表+双向链表）答案：pythonclassLRUCache:classNode:def__init__(self,key=0,value=0):self.key=keyself.value=valueself.prev=Noneself.next=Nonedef__init__(self,capacity:int):self.capacity=capacityself.cache={}self.head=self.Node(0,0)self.tail=self.Node(0,0)self.head.next=self.tailself.tail.prev=self.headdefget(self,key:int)->int:ifkeyinself.cache:node=self.cache[key]self._move_to_front(node)returnnode.valuereturn-1defput(self,key:int,value:int)->None:ifkeyinself.cache:node=self.cache[key]node.value=valueself._move_to_front(node)else:iflen(self.cache)==self.capacity:self._remove_lru()new_node=self.Node(key,value)self.cache[key]=new_nodeself._add_to_front(new_node)def_move_to_front(self,node):self._remove_node(node)self._add_to_front(node)def_remove_node(self,node):node.prev.next=node.nextnode.next.prev=node.prevdef_add_to_front(self,node):node.prev=self.headnode.next=self.head.nextself.head.next.prev=nodeself.head.next=nodedef_remove_lru(self):lru=self.tail.prevself._remove_node(lru)delself.cache[lru.key]解析：LRU缓存的核心是快速访问和删除最近最少使用的元素。使用双向链表+哈希表实现：1.双向链表：-头节点`head`和尾节点`tail`构成空链表。-链表头部表示最近使用的元素，尾部表示最久未使用的元素。-提供`_move_to_front`将节点移动到头部，`_remove_node`删除节点，`_add_to_front`添加节点到头部，`_remove_lru`删除尾部节点。2.哈希表：-`cache`存储`key`到节点的映射，实现O(1)的访问和删除。时间复杂度：O(1)。6.二叉树的层序遍历（BFS）答案：pythonfromcollectionsimportdequedeflevelOrder(root:TreeNode)->List[List[int]]:ifnotroot:return[]result=[]queue=deque([root])whilequeue:level_size=len(queue)level=[]for_inrange(level_size):node=queue.popleft()level.append(node.val)ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)result.append(level)returnresult解析：BFS（广度优先搜索）使用队列实现层序遍历：1.初始化队列，将根节点入队。2.当队列不为空时：-记录当前层的节点数量`level_size`。-遍历当前层的所有节点，出队并添加到当前层列表`level`中。-将左右子节点入队。-将当前层列表`level`添加到结果`result`中。时间复杂度：O(n)，空间复杂度：O(n)。三、编程实现题7.快速排序的非递归实现答案：pythondefquickSortIterative(nums:List[int])->List[int]:stack=[(0,len(nums)-1)]whilestack:start,end=stack.pop()ifstart>=end:continuepivot=nums[end]left=startforiinrange(start,end):ifnums[i]<=pivot:nums[i],nums[left]=nums[left],nums[i]left+=1nums[left],nums[end]=nums[end],nums[left]stack.append((start,left-1))stack.append((left+1,end))returnnums解析：非递归实现使用栈模拟递归过程：1.初始化栈，存储初始的`start`和`end`。2.当栈不为空时：-弹出栈顶的`start`和`end`。-使用`pivot`（`nums[end]`）划分，将小于等于`pivot`的元素移到左边。-将划分后的左右区间重新入栈，继续处理。时间复杂度：平均O(nlogn)，最坏O(n²)。8.二叉搜索树的最近公共祖先答案：pythondeflowestCommonAncestor(root:TreeNode,p:TreeNode,q:TreeNode)->TreeNode:current=rootwhilecurrent:ifp.val<current.valandq.val<current.val:current=current.leftelifp.val>current.val