2026年软件工程师面试算法题集

2026年软件工程师面试算法题集1.数组与字符串（3题，每题10分）题目1（10分）：给定一个包含重复字符的字符串`s`，返回其中不重复的最长子字符串的长度。例如，输入`s="abcabcbb"`，输出`4`（最长不重复子串为"bcab"）。题目2（10分）：给定一个整数数组`arr`，其中元素的范围在`1`到`n`（`n`为数组长度），且每个元素出现一次或两次。找出所有出现两次的元素。例如，输入`arr=[4,3,2,7,8,2,3,1]`，输出`[2,3]`。题目3（10分）：将一个字符串`s`中的所有`0`移动到末尾，保持其他字符的相对顺序。例如，输入`s="012"`，输出`"210"`。2.链表（2题，每题15分）题目4（15分）：设计一个单链表，支持在`O(1)`时间复杂度内删除任意节点（假设节点值唯一）。例如，给定链表`1->2->3`，删除节点`2`后变为`1->3`。题目5（15分）：判断一个链表是否为回文链表。例如，输入`1->2->2->1`，返回`true`。3.栈与队列（2题，每题15分）题目6（15分）：给定一个包含`'('`,`')'`,`''`的字符串`s`，判断是否存在一种括号匹配方式，使得字符串有效。`''`可以视为`'('`或`')'`。例如，输入`s="()"`，返回`true`。题目7（15分）：实现一个`MinStack`类，支持在`O(1)`时间复杂度内获取栈中最小值。例如，`MinStack`包含操作`push(5)`,`push(2)`,`min()`（返回`2`），`pop()`，`min()`（返回`5`）。4.树与二叉搜索树（2题，每题15分）题目8（15分）：给定一个二叉搜索树，找出其中所有范围在`[low,high]`的节点值之和。例如，输入`root=[10,5,15,3,7,null,18]`，`low=7`，`high=15`，输出`32`（节点`7`和`10`）。题目9（15分）：判断两棵二叉树是否相同。例如，树`A`为`[1,2,3]`，树`B`为`[1,2,3]`，返回`true`；树`A`为`[1,2]`，树`B`为`[1,2,3]`，返回`false`。5.哈希表（2题，每题15分）题目10（15分）：设计一个`LRUCache`类，支持在`O(1)`时间复杂度内实现`get`和`put`操作。缓存容量为`capacity`。例如，`LRUCache(2)`，`put(1,1)`,`put(2,2)`,`get(1)`（返回`1`），`put(3,3)`（驱逐`2`），`get(2)`（返回`-1`）。题目11（15分）：统计一个字符串`s`中所有不同字母的异或结果。例如，输入`s="abc"`，异或结果为`a^b^c`。6.排序与搜索（2题，每题15分）题目12（15分）：在一个未排序的数组`arr`中，找到第三大的数。如果数组长度小于`3`，返回最大数。例如，输入`arr=[1,2,-2147483648,9,9,2]`，输出`2`。题目13（15分）：实现二分查找的变种：给定一个旋转排序数组`nums`（如`[4,5,6,7,0,1,2]`），找到目标值`target`的索引。例如，输入`nums=[4,5,6,7,0,1,2]`，`target=0`，输出`4`。7.动态规划（2题，每题15分）题目14（15分）：给定一个整数数组`nums`，返回其中最多有多少个连续的`1`。例如，输入`nums=[1,1,0,1,1,1]`，输出`3`。题目15（15分）：给定一个字符串`s`，判断是否可以通过删除一些字符将其转换为回文串。例如，输入`s="baab"`，返回`true`（删除第一个`b`）。8.图（2题，每题15分）题目16（15分）：给定一个无向图，判断其是否为二分图（可以用两种颜色染色，使得相邻节点颜色不同）。例如，输入邻接矩阵`[[1,3],[0,2],[1,3],[0,2]]`，返回`true`。题目17（15分）：给定一个`mxn`的矩阵，找出从左上角到右下角的最短路径（只能向下或向右移动）。例如，输入`grid=[[0,0,0],[0,1,0],[0,0,0]]`，输出`2`。9.数学与位运算（2题，每题15分）题目18（15分）：给定一个正整数`n`，计算其二进制表示中`1`的个数。例如，输入`n=11`（二进制`1011`），输出`3`。题目19（15分）：给定两个正整数`a`和`b`，计算它们的二进制表示中不同位（异或）的个数。例如，输入`a=1`（`01`），`b=2`（`10`），输出`2`。答案与解析1.数组与字符串题目1：-答案：滑动窗口法。维护一个窗口`[left,right]`，使用哈希表记录窗口内字符出现次数。遍历字符串，若字符在哈希表中且计数大于`1`，则移动`left`直到该字符计数为`1`。每次更新最大长度`max_len`。-解析：时间`O(n)`，空间`O(n)`。题目2：-答案：哈希表记录元素出现次数，遍历数组将出现两次的元素加入结果列表。-解析：时间`O(n)`，空间`O(n)`。题目3：-答案：双指针法。维护两个指针`left`和`right`，分别指向字符串首尾。交换`left`非`0`字符和`right`字符，直到`left>=right`。-解析：时间`O(n)`，空间`O(1)`。2.链表题目4：-答案：直接复制前一个节点的值到当前节点，然后删除前一个节点。-解析：时间`O(1)`，空间`O(1)`。题目5：-答案：快慢指针判断回文。将前半部分反转，比较反转后与后半部分是否一致。-解析：时间`O(n)`，空间`O(1)`。3.栈与队列题目6：-答案：使用栈和计数器处理`'('`,`')'`,`''`。遍历字符串，遇到`''`时考虑两种情况，并使用两个计数器维护左括号和星号的数量。-解析：时间`O(n)`，空间`O(n)`。题目7：-答案：使用两个栈，一个存储常规值，另一个存储当前最小值。`push`时将当前最小值也压入最小值栈。`pop`时比较栈顶是否为最小值，是则同时弹出。-解析：时间`O(1)`，空间`O(n)`。4.树与二叉搜索树题目8：-答案：递归遍历二叉搜索树，累加`[low,high]`范围内的节点值。-解析：时间`O(n)`，空间`O(h)`。题目9：-答案：递归比较两棵树的根节点，以及左子树和右子树。-解析：时间`O(n)`，空间`O(h)`。5.哈希表题目10：-答案：使用双向链表和哈希表实现。链表头尾分别表示最近和最久未使用节点，哈希表记录节点值和链表中的位置。-解析：时间`O(1)`，空间`O(capacity)`。题目11：-答案：遍历字符串，使用哈希表记录每个字母的出现次数，最后计算所有字母的异或。-解析：时间`O(n)`，空间`O(1)`（假设字母表固定）。6.排序与搜索题目12：-答案：排序后取第`n-2`个元素。若数组长度小于`3`，返回最大值。-解析：时间`O(nlogn)`，空间`O(1)`（原地排序）。题目13：-答案：找到旋转点，将数组分成两部分，分别在左半部分和右半部分进行二分查找。-解析：时间`O(logn)`，空间`O(1)`。7.动态规划题目14：-答案：遍历数组，记录当前连续`1`的个数，遇到`0`时重置。-解析：时间`O(n)`，空间`O(1)`。题目15：-答案：转化为最长公共子序列问题，动态规划计算最长回文子序列。-解析：时间`O(n^2)`，空间`O(n^2)`。8.图题目16：-答案：使用BFS或DFS进行深度优先染色，判断是否能完成二分染色。-解析：时间`O(V+E)`，空间`O(V)`。题目17：-答案：BFS从左上角开始，记录已访问节点，每次移动向下或向右。-解析：时间`O(mn)`，空间`O(mn