大学ACM考试题目及作业答案

大学ACM考试题目及作业答案整理题目1：最大子数组和（Kadane算法应用）题目描述给定一个整数数组nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例输入:[2,1,3,4,1,2,1,5,4]输出:6解释:连续子数组[4,1,2,1]的和最大，为6。解题思路可以使用Kadane算法来解决这个问题。该算法的核心思想是在遍历数组的过程中，维护一个当前的最大子数组和以及一个全局的最大子数组和。对于数组中的每个元素，我们有两种选择：要么将其加入当前的子数组，要么以该元素作为新的子数组的起始。代码实现（Python）```pythondefmaxSubArray(nums):ifnotnums:return0current_sum=nums[0]max_sum=nums[0]foriinrange(1,len(nums)):current_sum=max(nums[i],current_sum+nums[i])max_sum=max(max_sum,current_sum)returnmax_sumnums=[2,1,3,4,1,2,1,5,4]print(maxSubArray(nums))```复杂度分析时间复杂度：$O(n)$，其中$n$是数组的长度。因为只需要遍历数组一次。空间复杂度：$O(1)$，只使用了常数级的额外空间。题目2：有效的括号题目描述给定一个只包括'('，')'，'{'，'}'，'['，']'的字符串，判断字符串是否有效。有效字符串需满足：1.左括号必须用相同类型的右括号闭合。2.左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。示例输入:"()"输出:true输入:"()[]{}"输出:true输入:"(]"输出:false解题思路可以使用栈来解决这个问题。遍历字符串，遇到左括号就将其压入栈中，遇到右括号就从栈中弹出一个左括号进行匹配。如果匹配成功，则继续遍历；如果匹配失败或者栈为空，则返回false。遍历结束后，如果栈为空，则说明所有括号都匹配成功，返回true。代码实现（Python）```pythondefisValid(s):stack=[]mapping={")":"(","}":"{","]":"["}forcharins:ifcharinmapping:top_element=stack.pop()ifstackelse''ifmapping[char]!=top_element:returnFalseelse:stack.append(char)returnnotstacks="()[]{}"print(isValid(s))```复杂度分析时间复杂度：$O(n)$，其中$n$是字符串的长度。因为只需要遍历字符串一次。空间复杂度：$O(n)$，在最坏情况下，栈需要存储所有的左括号。题目3：合并两个有序链表题目描述将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例输入：1>2>4,1>3>4输出：1>1>2>3>4>4解题思路可以使用递归或者迭代的方法来解决这个问题。递归的思路是比较两个链表的头节点，选择较小的节点作为新链表的头节点，然后递归地合并剩余的节点。迭代的思路是使用一个哨兵节点来简化边界条件，然后遍历两个链表，将较小的节点依次添加到新链表中。代码实现（Python，迭代方法）```pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefmergeTwoLists(l1,l2):dummy=ListNode(0)current=dummywhilel1andl2:ifl1.val<l2.val:current.next=l1l1=l1.nextelse:current.next=l2l2=l2.nextcurrent=current.nextcurrent.next=l1ifl1elsel2returndummy.next创建链表1>2>4l1=ListNode(1)l1.next=ListNode(2)l1.next.next=ListNode(4)创建链表1>3>4l2=ListNode(1)l2.next=ListNode(3)l2.next.next=ListNode(4)merged=mergeTwoLists(l1,l2)whilemerged:print(merged.val,end=">")merged=merged.next```复杂度分析时间复杂度：$O(m+n)$，其中$m$和$n$分别是两个链表的长度。因为需要遍历两个链表一次。空间复杂度：$O(1)$，只使用了常数级的额外空间。题目4：二叉树的中序遍历题目描述给定一个二叉树，返回它的中序遍历。示例输入:[1,null,2,3]1\2/3输出:[1,3,2]解题思路中序遍历的顺序是左子树>根节点>右子树。可以使用递归或者迭代的方法来实现。递归方法比较简单，直接按照中序遍历的顺序递归遍历左子树、访问根节点、递归遍历右子树。迭代方法需要使用栈来模拟递归的过程。代码实现（Python，迭代方法）```pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefinorderTraversal(root):result=[]stack=[]current=rootwhilecurrentorstack:whilecurrent:stack.append(current)current=current.leftcurrent=stack.pop()result.append(current.val)current=current.rightreturnresult创建二叉树root=TreeNode(1)root.right=TreeNode(2)root.right.left=TreeNode(3)print(inorderTraversal(root))```复杂度分析时间复杂度：$O(n)$，其中$n$是二叉树的节点数。因为需要遍历每个节点一次。空间复杂度：$O(n)$，在最坏情况下，栈需要存储所有的节点。题目5：爬楼梯题目描述假设你正在爬楼梯。需要$n$阶你才能到达楼顶。每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定$n$是一个正整数。示例输入：2输出：2解释：有两种方法可以爬到楼顶。1.1阶+1阶2.2阶输入：3输出：3解释：有三种方法可以爬到楼顶。1.1阶+1阶+1阶2.1阶+2阶3.2阶+1阶解题思路这是一个经典的动态规划问题。设$f(n)$表示爬到第$n$阶楼梯的方法数。因为每次可以爬1或2个台阶，所以$f(n)=f(n1)+f(n2)$，其中$f(1)=1$，$f(2)=2$。代码实现（Python）```pythondefclimbStairs(n):ifn==1:return1first=1second=2foriinrange(3,n+1):third=first+secondfirst=secondsecond=thirdreturnsecondn=3print(climbStairs(n))```复杂度分析时间复杂度：$O(n)$，因为只需要遍历一次。空间复杂度：$O(1)$，只使用了常数级的额外空间。题目6：两数之和题目描述给定一个整数数组nums和一个目标值target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。示例给定nums=[2,7,11,15],target=9因为nums[0]+nums[1]=2+7=9所以返回[0,1]解题思路可以使用哈希表来解决这个问题。遍历数组，对于每个元素$x$，检查$targetx$是否在哈希表中。如果存在，则返回$targetx$的下标和当前元素的下标；如果不存在，则将当前元素和其下标存入哈希表中。代码实现（Python）```pythondeftwoSum(nums,target):hashmap={}fori,numinenumerate(nums):complement=targetnumifcomplementinhashmap:return[hashmap[complement],i]hashmap[num]=inums=[2,7,11,15]target=9print(twoSum(nums,target))```复杂度分析时间复杂度：$O(n)$，其中$n$是数组的长度。因为只需要遍历数组一次。空间复杂度：$O(n)$，在最坏情况下，哈希表需要存储所有的元素。题目7：数组中的第K个最大元素题目描述在未排序的数组中找到第$k$个最大的元素。请注意，你需要找的是数组排序后的第$k$个最大的元素，而不是第$k$个不同的元素。示例输入:[3,2,1,5,6,4]和k=2输出:5解题思路可以使用快速选择算法来解决这个问题。快速选择算法是基于快速排序的思想，通过每次选择一个基准元素，将数组分为两部分，使得左边的元素都小于等于基准元素，右边的元素都大于等于基准元素。然后根据基准元素的位置与$k$的关系，决定在左边还是右边继续查找。代码实现（Python）```pythonimportrandomdeffindKthLargest(nums,k):defpartition(left,right,pivot_index):pivot=nums[pivot_index]nums[pivot_index],nums[right]=nums[right],nums[pivot_index]store_index=leftforiinrange(left,right):ifnums[i]<pivot:nums[store_index],nums[i]=nums[i],nums[store_index]store_index+=1nums[right],nums[store_index]=nums[store_index],nums[right]returnstore_indexdefselect(left,right,k_smallest):ifleft==right:returnnums[left]pivot_index=random.randint(left,right)pivot_index=partition(left,right,pivot_index)ifk_smallest==pivot_index:returnnums[k_smallest]elifk_smallest<pivot_index:returnselect(left,pivot_index1,k_smallest)else:returnselect(pivot_index+1,right,k_smallest)returnselect(0,len(nums)1,len(nums)k)nums=[3,2,1,5,6,4]k=2print(findKthLargest(nums,k))```复杂度分析时间复杂度：平均情况下为$O(n)$，最坏情况下为$O(n^2)$。空间复杂度：$O(1)$，只使用了常数级的额外空间。题目8：无重复字符的最长子串题目描述给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。示例输入:"abcabcbb"输出:3解释:因为无重复字符的最长子串是"abc"，所以其长度为3。解题思路可以使用滑动窗口的方法来解决这个问题。使用两个指针$left$和$right$表示滑动窗口的左右边界，使用一个哈希表来记录每个字符最后出现的位置。遍历字符串，当遇到重复字符时，将左指针移动到重复字符最后出现位置的下一个位置，同时更新哈希表。在遍历过程中，记录最长子串的长度。代码实现（Python）```pythondeflengthOfLongestSubstring(s):char_index_map={}left=0max_length=0forright,charinenumerate(s):ifcharinchar_index_mapandchar_index_map[char]>=left:left=char_index_map[char]+1char_index_map[char]=rightmax_length=max(max_length,rightleft+1)returnmax_lengths="abcabcbb"print(lengthOfLongestSubstring(s))```复杂度分析时间复杂度：$O(n)$，其中$n$是字符串的长度。因为只需要遍历字符串一次。空间复杂度：$O(k)$，其中$k$是字符集的大小。在本题中，字符集为ASCII字符集，$k$为128。题目9：排序链表题目描述在$O(nlogn)$时间复杂度和常数级空间复杂度下，对链表进行排序。示例输入:4>2>1>3输出:1>2>3>4解题思路可以使用归并排序来对链表进行排序。归并排序的时间复杂度为$O(nlogn)$，并且可以在常数级空间复杂度下实现。具体步骤如下：1.使用快慢指针找到链表的中点，将链表分为两部分。2.递归地对左右两部分链表进行排序。3.合并两个有序链表。代码实现（Python）```pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefsortList(head):ifnotheadornothead.next:returnheadslow=headfast=head.nextwhilefastandfast.next:slow=slow.nextfast=fast.next.nextmid=slow.nextslow.next=Noneleft=sortList(head)right=sortList(mid)returnmerge(left,right)defmerge(l1,l2):dummy=ListNode(0)current=dummywhilel1andl2:ifl1.val<l2.val:current.next=l1l1=l1.nextelse:current.next=l2l2=l2.nextcurrent=current.nextcurrent.next=l1ifl1elsel2returndummy.next创建链表head=ListNode(4)head.next=ListNode(2)head.next.next=ListNode(1)head.next.next.next=ListNode(3)sorted_head=sortList(head)whilesorted_head:print(sorted_head.val,end=">")sorted_head=sorted_head.next```复杂度分析时间复杂度：$O(nlogn)$，其中$n$是链表的长度。因为归并排序的时间复杂度为$O(nlogn)$。空间复杂度：$O(logn)$，主要是递归调用栈的空间。题目10：单词搜索题目描述给定一个二维网格和一个单词，找出该单词是否存在于网格中。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。示例board=[['A','B','C','E'],['S','F','C','S'],['A','D','E','E']]给定word="ABCCED",返回true给定word="SEE",返回true给定word="ABCB",返回false解题思路可以使用深度优先搜索（DFS）来解决这个问题。从网格的每个单元格开始，尝试匹配单词的第一个字符。如果匹配成功，则递归地在相邻的单元格中继续匹配单词的下一个字符。在递归过程中，需要标记已经访问过的单元格，避免重复使用。代码实现（Python）```pythondefexist(board,word):rows,cols=len(board),len(board[0])