华为面试机试题目及参考答案一览

华为面试机试经典题目及参考答案一览考试时间：______分钟总分：______分姓名：______第一题请编写一个函数，该函数接收一个字符串`s`作为输入，并返回一个新的字符串，其中`s`中所有大写字母都被转换成对应的小写字母，所有小写字母都被转换成对应的大写字母，其他字符保持不变。例如，输入`"HelloWorld!"`，输出`"hELLOwORLD!"`。第二题给定一个非空整数数组`nums`，请编写一个函数，找出该数组中和为零的三元组。三元组`(nums[i],nums[j],nums[k])`需要满足`i!=j`,`i!=k`,`j!=k`，且`nums[i]+nums[j]+nums[k]==0`。你可以假设每个输入都只有一个解，并且你不能重复使用相同的元素。例如，输入`[-1,0,1,2]`，输出`[-1,0,1]`和`[(-1,2,1)]`（输出顺序不重要）。第三题请实现一个`MyStack`类，以模拟栈的行为。栈应该支持以下操作：*`push(x)`：将元素`x`压入栈中。*`pop()`：弹出栈顶元素。*`top()`：获取栈顶元素，但不在栈中移除它。*`empty()`：检查栈是否为空。只能使用队列`queue`来实现这个栈。队列的常用方法包括`push()`、`pop()`、`peek()`或`front()`（获取队首元素）、`empty()`或`is_empty()`（检查队列是否为空）、`size()`（获取队列大小，根据需要可能用不到）。第四题给定两个字符串`s`和`t`，请判断`t`是否为`s`的字母异位词。字母异位词是指由相同字母重新排列组合而成的单词，字母的顺序可以不同。例如，输入`s="anagram"`,`t="nagaram"`，输出`true`；输入`s="rat"`,`t="car"`，输出`false`。第五题请编写一个函数，该函数接收一个链表的头节点`head`和一个整数`val`作为输入，并返回删除链表中所有等于`val`的节点的后的链表的头节点。链表节点的定义如下：```pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=next```例如，输入链表`[1->2->6->3->4->5->6]`和`val=6`，输出`[1->2->3->4->5]`。第六题给定一个包含`n`个整数的数组`nums`，判断该数组是否可以划分为至少`k`个连续的整数序列。每个序列至少包含一个数字。例如，输入`nums=[1,2,3,3,4,5]`,`k=3`，输出`true`；输入`nums=[1,2,3,3,4,4,5,6]`,`k=3`，输出`false`。第七题请编写一个函数，找出所有相加和为特定目标数`target`的不同三元组。三元组`(nums[i],nums[j],nums[k])`需要满足`i<j<k`，且`nums[i]+nums[j]+nums[k]==target`。你可以假设每个输入都只有一组解。例如，输入`nums=[3,2,4,1]`,`target=7`，输出`[[1,2,4]]`。第八题请编写一个函数，实现二叉树的深度优先遍历（前序遍历）。可以使用递归或迭代的方式实现。二叉树节点的定义如下：```pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=right```例如，给定二叉树`[3,9,20,null,null,15,7]`，前序遍历的结果应为`[3,9,20,15,7]`。第九题给定一个非负整数`n`，请编写一个函数，计算`n`的不同二进制表示中`1`的个数。例如，输入`n=5`，输出`2`（二进制表示为`101`，有两个`1`）；输入`n=0`，输出`0`。第十题请编写一个函数，找出数组中重复次数超过`n/2`的元素。假设数组中一定存在这样的元素。例如，输入`nums=[2,2,1,1,1,2,2]`，输出`2`。试卷答案第一题解析思路：第一题答案：```pythondefswap_case(s:str)->str:return''.join([char.lower()ifchar.isupper()elsechar.upper()ifchar.islower()elsecharforcharins])```第二题解析思路：可以使用排序加双指针的方法。首先对数组进行排序，然后固定一个数`nums[i]`，使用两个指针`left`和`right`分别指向`i+1`和数组末尾。计算`nums[i]+nums[left]+nums[right]`的和：*如果和等于零，记录下这个三元组，并将`left`和`right`都向内移动，同时跳过重复元素。*如果和小于零，说明需要更大的数，将`left`向右移动。*如果和大于零，说明需要更小的数，将`right`向左移动。重复这个过程直到`left`大于或等于`right`。遍历完所有可能的`i`即可。第二题答案：```pythondefthreeSum(nums):nums.sort()result=[]n=len(nums)foriinrange(n-2):ifi>0andnums[i]==nums[i-1]:continueleft,right=i+1,n-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```第三题解析思路：使用两个队列`q1`和`q2`来实现。`push(x)`操作：将元素`x`先放入`q2`，然后将`q1`中的所有元素依次取出放入`q2`。这样`q2`中就有`x`和`q1`中原来的所有元素，然后交换`q1`和`q2`的名字。`pop()`操作：直接从`q1`的队首弹出元素。`top()`操作：返回`q1`队首的元素但不弹出。`empty()`操作：检查`q1`是否为空。这种实现方式利用了队列先进先出的特性，通过两次队列操作模拟出栈的LIFO行为。第三题答案：```pythonfromcollectionsimportdequeclassMyStack:def__init__(self):self.q1=deque()self.q2=deque()defpush(self,x:int)->None:self.q2.append(x)whileself.q1:self.q2.append(self.q1.popleft())self.q1,self.q2=self.q2,self.q1defpop(self)->int:ifself.q1:returnself.q1.popleft()returnNone#Orraiseexceptionifstackisemptydeftop(self)->int:ifself.q1:returnself.q1[0]returnNone#Orraiseexceptionifstackisemptydefempty(self)->bool:returnnotself.q1```第四题解析思路：首先检查两个字符串的长度是否相同，如果不同则直接返回`false`。然后创建一个长度为26的数组（假设只含小写字母）或使用字典来统计`s`中每个字母的出现次数，同时遍历`t`，每遇到一个字母就将其在统计结构中的计数减一。最后检查统计结构中的所有计数是否都为零。如果都为零，则`t`是`s`的字母异位词。第四题答案：```pythondefisAnagram(s:str,t:str)->bool:iflen(s)!=len(t):returnFalsecount=[0]*26forcharins:count[ord(char)-ord('a')]+=1forcharint:count[ord(char)-ord('a')]-=1returnall(x==0forxincount)```第五题解析思路：使用虚拟头节点（dummyhead）可以简化边界条件的处理。创建一个虚拟头节点`dummy`，并使其`next`指向`head`。使用一个指针`prev`指向`dummy`，初始化`current`指向`head`。遍历链表，在遍历过程中，如果发现`current.val==val`，则将`prev.next`指向`current.next`，跳过当前节点`current`。否则，将`prev`向后移动一步，`current`也向后移动一步。遍历结束后，返回`dummy.next`作为新链表的头节点。第五题答案：```pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefremoveElements(head:ListNode,val:int)->ListNode:dummy=ListNode(0)dummy.next=headprev=dummycurrent=headwhilecurrent:ifcurrent.val==val:prev.next=current.nextcurrent=current.nextelse:prev=prev.nextcurrent=current.nextreturndummy.next```第六题解析思路：首先对数组进行排序。然后使用滑动窗口的方法，窗口大小为`k`。初始化两个指针`start`和`end`，都指向数组的开始。检查`end-start+1`是否等于`k`：*如果等于`k`，则检查窗口内的所有数是否是连续的整数（即`nums[end]-nums[start]==k-1`）。如果是，则找到了一个有效的序列，返回`true`。*如果不等于`k`，则移动`end`指针，扩大窗口。如果遍历完数组后没有找到满足条件的`k`个连续序列，则返回`false`。第六题答案：```pythondefisPossibleDivide(nums,k):iflen(nums)%k!=0:returnFalsenums.sort()count={}fornuminnums:count[num]=count.get(num,0)+1start=nums[0]required=kwhilerequired>0:end=startwhileendnotincountorcount[end]==0:end+=1ifend-start!=k-1:returnFalseforiinrange(start,end+1):ifcount[i]==0:returnFalsecount[i]-=1ifcount[i]==0andi!=end:start=i+1required-=1returnTrue```第七题解析思路：可以看作是第二题的变种，但需要保持元素的顺序`i<j<k`。可以先对数组进行排序。然后固定一个数`nums[i]`，使用两个指针`left`和`right`分别指向`i+1`和数组末尾。计算`nums[i]+nums[left]+nums[right]`的和：*如果和等于`target`，记录下这个三元组`[nums[i],nums[left],nums[right]]`，并将`left`和`right`都向内移动，同时跳过重复元素。*如果和小于`target`，说明需要更大的数，将`left`向右移动。*如果和大于`target`，说明需要更小的数，将`right`向左移动。重复这个过程直到`left`大于或等于`right`。遍历完所有可能的`i`即可。由于数组已排序，可以确保找到的三元组是唯一的。第七题答案：```pythondefthreeSumClosest(nums,target):nums.sort()n=len(nums)closest_sum=float('inf')foriinrange(n-2):ifi>0andnums[i]==nums[i-1]:continueleft,right=i+1,n-1whileleft<right:total=nums[i]+nums[left]+nums[right]ifabs(total-target)<abs(closest_sum-target):closest_sum=totaliftotal<target:left+=1eliftotal>target:right-=1else:returntotalreturnclosest_sum```第八题解析思路：递归方法：定义一个辅助函数`dfs(node)`，如果当前节点`node`为空，返回。否则，先访问当前节点（添加到结果中），然后递归地前序遍历左子树`node.left`，最后递归地前序遍历右子树`node.right`。迭代方法（使用栈）：初始化一个空栈`stack`，将根节点`root`入栈。当栈不为空时，弹出栈顶节点`node`，访问它（添加到结果中），然后先将其右子节点`node.right`入栈（如果存在），再将其左子节点`node.left`入栈（如果存在）。因为栈是后进先出结构，所以先入栈的右子节点会被后弹出，符合前序遍历的顺序（根-左-右）。第八题答案（递归）：```pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefpreorderTraversal(root:TreeNode)->List[int]:result=[]defdfs(node):i