2026年互联网技术岗面试宝典算法题快速上手指南

2026年互联网技术岗面试宝典：算法题快速上手指南一、链表算法（3题，每题10分）背景：链表是互联网面试中的高频考点，尤其在分布式系统、缓存机制、数据流处理中应用广泛。1.题目：给定一个链表，判断是否存在环。如果存在，返回环的入口节点；如果不存在，返回`null`。示例：输入：`1->2->3->4->2`（形成环）输出：节点`2`2.题目：合并两个有序链表，返回合并后的头节点。示例：输入：`1->3->5`和`2->4->6`输出：`1->2->3->4->5->6`3.题目：删除链表的倒数第`n`个节点，并返回新链表的头节点。示例：输入：`1->2->3->4->5`，`n=2`输出：`1->2->3->5`二、栈与队列算法（2题，每题15分）背景：栈和队列常用于解决括号匹配、滑动窗口、BFS等问题，是系统设计的基础。1.题目：实现一个`MinStack`类，支持在`O(1)`时间复杂度内获取栈的最小值。示例：pythonstack=MinStack()stack.push(5)stack.push(2)stack.getMin()#返回2stack.pop()stack.getMin()#返回52.题目：给定一个字符串`s`，判断是否可以通过删除一些字符使其变为有效的括号串（`()`）。示例：输入：`"()[]{}"`输出：`True`输入：`"(]"`输出：`False`三、树与二叉搜索树（3题，每题10分）背景：树结构在数据库索引、文件系统、决策树中应用广泛，是算法面试的核心。1.题目：二叉树的中序遍历、前序遍历和后序遍历。示例：输入：1/\23输出：-中序：`2->1->3`-前序：`1->2->3`-后序：`2->3->1`2.题目：判断两棵二叉树是否相同（结构相同且节点值相同）。示例：树1：树2：11/\/\2222输出：`True`3.题目：在二叉搜索树中查找给定值的节点，并返回其父节点。示例：输入：`root=[4,2,7,1,3]`，`target=2`输出：父节点`4`四、哈希表算法（3题，每题10分）背景：哈希表是解决高频查找、去重、统计问题的利器，尤其在社交平台、电商系统中有广泛应用。1.题目：给定一个字符串`s`，返回其中不重复的最长子串的长度。示例：输入：`"abcabcbb"`输出：`3`（"abc"）2.题目：判断两个数组中是否有至少一个共同元素。示例：输入：`nums1=[1,2,3]`，`nums2=[4,5,6]`输出：`False`3.题目：实现`LRU`缓存机制，支持`get`和`put`操作。示例：pythoncache=LRUCache(2)cache.put(1,1)cache.put(2,2)cache.get(1)#返回1cache.put(3,3)#去除键2cache.get(2)#返回-1(未找到)五、动态规划算法（2题，每题15分）背景：动态规划常用于解决背包问题、最长递增子序列等，是算法面试的难点。1.题目：给定一个整数数组，返回其最长递增子序列的长度。示例：输入：`[10,9,2,5,3,7,101,18]`输出：`4`（5->7->101或2->3->7->101）2.题目：零钱兑换问题：给定面值`coins`和总金额`amount`，返回最少需要多少枚硬币。示例：输入：`coins=[1,2,5]`，`amount=11`输出：`3`（5+5+1）六、贪心算法（2题，每题15分）背景：贪心算法在资源分配、排序优化中效率高，是面试常考题型。1.题目：合并区间：给定一个区间数组，合并所有重叠的区间。示例：输入：`[[1,3],[2,6],[8,10],[15,18]]`输出：`[[1,6],[8,10],[15,18]]`2.题目：在一条直线上有`n`个加油站，每个加油站提供一定量的油，返回从起点到终点的最小加油次数。示例：输入：`[1,2,3,4,5]`（每段距离相同）输出：`1`（只需在起点加满油）七、字符串算法（2题，每题15分）背景：字符串处理在自然语言处理、数据校验中应用广泛。1.题目：翻转字符串中的单词顺序，但保持每个单词内部字符顺序不变。示例：输入：`"theskyisblue"`输出：`"blueisskythe"`2.题目：实现字符串的子串查找（暴力匹配和KMP算法可选）。示例：输入：`text="ABABDABACDABABCABAB"`，`pattern="ABABCABAB"`输出：`10`（子串开始位置）八、数学与位运算（2题，每题15分）背景：数学与位运算是低级优化的重要基础，常用于面试中的思维考察。1.题目：给定一个非负整数`n`，返回其二进制表示中`1`的个数。示例：输入：`n=11`（二进制`1011`）输出：`3`2.题目：判断一个数是否是`2`的幂次方。示例：输入：`n=16`输出：`True`（`2^4=16`）答案与解析一、链表算法1.判断链表环的入口节点答案：pythonclassListNode:def__init__(self,x):self.val=xself.next=NonedefdetectCycle(head:ListNode)->ListNode:slow,fast=head,headwhilefastandfast.next:slow=slow.nextfast=fast.next.nextifslow==fast:slow=headwhileslow!=fast:slow=slow.nextfast=fast.nextreturnslowreturnNone解析：-使用快慢指针判断环（Floyd循环检测）。当`slow==fast`时存在环，重置`slow`为头节点并移动直到找到环入口。-时间复杂度：`O(N)`，空间复杂度：`O(1)`。2.合并两个有序链表答案：pythondefmergeTwoLists(l1:ListNode,l2:ListNode)->ListNode:dummy=ListNode(0)current=dummywhilel1andl2:ifl1.val<l2.val:current.next=l1l1=l1.nextelse:current.next=l2l2=l2.nextcurrent=current.nextcurrent.next=l1orl2returndummy.next解析：-使用虚拟头节点简化边界处理，逐个比较节点值并合并。3.删除倒数第`n`个节点答案：pythondefremoveNthFromEnd(head:ListNode,n:int)->ListNode:dummy=ListNode(0)dummy.next=headfirst=dummysecond=dummyfor_inrange(n+1):first=first.nextwhilefirst:first=first.nextsecond=second.nextsecond.next=second.next.nextreturndummy.next解析：-使用双指针，`first`先走`n+1`步，然后`first`和`second`同步移动，`second`的`next`即为待删除节点。二、栈与队列算法1.MinStack实现答案：pythonclassMinStack:def__init__(self):self.stack=[]self.min_stack=[]defpush(self,val:int):self.stack.append(val)ifnotself.min_stackorval<=self.min_stack[-1]:self.min_stack.append(val)defpop(self)->int:ifself.stack:top=self.stack.pop()iftop==self.min_stack[-1]:self.min_stack.pop()returntopreturnNonedefgetMin(self)->int:returnself.min_stack[-1]ifself.min_stackelseNone解析：-维护一个辅助栈`min_stack`存储当前最小值，`push`时若`val`小于等于当前最小值则入栈，`pop`时若出栈元素等于最小值则同步出栈。2.括号匹配答案：pythondefisValid(s:str)->bool:stack=[]mapping={')':'(','}':'{',']':'['}forcharins:ifcharinmapping:top=stack.pop()ifstackelse'#'ifmapping[char]!=top:returnFalseelse:stack.append(char)returnnotstack解析：-使用栈匹配括号，遇到闭括号时检查栈顶是否为对应开括号。三、树与二叉搜索树1.树的遍历答案：python中序遍历（递归）definorderTraversal(root):returninorderTraversal(root.left)+[root.val]+inorderTraversal(root.right)ifrootelse[]前序遍历（递归）defpreorderTraversal(root):return[root.val]+preorderTraversal(root.left)+preorderTraversal(root.right)ifrootelse[]后序遍历（递归）defpostorderTraversal(root):returnpostorderTraversal(root.left)+postorderTraversal(root.right)+[root.val]ifrootelse[]解析：-递归实现简单直观，中序`左-根-右`，前序`根-左-右`，后序`左-右-根`。2.判断两棵树相同答案：pythondefisSameTree(p,q):ifnotpandnotq:returnTrueifnotpornotq:returnFalsereturnp.val==q.valandisSameTree(p.left,q.left)andisSameTree(p.right,q.right)解析：-递归比较节点值和子树是否相同。3.查找节点父节点答案：pythondeffindParent(root,target):ifnotroot:returnNoneifroot.leftandroot.left.val==target:returnrootifroot.rightandroot.right.val==target:returnrootreturnfindParent(root.left,target)orfindParent(root.right,target)解析：-递归遍历左右子树，找到目标节点时返回父节点。四、哈希表算法1.最长无重复子串答案：pythondeflengthOfLongestSubstring(s:str)->int:char_map={}left=0max_len=0forright,charinenumerate(s):ifcharinchar_mapandchar_map[char]>=left:left=char_map[char]+1char_map[char]=rightmax_len=max(max_len,right-left+1)returnmax_len解析：-滑动窗口+哈希表记录字符上一次出现位置，优化重复字符处理。2.判断数组有公共元素答案：pythondefhasCommon(nums1,nums2):returnset(nums1)&set(nums2)解析：-集合交集操作可快速判断是否有公共元素。3.LRU缓存机制答案：pythonclassLRUCache:def__init__(self,capacity:int):self.capacity=capacityself.cache={}self.order=[]defget(self,key:int)->int:ifkeyinself.cache:self.order.remove(key)self.order.append(key)returnself.cache[key]return-1defput(self,key:int,value:int)->None:ifkeyinself.cache:self.order.remove(key)eliflen(self.cache)==self.capacity:self.cache.pop(self.order.pop(0))self.cache[key]=valueself.order.append(key)解析：-使用哈希表记录键值对，双向链表维护使用顺序。五、动态规划算法1.最长递增子序列答案：pythondeflengthOfLIS(nums):dp=[1]len(nums)foriinrange(1,len(nums)):forjinrange(i):ifnums[i]>nums[j]:dp[i]=max(dp[i],dp[j]+1)returnmax(dp)解析：-`dp[i]`表示以`nums[i]`结尾的最长递增子序列长度，遍历更新。2.零钱兑换答案：pythondefcoinChange(coins,amount):dp=[amount+1](amount+1)dp[0]=0foriinrange(1,amount+1):forcoinincoins:ifi>=coin:dp[i]=min(dp[i],dp[i-coin]+1)returndp[amount]ifdp[amount]!=amount+1else-1解析：-`dp[i]`表示凑出`i`所需的最少硬币数，贪心更新。六、贪心算法1.合并区间答案：pythondefmerge(intervals):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解析：-先按起点排序，贪心合并重叠区间。2.最少加油次数答案：pythondefminRefuelStops(target,fuel,positions):pq=[]current_fuel=0stops=0positions=sorted([(p,f)forp,finzip(positions,fuel)])foriinrange(len(positions)-1,-1,-1):p,f=positions[i]ifp+current_fuel>=target:returnstopswhilepqandcurrent_fuel<p:current_fuel+=-heapq.heappop(pq)stops+=1ifcurrent_fuel<p:return-1heapq.heappush(pq,-f)returnstopsifcurrent_fuel>=targetelse-1解析：-贪心选择当前能覆盖最远距离的加油站，优先级队列（最大堆）维护最近加油站。七、字符串算法1.翻转单词顺序答案：pythondefreverseWords(s:str)->str:return''.join(s.split()[::-1])解析：-按空格分割反转再连接。2.子串查找（