程序员面试攻略代码实现与算法设计问题解析

2026年程序员面试攻略：代码实现与算法设计问题解析一、链表操作题（共3题，每题10分）1.题目：实现一个功能，判断一个链表是否存在环。如果存在环，返回环的入口节点；如果不存在环，返回`null`。链表节点定义如下：pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=next2.题目：给定一个链表，反转链表并返回反转后的头节点。例如，输入`1->2->3->4->5`，输出`5->4->3->2->1`。3.题目：合并两个有序链表，合并后的链表依然有序。例如，输入链表1：`1->2->4`，链表2：`1->3->4`，输出`1->1->2->3->4->4`。二、动态规划题（共2题，每题15分）1.题目：给定一个字符串，找出其中不含有重复字符的最长子串的长度。例如，输入`s="abcabcbb"`，输出`3`（因为无重复的最长子串是`abc`）。2.题目：给你一个包含`n`个整数的数组`nums`，判断数组中是否存在三个元素`a,b,c`，使得`a+b+c=0`？请找出所有满足条件且不重复的三元组。例如，输入`nums=[-1,0,1,2]`，输出`[-1,0,1]`和`[-1,2,1]`。三、树与二叉搜索树（共2题，每题15分）1.题目：实现二叉树的深度优先遍历（前序、中序、后序），并分别用递归和迭代的方式实现。二叉树节点定义如下：pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=right2.题目：给定一个二叉搜索树，找出其中所有满足条件的节点，使得这些节点的值之和等于给定目标值`target`。例如，输入二叉搜索树和`target=22`，输出满足条件的节点值组合。四、数组与矩阵操作题（共3题，每题10分）1.题目：给定一个二维数组`matrix`，原地旋转90度。例如，输入`matrix=[[1,2,3],[4,5,6],[7,8,9]]`，输出`[[7,4,1],[8,5,2],[9,6,3]]`。2.题目：给定一个包含`n`个整数的数组，返回所有可能的子集。例如，输入`nums=[1,2,3]`，输出`[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]`。3.题目：给定一个包含`n`个整数的数组，找出其中和最大且不连续的子序列的和。例如，输入`nums=[1,2,[3,1],3,1]`，输出`6`（子序列`[3,1],3`）。五、贪心算法题（共2题，每题15分）1.题目：给定一个整数数组`coins`，表示不同面值的硬币，以及一个整数`amount`，计算可以凑出`amount`的硬币组合数。假设每种面值的硬币数量无限。例如，输入`coins=[1,2,5]`，`amount=5`，输出`4`（组合`5`,`2+2+1`,`2+1+1+1`,`1+1+1+1+1`）。2.题目：给定一个非负整数数组`height`，表示每个位置的水桶的高度，计算可以接住的水的总量。例如，输入`height=[1,8,6,2,5,4,8,3,7]`，输出`49`（接住的总量为`[1,8,6,2,5,4,8,3,7]`中的最小值和相邻位置差值的累加）。六、字符串处理题（共3题，每题10分）1.题目：实现一个函数，判断一个字符串是否是有效的括号组合。例如，输入`"()"`，输出`True`；输入`"()[]{}"`，输出`True`；输入`"(]"`，输出`False`。2.题目：给定一个字符串`s`，找到其中最长的回文子串。例如，输入`s="babad"`，输出`"bab"`或`"aba"`。3.题目：给定两个字符串`s1`和`s2`，判断`s2`是否可以通过对`s1`进行删除某些字符得到。例如，输入`s1="abcde"`,`s2="ace"`，输出`True`。答案与解析一、链表操作题1.判断链表是否存在环并返回入口节点：答案：使用快慢指针法（Floyd'sTortoiseandHare）。快指针每次走两步，慢指针每次走一步，如果存在环，快慢指针最终会相遇；相遇后，将慢指针移到头节点，快慢指针再次每次走一步，相遇点即为环的入口节点。pythondefdetectCycle(head):ifnotheadornothead.next:returnNoneslow,fast=head,headwhilefastandfast.next:slow=slow.nextfast=fast.next.nextifslow==fast:slow=headwhileslow!=fast:slow=slow.nextfast=fast.nextreturnslowreturnNone2.反转链表：答案：使用迭代法，遍历链表并逐个反转节点指向。pythondefreverseList(head):prev,curr=None,headwhilecurr:next_node=curr.nextcurr.next=prevprev=currcurr=next_nodereturnprev3.合并两个有序链表：答案：使用伪头节点，同时遍历两个链表，按顺序合并。pythondefmergeTwoLists(l1,l2):dummy=ListNode(0)curr=dummywhilel1andl2:ifl1.val<l2.val:curr.next=l1l1=l1.nextelse:curr.next=l2l2=l2.nextcurr=curr.nextcurr.next=l1orl2returndummy.next二、动态规划题1.最长无重复子串：答案：使用滑动窗口法，记录字符上一次出现的位置，动态调整窗口范围。pythondeflengthOfLongestSubstring(s):char_map={}left=0max_len=0forrightinrange(len(s)):ifs[right]inchar_map:left=max(left,char_map[s[right]]+1)char_map[s[right]]=rightmax_len=max(max_len,right-left+1)returnmax_len2.三数之和：答案：先排序，然后使用双指针法。pythondefthreeSum(nums):nums.sort()result=[]foriinrange(len(nums)-2):ifi>0andnums[i]==nums[i-1]:continueleft,right=i+1,len(nums)-1whileleft<right:total=nums[i]+nums[left]+nums[right]iftotal==0:result.append([nums[i],nums[left],nums[right]])whileleft<rightandnums[left]==nums[left+1]:left+=1whileleft<rightandnums[right]==nums[right-1]:right-=1left+=1right-=1eliftotal<0:left+=1else:right-=1returnresult三、树与二叉搜索树1.二叉树遍历：前序遍历（递归）：pythondefpreorderTraversal(root):ifnotroot:return[]return[root.val]+preorderTraversal(root.left)+preorderTraversal(root.right)中序遍历（递归）：pythondefinorderTraversal(root):ifnotroot:return[]returninorderTraversal(root.left)+[root.val]+inorderTraversal(root.right)后序遍历（递归）：pythondefpostorderTraversal(root):ifnotroot:return[]returnpostorderTraversal(root.left)+postorderTraversal(root.right)+[root.val]前序遍历（迭代）：pythondefpreorderTraversalIterative(root):ifnotroot:return[]stack,result=[root],[]whilestack:node=stack.pop()result.append(node.val)ifnode.right:stack.append(node.right)ifnode.left:stack.append(node.left)returnresult2.二叉搜索树中和为target的节点：答案：使用深度优先搜索（DFS）遍历树，记录路径和，如果路径和等于`target`，则记录该路径。pythondefpathSum(root,target):defdfs(node,path,target):ifnotnode:returnpath.append(node.val)current_sum=sum(path)ifcurrent_sum==target:result.append(path.copy())dfs(node.left,path,target)dfs(node.right,path,target)path.pop()result=[]dfs(root,[],target)returnresult四、数组与矩阵操作题1.旋转二维矩阵：答案：先按层反转，再反转每层。pythondefrotate(matrix):n=len(matrix)foriinrange(n//2):forjinrange(i,n-i-1):temp=matrix[i][j]matrix[i][j]=matrix[n-j-1][i]matrix[n-j-1][i]=matrix[n-i-1][n-j-1]matrix[n-i-1][n-j-1]=matrix[j][n-i-1]matrix[j][n-i-1]=temp2.全子集：答案：使用回溯法，遍历所有可能的子集。pythondefsubsets(nums):result=[]subset=[]defbacktrack(index):result.append(subset.copy())foriinrange(index,len(nums)):subset.append(nums[i])backtrack(i+1)subset.pop()backtrack(0)returnresult3.最大不连续子序列和：答案：动态规划，`dp[i]`表示以`nums[i]`结尾的最大不连续子序列和。pythondefmaxNonContiguousSubarraySum(nums):ifnotnums:return0dp=[0]len(nums)dp[0]=nums[0]foriinrange(1,len(nums)):dp[i]=max(dp[i-1],nums[i]+(dp[i-2]ifi>=2else0))returndp[-1]五、贪心算法题1.硬币组合数：答案：排序后，从大到小贪心选择硬币。pythondefcoinChange(coins,amount):coins.sort(reverse=True)count=0forcoinincoins:ifamount==0:breaknum=amount//coincount+=numamount-=numcoinreturncountifamount==0else-12.接雨水：答案：使用双指针法，分别从左和从右遍历，记录左右两侧的最高水位。pythondeftrap(height):ifnotheight:return0left,right=0,len(height)-1left_max,right_max=height[left],height[right]result=0whileleft<right:ifheight[left]<height[right]:left+=1left_max=max(left_max,height[left])result+=left_max-height[left]else:right-=1right_max=max(right_max,height[right])result+=right_max-height[right]returnresult六、字符串处理题1.有效括号：答案：使用栈，遍历字符串，遇到左括号入栈，遇到右括号弹出并判断是否匹配。pythondefisValid(s):stack=[]mapping={')':'(','}':'{',']':'['}forcharins:ifcharinm