2026年程序员面试算法题解析

2026年程序员面试算法题解析一、字符串处理（3题，每题10分）1.题目：给定一个字符串`s`，请判断其是否是一个有效的括号嵌套字符串。字符串只包含`'('`和`')'`，且括号必须正确匹配。例如：-输入：`"(()())"`→输出：`true`-输入：`"())("`→输出：`false`-输入：`"(()"`→输出：`false`要求：-时间复杂度O(n)-空间复杂度O(1)2.题目：将一个字符串中的所有空格`''`替换为`%20`。例如：-输入：`"Wearehappy."`→输出：`"We%20are%20happy."`要求：-不能使用额外的字符串库函数，需原地修改字符串（假设有足够空间存储）。3.题目：实现一个函数`isPalindrome(s)`，判断一个字符串`s`是否是回文串，忽略大小写和非字母数字字符。例如：-输入：`"Aman,aplan,acanal:Panama"`→输出：`true`-输入：`"raceacar"`→输出：`false`要求：-时间复杂度O(n)-空间复杂度O(1)二、数组与矩阵（4题，每题12分）1.题目：给定一个非负整数数组`nums`，返回其中和最大的连续子数组的和。例如：-输入：`[-2,1,-3,4,-1,2,1,-5,4]`→输出：`6`（子数组`[4,-1,2,1]`）要求：-动态规划解法2.题目：给定一个`mxn`的矩阵，找出其中最长的递增路径的长度。路径可以从任意一个单元格开始，只能向下、向右或向左移动。例如：-输入：[[3,4,5],[3,2,6],[2,2,1]]输出：`4`（路径`[3,4,5,6]`）要求：-深度优先搜索（DFS）+记忆化搜索3.题目：给定一个`nxn`的二维矩阵，判断其是否是一个有效的“魔方阵”（即每行、每列、两条对角线的数字之和都相等）。例如：-输入：[[2,7,6],[9,5,1],[4,3,8]]输出：`true`要求：-不需要计算所有和，只需验证一致性4.题目：给定一个`mxn`的矩阵，将矩阵旋转90度（顺时针）。例如：-输入：[[1,2,3],[4,5,6],[7,8,9]]输出：[[7,4,1],[8,5,2],[9,6,3]]要求：-先转置矩阵，再反转每一行三、链表（3题，每题15分）1.题目：给定两个非空链表`l1`和`l2`，将它们合并为一个新的链表，合并后的链表按升序排列。例如：-输入：l1:1->2->4,l2:1->3->4输出：`1->1->2->3->4->4`要求：-迭代解法2.题目：判断一个链表是否有环，并返回环的入口节点。例如：-输入：head:3->2->0->-4,next(2)指向-4输出：`2`（环的入口节点）要求：-快慢指针法3.题目：删除链表的倒数第`n`个节点。例如：-输入：head:1->2->3->4->5,n=2输出：`1->2->3->5`要求：-双指针法四、树与递归（3题，每题15分）1.题目：给定一个二叉树，判断其是否是平衡二叉树（即任意节点的左右子树高度差不超过1）。例如：-输入：3/\920/\157输出：`true`要求：-递归解法（自底向上）2.题目：给定一个二叉搜索树（BST），查找其中值介于`low`和`high`之间的所有节点之和。例如：-输入：10/\515/\\3718low=7,high=15→输出：`32`（节点3+7+10+15）要求：-利用BST性质优化遍历3.题目：实现二叉树的层序遍历（BFS）。例如：-输入：1/\23/\\456输出：`[1,2,3,4,5,6]`要求：-使用队列实现五、动态规划（3题，每题15分）1.题目：给定一个整数数组`nums`，返回其中最多有多少个不重叠的“好子数组”（子数组中所有元素都相等）。例如：-输入：`[1,1,0,1,1,1]`→输出：`3`（子数组`[1,1,0]`,`[1,1,1]`,`[1]`）要求：-动态规划解法2.题目：给定一个字符串`s`和一个字典`wordDict`，判断`s`是否可以由字典中的单词组合而成。例如：-输入：s="applepenapple",wordDict=["apple","pen"]输出：`true`（"applepenapple"→"applepenapple"）要求：-动态规划解法（记忆化搜索）3.题目：给定一个非负整数`n`，计算`1`到`n`的所有整数中数字`1`出现的次数。例如：-输入：`n=13`→输出：`6`（1,10,11,12,13各有一个1，共6个）要求：-数学解法+动态规划辅助答案与解析一、字符串处理1.有效性括号嵌套字符串：解法：-使用栈，遍历字符串：-遇到`'('`，压入栈；-遇到`')'`，检查栈是否为空：若为空，则无效；否则弹出栈顶。-最后检查栈是否为空，若为空则有效。时间复杂度：O(n)空间复杂度：O(1)（假设栈空间不计入）2.空格替换为`%20`：解法：-双指针法：-从后向前遍历字符串，统计空格数量；-修改字符串时，从后向前替换，避免覆盖未处理的字符。时间复杂度：O(n)空间复杂度：O(1)3.回文串判断：解法：-双指针法：-左右指针分别指向字符串首尾，跳过非字母数字字符；-比较对应字符是否相等，若不等则返回`false`；-若全部相等，返回`true`。时间复杂度：O(n)空间复杂度：O(1)二、数组与矩阵1.最大子数组和（动态规划）：解法：-定义`dp[i]`为以`nums[i]`结尾的最大子数组和；-递推关系：`dp[i]=max(dp[i-1]+nums[i],nums[i])`；-最大值在`dp`数组中。时间复杂度：O(n)空间复杂度：O(n)（可优化至O(1)）2.最长递增路径（DFS+记忆化）：解法：-定义`dp[i][j]`为以`(i,j)`结尾的最长递增路径长度；-从上、左、下、右四个方向搜索，若相邻节点更大，则更新`dp[i][j]`；-记忆化避免重复计算。时间复杂度：O(mn)空间复杂度：O(mn)3.魔方阵判断：解法：-计算左上角节点的行和、列和、主对角线和、副对角和；-遍历其他节点，检查是否满足上述和相等。时间复杂度：O(n^2)空间复杂度：O(1)4.矩阵旋转90度：解法：-先转置矩阵：交换`(i,j)`和`(j,i)`；-再反转每一行：`reverse(row)`。时间复杂度：O(mn)空间复杂度：O(1)三、链表1.合并两个有序链表（迭代）：解法：-创建虚拟头节点`dummy`，比较两个链表节点大小，按顺序连接；-最后处理剩余节点。时间复杂度：O(n)空间复杂度：O(1)2.判断链表环并返回入口（快慢指针）：解法：-快指针每次走两步，慢指针走一步；-若存在环，快慢指针必相遇；-再次从头遍历，快指针走一步，相遇点即为入口。时间复杂度：O(n)空间复杂度：O(1)3.删除倒数第n个节点（双指针）：解法：-创建虚拟头节点，快指针先走`n+1`步；-快慢指针同时走，快指针到末尾时，慢指针的下一个节点即为目标。时间复杂度：O(n)空间复杂度：O(1)四、树与递归1.平衡二叉树判断（自底向上）：解法：-定义`height(node)`返回节点高度；-若左右子树高度差>1，返回`-1`表示不平衡；-否则返回高度，递归检查子树。时间复杂度：O(n)空间复杂度：O(h)（递归栈）2.BST中值在[low,high]的节点之和：解法：-利用BST性质，若节点值<low，则左子树无需遍历；-若节点值>high，则右子树无需遍历；-递归计算左右子树和。时间复杂度：O(n)空间复杂度：O(h)3.层序遍历（BFS）：解法：-使用队列，初始入队根节点；-每次弹出节点，记录值，并将子节点入队。时间复杂度：O(n)空间复杂度：O(n)五、动态规划1.最多不重叠好子数组数量：解法：-定义`dp[i]`为前`i`个元素的最大好子数组数量；-遍历数组，遇到`nums[i]!=nums[i-1]`，则`dp[i]=dp[i-1]`；-否则`dp[i]=max(dp[i-1],dp[i-2]+1)`。时间复杂度：O(n)空间复杂度：O(n)2.字符串分割（回溯+记忆化）：解法：-定义`dp[i]`为前`i`个字符是否可由字典单词组成；-遍历`i`，检查`j`到`i`的子串是否在字典中，并利用`dp[j-1]`判断；