算法面试高频题目与标准答案

算法面试高频题目与标准答案考试时间：______分钟总分：______分姓名：______第一题请编写一个函数，该函数接收一个非空字符串`s`，并返回一个新字符串，其中每个字符在`s`中出现的次数都是唯一的。如果无法满足条件，请返回一个空字符串。例如，输入"ccbbba"应返回"ccbbba"，输入"abab"应返回""，输入"aab"应返回"aab"。第二题给定一个整数数组`nums`和一个整数`k`，请设计一个算法，找到`nums`中最长的子数组，该子数组的和恰好为`k`。你需要返回这个子数组的长度。如果不存在这样的子数组，返回0。例如，输入`nums=[1,-1,5,-2,3]`,`k=3`，应返回4，因为子数组`[1,-1,5,-2]`的和为3。第三题请实现一个`MyStack`类，以模拟栈（栈）的行为。栈应该支持以下操作：*`push(x)`：将元素`x`压入栈顶。*`pop()`：弹出栈顶元素。*`top()`：获取栈顶元素。*`empty()`：检查栈是否为空。你可以使用几个栈来实现这个`MyStack`，也可以使用一个栈加上一个辅助数据结构。你需要提供你的实现代码。第四题给定一个二叉树，其中每个节点的值是唯一的，请设计一个算法来找出从根节点到叶子节点的所有路径，且这些路径上的节点值之和等于给定的目标和`sum`。例如，给定如下二叉树和目标和`sum=22`：```5/\48/\134/\\5117/\72```应返回所有路径，例如`[[5,4,11,2],[5,8,4,5]]`。第五题请编写一个函数，输入是一个非负整数`n`，返回`1`到`n`中所有整数的乘积之积（即`n!`），但结果需要对`10^9+7`取模。例如，输入`n=10`，输出`3628800`。第六题给定一个整数数组`nums`，其中可能包含重复元素，请找出数组中的所有唯一重复元素（即出现次数超过一次的元素），并按升序排列返回。例如，输入`nums=[4,3,2,7,8,2,3,1]`，应返回`[2,3]`。第七题请实现一个算法，在不使用额外空间的情况下，将一个给定数组中的所有0移动到数组的末尾，同时保持非零元素的相对顺序。例如，输入`nums=[0,1,0,3,12]`，输出`[1,3,12,0,0]`。第八题给定一个包含`n`个整数的数组`nums`，其中`n`是偶数，请设计一个算法将数组分成`n/2`对，使得每对的两个元素之和等于给定的值`target`。你需要返回所有可能的配对方案的数量。例如，输入`nums=[1,2,3,4,5,6]`,`target=7`，应返回4，因为有以下四种有效的配对：`(1,6)`,`(2,5)`,`(3,4)`,`(1,6)`（顺序不同视为不同配对）。第九题请编写一个函数，输入是一个字符串`s`，返回`s`中不同字母的反转字符串。例如，输入`s="aabbcc"`，输出`"ccbbaa"`。第十题给定一个二叉搜索树（BST），其中每个节点的值是唯一的，请设计一个算法来删除一个给定值`key`的节点，并返回删除节点后的二叉搜索树。保证删除后二叉搜索树仍然满足BST的性质。你需要提供你的实现代码。试卷答案第一题解析思路：使用哈希表统计每个字符的出现次数。然后遍历字符串，对于每个字符，检查其出现次数是否与前面已处理字符的出现次数不同。如果不同，则保留该字符；如果相同，则跳过该字符。最后将保留的字符拼接成新字符串返回。如果所有字符的出现次数都相同（除了可能的唯一一个），则返回空字符串。第一题答案：```pythondefuniqueOccurrences(s:str)->str:count_map={}forcharins:count_map[char]=count_map.get(char,0)+1freq_map={}forcountincount_map.values():ifcountinfreq_map:return""freq_map[count]=Trueresult=[]forcharins:ifcount_map[char]infreq_map:result.append(char)return''.join(result)```第二题解析思路：使用哈希表（前缀和映射）来存储前缀和到其首次出现索引的映射。初始化哈希表为`{0:-1}`，表示前缀和为0时索引为-1。遍历数组，计算当前前缀和`prefix_sum`。检查`prefix_sum-k`是否在哈希表中：*如果在，说明从`hash[prefix_sum-k]+1`到当前索引`i`的子数组和为`k`，更新最大长度。*如果不在，将当前前缀和`prefix_sum`及其索引`i`加入哈希表。继续遍历。第二题答案：```pythondefsubarraySum(nums,k):prefix_sum_map={0:-1}prefix_sum=0max_len=0fori,numinenumerate(nums):prefix_sum+=numif(prefix_sum-k)inprefix_sum_map:start_index=prefix_sum_map[prefix_sum-k]+1max_len=max(max_len,i-start_index+1)ifprefix_sumnotinprefix_sum_map:prefix_sum_map[prefix_sum]=ireturnmax_len```第三题解析思路：使用一个栈`stack`来实现。`push(x)`操作直接将`x`压入`stack`。`pop()`操作弹出`stack`的栈顶元素。`top()`操作返回`stack`的栈顶元素但不弹出。`empty()`操作检查`stack`是否为空。这种实现是最直接的，时间复杂度均为O(1)。第三题答案：```pythonclassMyStack:def__init__(self):self.stack=[]defpush(self,x:int)->None:self.stack.append(x)defpop(self)->int:ifself.empty():raiseIndexError("Popfromemptystack")returnself.stack.pop()deftop(self)->int:ifself.empty():raiseIndexError("Topfromemptystack")returnself.stack[-1]defempty(self)->bool:returnlen(self.stack)==0```第四题解析思路：采用深度优先搜索（DFS）或递归方法遍历二叉树。从根节点开始，沿着路径累加节点值。当访问到叶子节点时，检查当前路径上节点值的和是否等于目标和`sum`。如果等于，则将当前路径复制并加入结果列表。在遍历过程中，需要考虑左右子树。第四题答案：```python#Definitionforabinarytreenode.#classTreeNode:#def__init__(self,val=0,left=None,right=None):#self.val=val#self.left=left#self.right=rightclassSolution:defpathSum(self,root:TreeNode,sum:int)->List[List[int]]:result=[]path=[]defdfs(node,current_sum):ifnotnode:returncurrent_sum+=node.valpath.append(node.val)ifnotnode.leftandnotnode.right:#Checkifleafifcurrent_sum==sum:result.append(path.copy())else:ifnode.left:dfs(node.left,current_sum)ifnode.right:dfs(node.right,current_sum)path.pop()#Backtrackdfs(root,0)returnresult```第五题解析思路：计算阶乘`n!`。由于`n!`很快会变得非常大，需要对`10^9+7`取模。可以在每次乘法操作后立即取模，以防止整数溢出。实现一个简单的循环从1乘到`n`，每次乘法结果都对`10^9+7`取模。第五题答案：```pythondefmultiplyNumbers(n:int)->int:MOD=109+7result=1foriinrange(1,n+1):result=(result*i)%MODreturnresult```第六题解析思路：首先对数组进行排序。排序后，重复元素会相邻出现。然后遍历排序后的数组，比较当前元素与前一个元素。如果相同，则将其加入结果列表（如果之前未加入过）。为了确保唯一性，使用一个变量`last_added`记录上次加入结果列表的重复元素值，避免重复加入。最后对结果列表进行排序（虽然已经排序，但逻辑上需要）。第六题答案：```pythondeffindDuplicates(nums):nums.sort()result=[]last_added=Noneforiinrange(1,len(nums)):ifnums[i]==nums[i-1]:ifnums[i]!=last_added:result.append(nums[i])last_added=nums[i]returnresult```第七题解析思路：使用双指针技术。一个指针`last_non_zero`用于追踪下一个非零元素应该放置的位置（初始化为0）。另一个指针`i`遍历数组。当`i`指向的元素不为零时，将其与`last_non_zero`指向的元素交换，并将`last_non_zero`向后移动一位。遍历结束后，所有非零元素都被移到前面，`last_non_zero`之后的元素都设为零。第七题答案：```pythondefmoveZeroes(nums):last_non_zero_found_at=0foriinrange(len(nums)):ifnums[i]!=0:nums[last_non_zero_found_at],nums[i]=nums[i],nums[last_non_zero_found_at]last_non_zero_found_at+=1#Filltheremainderofthearraywithzerosforiinrange(last_non_zero_found_at,len(nums)):nums[i]=0```第八题解析思路：首先对数组进行排序。排序后，可以使用双指针方法寻找配对。初始化两个指针`left`指向数组的第一个元素，`right`指向数组的最后一个元素。计算`nums[left]+nums[right]`：*如果和等于`target`，则找到了一对有效配对，`left`向右移动，`right`向左移动，计数加一。*如果和小于`target`，则`left`向右移动，以增加和。*如果和大于`target`，则`right`向左移动，以减少和。重复上述过程，直到`left`大于或等于`right`。最后返回计数。第八题答案：```pythondefnumRescueBoats(nums,target):nums.sort()left,right=0,len(nums)-1count=0whileleft<=right:ifnums[left]+nums[right]==target:count+=1left+=1right-=1elifnums[left]+nums[right]<target:left+=1else:#nums[left]+nums[right]>targetright-=1returncount```第九题解析思路：将字符串`s`转换为字符数组`chars`。对`chars`数组进行原地反转。然后，使用双指针方法（一个指向开头，一个指向结尾）对字符数组进行反转，使得所有字母字符保持原顺序，非字母字符移到末尾。最后，将字符数组转换回字符串返回。这里的“字母”通常指`[a-zA-Z]`。第九题答案：```pythondefreverseOnlyLetters(s:str)->str:chars=list(s)i,j=0,len(chars)-1defis_letter(c):return('a'<=c<='z')or('A'<=c<='Z')whilei<j:ifnotis_letter(chars[i]):i+=1elifnotis_letter(chars[j]):j-=1else:chars[i],chars[j]=chars[j],chars[i]i+=1j-=1return''.join(chars)```第十题解析思路：分三种情况讨论：1.树为空：返回`None`。2.要删除的节点`node`是根节点：*如果根节点没有右子树，直接返回根节点的左子树作为新树。*如果根节点有右子树，找到右子树中最左边的节点（后继节点），用该节点的值替换根节点的值，然后删除原右子树中的该后继节点。3.要删除的节点`node`不是根节点：*如果`node`是左子节点，调用递归函数删除`node`，并更新左子节点指针。*如果`node`是右子节点，调用递归函数删除`node`，并更新右子节点指针。递归函数需要返回删除节点后的子树根节点。第十题答案：```python#Definitionforabinarytreenode.#classTreeNode:#def__init__(self,val=0,left=None,right=None):#self.val=val#self.left=left#self.right=rightclassSolution:defdeleteNode(self,root:TreeNode,key:int)->TreeNode:ifnotroot:returnNoneifkey<root.val:root.left=self.delet