acm大賽的題目及答案ACM大賽的題目及答案1.題目一：二分查找題目描述：給定一個有序整數(shù)數(shù)組`nums`（升序排列），和一個目標(biāo)值`target`，寫一個函數(shù)來搜索`nums`中的`target`，如果`target`存在返回其索引，否則返回`-1`。輸入：`nums=[1,2,3,4,5]`,`target=3`輸出：`2`答案：```pythondefsearch(nums,target):left,right=0,len(nums)-1whileleft<=right:mid=(left+right)//2ifnums[mid]==target:returnmidelifnums[mid]<target:left=mid+1else:right=mid-1return-1```2.題目二：兩數(shù)之和題目描述：給定一個整數(shù)數(shù)組`nums`和一個目標(biāo)值`target`，請你在該數(shù)組中找出和為目標(biāo)值的那兩個整數(shù)，并返回他們的數(shù)組下標(biāo)。輸入：`nums=[2,7,11,15]`,`target=9`輸出：`[0,1]`答案：```pythondeftwoSum(nums,target):hashmap={}fori,numinenumerate(nums):iftarget-numinhashmap:return[hashmap[target-num],i]hashmap[num]=ireturn[]```3.題目三：無重復(fù)字符的最長子串題目描述：給定一個字符串，請你找出其中不含有重復(fù)字符的最長子串的長度。輸入：`s="abcabcbb"`輸出：`3`答案：```pythondeflengthOfLongestSubstring(s):char_set=set()left=max_length=0forrightinrange(len(s)):whiles[right]inchar_set:char_set.remove(s[left])left+=1char_set.add(s[right])max_length=max(max_length,right-left+1)returnmax_length```4.題目四：螺旋矩陣題目描述：給定一個包含`mxn`個元素的矩陣（`m`行，`n`列），按照順時針螺旋順序，返回矩陣中的所有元素。輸入：`matrix=[[1,2,3],[4,5,6],[7,8,9]]`輸出：`[1,2,3,6,9,8,7,4,5]`答案：```pythondefspiralOrder(matrix):ifnotmatrix:return[]result=[]whilematrix:result+=matrix.pop(0)ifmatrixandmatrix[0]:forrowinmatrix:result.append(row.pop())ifmatrix:result+=matrix.pop()[::-1]ifmatrixandmatrix[0]:forrowinmatrix[::-1]:result.append(row.pop(0))returnresult```5.題目五：合并兩個有序鏈表題目描述：將兩個升序鏈表合并為一個新的升序鏈表并返回。新鏈表值為兩個鏈表的節(jié)點值。輸入：`l1=[1,2,4]`,`l2=[1,3,4]`輸出：`[1,1,2,3,4,4]`答案：```pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefmergeTwoLists(l1,l2):prehead=ListNode(0)prev=preheadwhilel1andl2:ifl1.val<l2.val:prev.next=l1l1=l1.nextelse:prev.next=l2l2=l2.nextprev=prev.nextprev.next=l1orl2returnprehead.next```6.題目六：有效的括號題目描述：給定一個只包括`'('`,`')'`,`'{'`,`'}'`,`'['`,`']'`的字符串`s`，判斷字符串是否有效。輸入：`s="()"`輸出：`True`答案：```pythondefisValid(s):stack=[]brackets={')':'(','}':'{',']':'['}forcharins:ifcharinbrackets.values():stack.append(char)elifcharinbrackets:ifnotstackorstack.pop()!=brackets[char]:returnFalsereturnnotstack```7.題目七：尋找旋轉(zhuǎn)排序數(shù)組中的最小值題目描述：假設(shè)按照升序排序的數(shù)組在預(yù)先未知的某個點上進(jìn)行了旋轉(zhuǎn)（例如，數(shù)組`0124567`可能變?yōu)閌4567012`）。請找出其中最小的元素。輸入：`nums=[4,5,6,7,0,1,2]`輸出：`0`答案：```pythondeffindMin(nums):left,right=0,len(nums)-1whileleft<right:mid=(left+right)//2ifnums[mid]>nums[right]:left=mid+1else:right=midreturnnums[left]```8.題目八：字符串的排列題目描述：給定兩個字符串`s1`和`s2`，寫一個函數(shù)來判斷`s2`是否包含`s1`的排列。輸入：`s1="ab"`,`s2="eidbaooo"`輸出：`True`答案：```pythondefcheckInclusion(s1,s2):iflen(s1)>len(s2):returnFalsecount1,count2=[0]256,[0]256forcharins1:count1[ord(char)]+=1foriinrange(len(s1)):count2[ord(s2[i])]+=1foriinrange(len(s1),len(s2)):ifcount1==count2:return