荣耀机试题目及答案完整呈现

荣耀机试题目及答案完整呈现考试时间：______分钟总分：______分姓名：______第一题给定一个非空整数数组`nums`，返回其中存在重复元素的最短子数组的长度。如果数组中不存在重复元素，返回0。子数组`nums[i..j]`的长度是`j-i+1`。你可以假设数组的大小不超过10^4。第二题实现一个`MyStack`类来模拟栈。你的`MyStack`类需要支持以下方法：*`push(intx)`:将元素x压入栈顶。*`pop()`:移除栈顶元素并返回该元素。*`top()`:返回栈顶元素。*`empty()`:返回栈是否为空。你可以使用其他栈来辅助实现这个栈。第三题给定一个字符串`s`，找到最长的不包含重复字符的子串的长度。你可以假设`s`只包含字母表中的小写字母。第四题给定一个正整数`n`，生成一个包含1到`n`^2所有元素，按顺时针螺旋顺序填充的`nxn`的二维矩阵。第五题给定一个正整数`n`，判断它是不是2的幂。一个正整数`n`是2的幂，当且仅当它在二进制表示中只有一位是1。第六题设计一个算法，找出数组中未排序的最大子数组，并返回其起始和结束索引。最大子数组是指所有元素都严格递增的子数组。例如，在数组`[1,2,-1,3,5,4,7,2,3]`中，最大子数组是`[1,2,3,5,7]`，起始索引为0，结束索引为6。第七题给定一个非空字符串`s`和一个包含非空单词列表的字符串数组`wordDict`，判断`s`是否可以被`wordDict`中的单词按顺序拼接而成。你可以假设`wordDict`中的所有单词都是不同的。字符串`s`可以分割为一些（可以重复）`wordDict`中的单词的连接。例如，给定`s="catsanddog"`，`wordDict=["cat","cats","and","sand","dog"]`，则返回`true`，因为`"catsanddog"`可以分割为`"cats"`+`"and"`+`"dog"`。第八题给定一个非空整数数组`nums`，返回一个数组`product`，其中`product[i]`是`nums`中除了`nums[i]`之外所有其他元素的乘积。你可以假设数组大小不超过10。你不能使用除法。第九题给定一个链表的头节点`head`，判断链表是否是一个回文链表。你可以假设链表的大小不超过10^4。你可以设计一个O(n)时间复杂度和O(1)空间复杂度的算法吗？第十题给定一个正整数`n`，返回`n`的幂次方展开形式的所有数字。例如，给定`n=123`，返回`[1,2,3]`。如果`n`为0，返回`[0]`。你可以假设`0<=n<=1000`。试卷答案第一题解析思路：使用滑动窗口的思想。初始化两个指针left和right表示窗口的左右边界，以及一个哈希集合记录窗口中出现的元素。右指针遍历数组，对于每个元素nums[right]，如果它已经在哈希集合中，则窗口内存在重复，更新最短长度并移动左指针缩小窗口，直到窗口内不再包含nums[right]。如果不在哈希集合中，则将其加入集合，并继续移动右指针。遍历结束后，如果找到重复元素，返回记录的最短长度，否则返回0。第一题答案：```pythondefminSubArrayLen(nums,target):n=len(nums)left=0current_sum=0min_len=float('inf')seen={}forrightinrange(n):current_sum+=nums[right]whilecurrent_sum>=target:min_len=min(min_len,right-left+1)current_sum-=nums[left]left+=1ifcurrent_sumnotinseen:seen[current_sum]=rightreturnmin_lenifmin_len!=float('inf')else0```第二题解析思路：可以使用两个栈实现。一个栈`stack`用于正常压入和弹出操作，另一个栈`auxiliary`用于辅助`top`操作。`push(x)`直接将元素压入`stack`，并压入`auxiliary`中保持顺序。`pop()`先从`auxiliary`中弹出顶部元素，然后从`stack`中弹出顶部元素。`top()`返回`auxiliary`的顶部元素。`empty()`判断`stack`是否为空。第二题答案：```pythonclassMyStack:def__init__(self):self.stack=[]self.auxiliary=[]defpush(self,x:int)->None:self.stack.append(x)ifnotself.auxiliaryorself.auxiliary[-1]!=x:self.auxiliary.append(x)defpop(self)->int:ifnotself.auxiliary:returnNoneself.auxiliary.pop()returnself.stack.pop()deftop(self)->int:ifnotself.auxiliary:returnNonereturnself.auxiliary[-1]defempty(self)->bool:returnnotself.stack```第三题解析思路：使用滑动窗口和哈希集合。维护一个哈希集合记录窗口中出现的字符，以及两个指针left和right表示窗口的左右边界。右指针遍历字符串，对于每个字符s[right]，如果它已经在哈希集合中，则移动左指针缩小窗口，直到窗口内不再包含s[right]。如果不在哈希集合中，则将s[right]加入集合，并尝试扩展窗口。在每一步，记录窗口的最大长度。第三题答案：```pythondeflengthOfLongestSubstring(s:str)->int:n=len(s)left=0max_len=0seen={}forrightinrange(n):ifs[right]inseenandseen[s[right]]>=left:left=seen[s[right]]+1seen[s[right]]=rightmax_len=max(max_len,right-left+1)returnmax_len```第四题解析思路：模拟顺时针填充过程。定义四个变量top,bottom,left,right分别表示当前填充的边界。使用一个nxn的二维数组matrix初始化为0。从1开始，按顺序填充，先从左到右填充top行，再从上到下填充right列，再从右到左填充bottom行，最后从下到上填充left列。每填充完一圈，更新相应的边界，直到填充完所有元素。第四题答案：```pythondefgenerateMatrix(n:int):matrix=[[0]*nfor_inrange(n)]num=1top,bottom=0,n-1left,right=0,n-1whiletop<=bottomandleft<=right:forjinrange(left,right+1):matrix[top][j]=numnum+=1top+=1foriinrange(top,bottom+1):matrix[i][right]=numnum+=1right-=1iftop<=bottom:forjinrange(right,left-1,-1):matrix[bottom][j]=numnum+=1bottom-=1ifleft<=right:foriinrange(bottom,top-1,-1):matrix[i][left]=numnum+=1left+=1returnmatrix```第五题解析思路：一个正整数是2的幂，当且仅当它在二进制表示中只有一位是1。可以通过位运算判断：一个数n是2的幂，当且仅当n>0且(n&(n-1))==0。这是因为2的幂在二进制表示中只有一位1，减去1后，这一位1及其右边的所有0都变为1，与原数进行按位与操作结果为0。第五题答案：```pythondefisPowerOfTwo(n:int)->bool:returnn>0and(n&(n-1))==0```第六题解析思路：使用两次遍历。第一次遍历从左到右，记录以每个位置结尾的最长递增子数组的长度`length[i]`。第二次遍历从右到左，记录以每个位置开始的longestincsubarraylength`length_r[i]`。最后，遍历每个位置i，计算`length[i]`和`length_r[i]`的乘积，找出最大的乘积及其对应的起始和结束索引。第六题答案：```pythondeffindUnsortedSubarray(nums):n=len(nums)length=[1]*nforiinrange(1,n):ifnums[i]>nums[i-1]:length[i]=length[i-1]+1max_len=max(length)max_index=length.index(max_len)length_r=[1]*nforiinrange(n-2,-1,-1):ifnums[i]<nums[i+1]:length_r[i]=length_r[i+1]+1min_len=min(length_r)min_index=length_r.index(min_len)returnmin_index,n-min_index-1ifmax_index>=min_indexelse0,max_index```第七题解析思路：使用动态规划。定义一个布尔数组dp，其中dp[i]表示字符串s的前i个字符是否可以被wordDict中的单词拼接而成。初始化dp[0]=True。遍历dp数组，对于每个i，如果dp[i]为True，则尝试将s[j:i]（j从i-1到0）与wordDict中的单词匹配，如果匹配成功且dp[j]为True，则设置dp[i]=True。最后返回dp[len(s)]。第七题答案：```pythondefwordBreak(s:str,wordDict):word_set=set(wordDict)max_len=max(len(word)forwordinword_set)dp=[False]*(len(s)+1)dp[0]=Trueforiinrange(1,len(s)+1):forjinrange(max(0,i-max_len),i):ifdp[j]ands[j:i]inword_set:dp[i]=Truebreakreturndp[len(s)]```第八题解析思路：首先计算所有元素的乘积product。对于每个元素product[i]，它左边的所有元素的乘积为left_product[i]，右边的所有元素的乘积为right_product[i]。则product[i]=left_product[i]*right_product[i]。可以首先计算left_product，然后从右到左计算right_product并更新结果。第八题答案：```pythondefproductExceptSelf(nums):n=len(nums)product=[1]*nleft_product=[1]*nright_product=[1]*nforiinrange(1,n):left_product[i]=left_product[i-1]*nums[i-1]foriinrange(n-2,-1,-1):right_product[i]=right_product[i+1]*nums[i+1]foriinrange(n):product[i]=left_product[i]*right_product[i]returnproduct```第九题解析思路：找到链表的中点，将链表后半部分反转，然后比较前后两半是否相同。可以使用快慢指针找到中点。反转后半部分链表。比较两个链表的每个节点。最后，如果相同，则恢复链表（反转后半部分回来）。第九题答案：```pythonclassListNode:def__init__(self,val=0,next=None):