力扣题库及答案解析

力扣题库及答案解析一、数据结构类题目1.数组与字符串1.1两数之和题目描述：给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。你可以按任意顺序返回答案。示例：```输入：nums=[2,7,11,15],target=9输出：[0,1]解释：因为nums[0]+nums[1]==9，返回[0,1]。```解题思路：最直观的方法是使用双重循环遍历所有可能的两个数的组合，检查它们的和是否等于目标值。这种方法的时间复杂度是O(n²)，空间复杂度是O(1)。更高效的方法是使用哈希表（在Python中是字典）。我们可以在遍历数组的同时，检查当前元素的补数（即目标值减去当前元素）是否已经存在于哈希表中。如果存在，我们就找到了答案；如果不存在，就将当前元素存入哈希表中。这种方法的时间复杂度是O(n)，空间复杂度是O(n)。代码实现：```pythondeftwoSum(nums,target):num_map={}fori,numinenumerate(nums):complement=target-numifcomplementinnum_map:return[num_map[complement],i]num_map[num]=ireturn[]```复杂度分析：-时间复杂度：O(n)，其中n是数组的长度。我们只需要遍历数组一次。-空间复杂度：O(n)，其中n是数组的长度。哈希表最多存储n个元素。1.2盛最多水的容器题目描述：给你n个非负整数a1，a2，...，an，每个数代表坐标中的一个点(i,ai)。在坐标内画n条垂直线，垂直线i的两个端点分别为(i,ai)和(i,0)。找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水。示例：```输入：[1,8,6,2,5,4,8,3,7]输出：49解释：图中垂直线代表输入数组[1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为49。```解题思路：这是一个经典的"双指针"问题。我们可以使用两个指针，一个在数组的开头，一个在数组的末尾。然后，我们计算这两个指针所指向的线与x轴构成的容器能够容纳的水量。接着，我们移动指向较短线的指针，因为移动较长的指针不会增加容器的高度，反而可能会减少宽度，从而减少容量。代码实现：```pythondefmaxArea(height):left,right=0,len(height)-1max_area=0whileleft<right:current_area=min(height[left],height[right])(right-left)max_area=max(max_area,current_area)ifheight[left]<height[right]:left+=1else:right-=1returnmax_area```复杂度分析：-时间复杂度：O(n)，其中n是数组的长度。我们只需要遍历数组一次。-空间复杂度：O(1)，我们只使用了常数个额外空间。1.3最长公共前缀题目描述：编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串""。示例：```输入：strs=["flower","flow","flight"]输出："fl"```解题思路：最直观的方法是纵向扫描。我们取第一个字符串作为基准，然后依次比较其他字符串的对应位置字符是否相同。如果相同，则继续比较下一个位置；如果不同，则返回已经匹配的前缀。代码实现：```pythondeflongestCommonPrefix(strs):ifnotstrs:return""prefix=strs[0]forsinstrs[1:]:whiles[:len(prefix)]!=prefix:prefix=prefix[:-1]ifnotprefix:return""returnprefix```复杂度分析：-时间复杂度：O(S)，其中S是所有字符串中字符数量的总和。-空间复杂度：O(1)，我们只使用了常数个额外空间。1.4有效的字母异位词题目描述：给定两个字符串s和t，编写一个函数来判断t是否是s的字母异位词。注意：你可以假设字符串只包含小写字母。示例：```输入:s="anagram",t="nagaram"输出:true```解题思路：字母异位词是指两个字符串包含相同的字母，但字母的顺序可能不同。我们可以使用哈希表（在Python中是字典）来统计每个字母出现的次数。然后，比较两个字符串的字母计数是否相同。代码实现：```pythondefisAnagram(s,t):iflen(s)!=len(t):returnFalsecount={}forcharins:count[char]=count.get(char,0)+1forcharint:ifcharnotincount:returnFalsecount[char]-=1ifcount[char]==0:delcount[char]returnlen(count)==0```复杂度分析：-时间复杂度：O(n)，其中n是字符串的长度。我们只需要遍历两个字符串各一次。-空间复杂度：O(1)，因为哈希表的大小最多为26（字母表的大小），是常数级别的。2.链表2.1合并两个有序链表题目描述：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例：```输入：1->2->4,1->3->4输出：1->1->2->3->4->4```解题思路：我们可以使用递归或迭代的方法来合并两个有序链表。这里我们介绍迭代的方法。我们创建一个哑节点作为新链表的头部，然后使用两个指针分别遍历两个链表，比较当前节点的值，将较小的节点连接到新链表中，然后移动该指针。当一个链表遍历完后，将另一个链表剩余的部分连接到新链表的末尾。代码实现：```pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefmergeTwoLists(l1,l2):dummy=ListNode()current=dummywhilel1andl2:ifl1.val<l2.val:current.next=l1l1=l1.nextelse:current.next=l2l2=l2.nextcurrent=current.nextcurrent.next=l1ifl1elsel2returndummy.next```复杂度分析：-时间复杂度：O(m+n)，其中m和n分别是两个链表的长度。我们最多需要遍历两个链表的所有节点。-空间复杂度：O(1)，我们只使用了常数个额外空间。2.2环形链表题目描述：给定一个链表，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪next指针再次到达，则链表中存在环。为了表示给定链表中的环，我们使用整数pos来表示链表尾连接到链表中的位置（索引从0开始）。如果pos是-1，则在该链表中没有环。注意：pos不作为参数传递，仅仅是为了标识链表的实际情况。示例：```输入：head=[3,2,0,-4],pos=1输出：true解释：链表中有一个环，其尾部连接到第二个节点。```解题思路：我们可以使用快慢指针的方法来解决环形链表的问题。快指针每次移动两步，慢指针每次移动一步。如果链表中有环，快指针最终会追上慢指针；如果没有环，快指针会先到达链表的末尾。代码实现：```pythondefhasCycle(head):ifnotheadornothead.next:returnFalseslow=headfast=head.nextwhileslow!=fast:ifnotfastornotfast.next:returnFalseslow=slow.nextfast=fast.next.nextreturnTrue```复杂度分析：-时间复杂度：O(n)，其中n是链表的长度。在最坏的情况下，我们需要遍历整个链表。-空间复杂度：O(1)，我们只使用了常数个额外空间。3.栈与队列3.1有效的括号题目描述：给定一个只包括'('，')'，'{'，'}'，'['，']'的字符串，判断字符串是否有效。有效字符串需满足：-左括号必须用相同类型的右括号闭合。-左括号必须以正确的顺序闭合。-每个右括号都有一个对应的相同类型的左括号。示例：```输入："()"输出：true输入："()[]{}"输出：true输入："(]"输出：false```解题思路：我们可以使用栈来解决这个问题。当我们遇到一个左括号时，我们将其压入栈中；当我们遇到一个右括号时，我们检查栈顶的左括号是否与之匹配。如果匹配，则弹出栈顶的左括号；如果不匹配，则返回false。最后，如果栈为空，则说明所有的括号都匹配；否则，说明有未匹配的左括号。代码实现：```pythondefisValid(s):stack=[]mapping={')':'(','}':'{',']':'['}forcharins:ifcharinmapping:top_element=stack.pop()ifstackelse''ifmapping[char]!=top_element:returnFalseelse:stack.append(char)returnnotstack```复杂度分析：-时间复杂度：O(n)，其中n是字符串的长度。我们只需要遍历字符串一次。-空间复杂度：O(n)，在最坏的情况下，我们需要存储所有的左括号。3.2用队列实现栈题目描述：使用队列实现栈的操作。实现一个栈，支持push、top、pop和empty操作。使用两个队列来实现栈，队列的基本操作有push、pop、size和empty。示例：```MyStackstack=newMyStack();stack.push(1);stack.push(2);stack.top();//返回2stack.pop();//返回2stack.empty();//返回false```解题思路：我们可以使用两个队列来实现栈。其中一个队列用于存储元素，另一个队列作为辅助。当需要push元素时，我们将元素添加到非空队列中；当需要pop或top元素时，我们将非空队列中的元素依次移动到另一个队列中，直到只剩下一个元素，然后返回该元素。代码实现：```pythonclassMyStack:def__init__(self):self.queue1=[]self.queue2=[]defpush(self,x):ifnotself.queue1:self.queue1.append(x)whileself.queue2:self.queue1.append(self.queue2.pop(0))else:self.queue2.append(x)whileself.queue1:self.queue2.append(self.queue1.pop(0))defpop(self):ifself.queue1:returnself.queue1.pop(0)else:returnself.queue2.pop(0)deftop(self):ifself.queue1:returnself.queue1[0]else:returnself.queue2[0]defempty(self):returnnotself.queue1andnotself.queue2```复杂度分析：-时间复杂度：push操作的时间复杂度是O(n)，因为我们需要将一个队列中的所有元素移动到另一个队列中。pop、top和empty操作的时间复杂度都是O(1)。-空间复杂度：O(n)，其中n是栈中元素的数量。4.树与二叉树4.1二叉树的最大深度题目描述：给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。示例：```给定二叉树[3,9,20,null,null,15,7]，3/\920/\157返回它的最大深度3。```解题思路：我们可以使用递归或迭代的方法来求解二叉树的最大深度。递归的方法是：如果当前节点为空，则深度为0；否则，深度为左子树和右子树的深度中的较大值加1。迭代的方法是使用深度优先搜索（DFS）或广度优先搜索（BFS）来遍历整个树，并记录遍历的深度。代码实现：```pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefmaxDepth(root):ifnotroot:return0left_depth=maxDepth(root.left)right_depth=maxDepth(root.right)returnmax(left_depth,right_depth)+1```复杂度分析：-时间复杂度：O(n)，其中n是二叉树的节点数量。我们需要遍历每个节点。-空间复杂度：O(h)，其中h是二叉树的高度。在最坏的情况下，空间复杂度是O(n)，当二叉树退化为链表时。4.2二叉树的层序遍历题目描述：给你一个二叉树，请你返回其按层序遍历得到的节点值。（即从左到右，逐层遍历）。示例：```给定二叉树:[3,9,20,null,null,15,7],3/\920/\157返回其层序遍历结果：[[3],[9,20],[15,7]]```解题思路：我们可以使用广度优先搜索（BFS）来实现二叉树的层序遍历。我们使用一个队列来存储每一层的节点。首先，将根节点入队。然后，当队列不为空时，我们获取当前队列的大小，即当前层的节点数量。然后，遍历这些节点，将它们的值添加到结果中，并将它们的子节点入队。代码实现：```pythonfromcollectionsimportdequedeflevelOrder(root):ifnotroot:return[]result=[]queue=deque([root])whilequeue:level_size=len(queue)current_level=[]for_inrange(level_size):node=queue.popleft()current_level.append(node.val)ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)result.append(current_level)returnresult```复杂度分析：-时间复杂度：O(n)，其中n是二叉树的节点数量。我们需要遍历每个节点。-空间复杂度：O(n)，在最坏的情况下，队列中可能存储所有的节点。5.哈希表5.1两数之和题目描述：给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。你可以按任意顺序返回答案。示例：```输入：nums=[2,7,11,15],target=9输出：[0,1]解释：因为nums[0]+nums[1]==9，返回[0,1]。```解题思路：我们可以使用哈希表来解决这个问题。在遍历数组的同时，我们检查当前元素的补数（即目标值减去当前元素）是否已经存在于哈希表中。如果存在，我们就找到了答案；如果不存在，就将当前元素存入哈希表中。代码实现：```pythondeftwoSum(nums,target):num_map={}fori,numinenumerate(nums):complement=target-numifcomplementinnum_map:return[num_map[complement],i]num_map[num]=ireturn[]```复杂度分析：-时间复杂度：O(n)，其中n是数组的长度。我们只需要遍历数组一次。-空间复杂度：O(n)，其中n是数组的长度。哈希表最多存储n个元素。5.2存在重复元素题目描述：给定一个整数数组，判断是否存在重复元素。如果存在一值在数组中出现至少两次，函数返回true；如果数组中每个元素都不相同，则返回false。示例：```输入:[1,2,3,1]输出:true输入:[1,2,3,4]输出:false```解题思路：我们可以使用哈希表来解决这个问题。在遍历数组的同时，我们检查当前元素是否已经存在于哈希表中。如果存在，则说明数组中有重复元素；如果不存在，就将当前元素存入哈希表中。代码实现：```pythondefcontainsDuplicate(nums):num_set=set()fornuminnums:ifnuminnum_set:returnTruenum_set.add(num)returnFalse```复杂度分析：-时间复杂度：O(n)，其中n是数组的长度。我们只需要遍历数组一次。-空间复杂度：O(n)，在最坏的情况下，哈希表需要存储所有的元素。6.堆与优先队列6.1数组中的第K个最大元素题目描述：在未排序的数组中找到第k个最大的元素。请注意，你需要找的是数组排序后的第k个最大的元素，而不是第k个不同的元素。示例：```输入:[3,2,1,5,6,4]和k=2输出:5```解题思路：我们可以使用堆来解决这个问题。我们可以构建一个大小为k的最小堆，然后遍历数组中的每个元素。如果堆的大小小于k，则将元素加入堆中；否则，如果当前元素大于堆顶的元素，则将堆顶的元素弹出，并将当前元素加入堆中。最后，堆顶的元素就是第k个最大的元素。代码实现：```pythonimportheapqdeffindKthLargest(nums,k):heap=[]fornuminnums:iflen(heap)<k:heapq.heappush(heap,num)else:ifnum>heap[0]:heapq.heappop(heap)heapq.heappush(heap,num)returnheap[0]```复杂度分析：-时间复杂度：O(nlogk)，其中n是数组的长度。对于每个元素，我们需要进行堆操作，时间复杂度为O(logk)。-空间复杂度：O(k)，我们需要存储一个大小为k的堆。6.2前K个高频元素题目描述：给定一个非空的整数数组，返回其中出现频率前k高的元素。示例：```输入:nums=[1,1,1,2,2,3],k=2输出:[1,2]```解题思路：我们可以使用哈希表和堆来解决这个问题。首先，使用哈希表统计每个元素出现的频率。然后，使用一个大小为k的最大堆（或最小堆）来存储频率最高的k个元素。最后，从堆中取出这k个元素。代码实现：```pythonimportheapqfromcollectionsimportdefaultdictdeftopKFrequent(nums,k):freq_map=defaultdict(int)fornuminnums:freq_map[num]+=1heap=[]fornum,freqinfreq_map.items():heapq.heappush(heap,(-freq,num))result=[]for_inrange(k):result.append(heapq.heappop(heap)[1])returnresult```复杂度分析：-时间复杂度：O(nlogk)，其中n是数组的长度。对于每个元素，我们需要进行堆操作，时间复杂度为O(logk)。-空间复杂度：O(n)，我们需要存储哈希表和堆。7.图7.1岛屿数量题目描述：给你一个由'1'（陆地）和'0'（水）组成的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接而成。示例：```输入：grid=[["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]输出：1```解题思路：我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来解决这个问题。我们遍历网格中的每个格子，如果遇到陆地（'1'），我们就进行DFS或BFS，将相邻的陆地都标记为已访问，并将岛屿数量加1。代码实现：```pythondefnumIslands(grid):ifnotgridornotgrid[0]:return0rows,cols=len(grid),len(grid[0])count=0foriinrange(rows):forjinrange(cols):ifgrid[i][j]=='1':self.dfs(grid,i,j)count+=1returncountdefdfs(self,grid,i,j):ifi<0ori>=len(grid)orj<0orj>=len(grid[0])orgrid[i][j]!='1':returngrid[i][j]='0'self.dfs(grid,i+1,j)self.dfs(grid,i-1,j)self.dfs(grid,i,j+1)self.dfs(grid,i,j-1)```复杂度分析：-时间复杂度：O(mn)，其中m和n分别是网格的行数和列数。我们需要遍历每个格子。-空间复杂度：O(mn)，在最坏的情况下，递归栈的深度可能达到mn。7.2课程表题目描述：你这个学期必须选修numCourse门课程，记为0到numCourse-1。在选修某些课程之前需要一些先修课程。例如，想要学习课程0，你需要先完成课程1，我们用一个匹配来表示他们：[0,1]给定课程总量以及它们的先修要求，请你判断是否可能完成所有课程的学习？示例：```输入:numCourses=2,prerequisites=[[1,0]]输出:true解释:总共有2门课程。要学习课程1，你需要先完成课程0。因此，它是有可能的。```解题思路：这个问题可以转化为判断有向图中是否存在环。我们可以使用拓扑排序来解决。我们首先构建一个邻接表来表示课程之间的依赖关系，然后计算每个课程的入度。我们使用一个队列来存储入度为0的课程，然后依次从队列中取出课程，减少其邻居课程的入度。如果邻居课程的入度变为0，则将其加入队列。最后，如果所有课程都被处理过，则说明没有环，可以完成所有课程的学习；否则，说明有环，无法完成所有课程的学习。代码实现：```pythonfromcollectionsimportdequedefcanFinish(numCourses,prerequisites):创建邻接表和入度数组adj=[[]for_inrange(numCourses)]in_degree=[0]numCourses构建邻接表和入度数组forcourse,prereqinprerequisites:adj[prereq].append(course)in_degree[course]+=1将所有入度为0的课程加入队列queue=deque()foriinrange(numCourses):ifin_degree[i]==0:queue.append(i)count=0whilequeue:course=queue.popleft()count+=1减少邻居课程的入度forneighborinadj[course]:in_degree[neighbor]-=1ifin_degree[neighbor]==0:queue.append(neighbor)returncount==numCourses```复杂度分析：-时间复杂度：O(V+E)，其中V是课程的数量，E是先修要求的数量。我们需要遍历每个课程和每个先修要求。-空间复杂度：O(V+E)，我们需要存储邻接表和入度数组。二、算法类题目1.排序算法1.1快速排序题目描述：给定一个整数数组nums，将该数组按照升序排序。示例：```输入:[5,2,3,1]输出:[1,2,3,5]```解题思路：快速排序是一种分治算法。它选择一个元素作为基准，然后将数组分为两部分，左边部分的元素都小于基准，右边部分的元素都大于基准。然后，递归地对左右两部分进行排序。代码实现：```pythondefquickSort(nums):iflen(nums)<=1:returnnumspivot=nums[len(nums)//2]left=[xforxinnumsifx<pivot]middle=[xforxinnumsifx==pivot]right=[xforxinnumsifx>pivot]returnquickSort(left)+middle+quickSort(right)```复杂度分析：-时间复杂度：平均情况下是O(nlogn)，最坏情况下是O(n²)，当数组已经有序或逆序时。-空间复杂度：O(logn)，这是递归调用栈的空间。1.2归并排序题目描述：给定一个整数数组nums，将该数组按照升序排序。示例：```输入:[5,2,3,1]输出:[1,2,3,5]```解题思路：归并排序是一种分治算法。它将数组分成两半，分别对两半进行排序，然后将排序好的两半合并成一个有序数组。代码实现：```pythondefmergeSort(nums):iflen(nums)<=1:returnnumsmid=len(nums)//2left=mergeSort(nums[:mid])right=mergeSort(nums[mid:])returnmerge(left,right)defmerge(left,right):result=[]i=j=0whilei<len(left)andj<len(right):ifleft[i]<right[j]:result.append(left[i])i+=1else:result.append(right[j])j+=1result.extend(left[i:])result.extend(right[j:])returnresult```复杂度分析：-时间复杂度：O(nlogn)，对于所有情况都是如此。-空间复杂度：O(n)，我们需要额外的空间来存储合并后的数组。2.搜索算法2.1二分查找题目描述：给定一个n个元素有序的（升序）整型数组nums和一个目标值target，写一个函数搜索nums中的target，如果目标值存在返回下标，否则返回-1。示例：```输入:nums=[-1,0,3,5,9,12],target=9输出:4解释:9出现在nums中并且下标为4```解题思路：二分查找是一种在有序数组中查找特定元素的算法。它通过不断将搜索区间减半来查找目标值。具体来说，它首先比较中间元素与目标值，如果中间元素等于目标值，则返回中间元素的索引；如果中间元素小于目标值，则在右半部分继续搜索；如果中间元素大于目标值，则在左半部分继续搜索。代码实现：```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```复杂度分析：-时间复杂度：O(logn)，其中n是数组的长度。每次搜索都将搜索区间减半。-空间复杂度：O(1)，我们只使用了常数个额外空间。2.2搜索二维矩阵题目描述：编写一个高效的算法来搜索mxn矩阵matrix中的一个目标值target。该矩阵具有以下特性：-每行的元素从左到右升序排列。-每列的元素从上到下升序排列。示例：```输入:matrix=[[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]],target=5输出:true```解题思路：我们可以从矩阵的右上角开始搜索。如果当前元素等于目标值，则返回true；如果当前元素大于目标值，则向左移动；如果当前元素小于目标值，则向下移动。如果搜索过程中超出了矩阵的边界，则说明目标值不存在。代码实现：```pythondefsearchMatrix(matrix,target):ifnotmatrixornotmatrix[0]:returnFalserows,cols=len(matrix),len(matrix[0])row,col=0,cols-1whilerow<rowsandcol>=0:ifmatrix[row][col]==target:returnTrueelifmatrix[row][col]>target:col-=1else:row+=1returnFalse```复杂度分析：-时间复杂度：O(m+n)，其中m和n分别是矩阵的行数和列数。在最坏的情况下，我们需要从右上角走到左下角。-空间复杂度：O(1)，我们只使用了常数个额外空间。3.递归与分治3.1爬楼梯题目描述：假设你正在爬楼梯。需要n阶你才能到达楼顶。每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶？示例：```输入：2输出：2解释：有两种方法可以爬到楼顶。1.1阶+1阶2.2阶```解题思路：这个问题可以使用动态规划或递归来解决。递归的思路是：要到达第n阶楼梯，你可以从第n-1阶爬1步，或者从第n-2阶爬2步。因此，到达第n阶的方法数等于到达第n-1阶的方法数加上到达第n-2阶的方法数。代码实现：```pythondefclimbStairs(n):ifn==1:return1ifn==2:return2dp=[0](n+1)dp[1]=1dp[2]=2foriinrange(3,n+1):dp[i]=dp[i-1]+dp[i-2]returndp[n]```复杂度分析：-时间复杂度：O(n)，我们需要计算从1到n的所有值。-空间复杂度：O(n)，我们需要一个大小为n+1的数组来存储中间结果。3.2分治算法题目描述：给定一个整数数组nums，将该数组按照升序排序。示例：```输入:[5,2,3,1]输出:[1,2,3,5]```解题思路：分治算法的基本思想是将问题分解为若干个子问题，递归地解决子问题，然后将子问题的解合并起来。对于排序问题，我们可以将数组分成两半，分别对两半进行排序，然后将排序好的两半合并成一个有序数组。代码实现：```pythondefsortArray(nums):iflen(nums)<=1:returnnumsmid=len(nums)//2left=sortArray(nums[:mid])right=sortArray(nums[mid:])returnmerge(left,right)defmerge(left,right):result=[]i=j=0whilei<len(left)andj<len(right):ifleft[i]<right[j]:result.append(left[i])i+=1else:result.append(right[j])j+=1result.extend(left[i:])result.extend(right[j:])returnresult```复杂度分析：-时间复杂度：O(nlogn)，对于所有情况都是如此。-空间复杂度：O(n)，我们需要额外的空间来存储合并后的数组。4.动态规划4.1最大子序和题目描述：给定一个整数数组nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例：```输入:[-2,1,-3,4,-1,2,1,-5,4]输出:6解释:连续子数组[4,-1,2,1]的和最大，为6。```解题思路：我们可以使用动态规划来解决最大子序和问题。定义一个状态dp[i]表示以第i个元素结尾的连续子数组的最大和。那么，dp[i]=max(nums[i],dp[i-1]+nums[i])。我们只需要遍历数组，计算每个dp[i]的值，并记录其中的最大值。代码实现：```pythondefmaxSubArray(nums):ifnotnums:return0max_sum=current_sum=nums[0]fornuminnums[1:]:current_sum=max(num,current_sum+num)max_sum=max(max_sum,current_sum)returnmax_sum```复杂度分析：-时间复杂度：O(n)，其中n是数组的长度。我们只需要遍历数组一次。-空间复杂度：O(1)，我们只使用了常数个额外空间。4.2零钱兑换题目描述：给定不同面额的硬币coins和一个总金额amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回-1。示例：```输入:coins=[1,2,5],amount=11输出:3解释:11=5+5+1```解题思路：我们可以使用动态规划来解决零钱兑换问题。定义一个状态dp[i]表示凑成金额i所需的最少硬币个数。那么，dp[i]=min(dp[i],dp[i-coin]+1)，其中coin是硬币的面额。我们只需要从1到amount遍历，计算每个dp[i]的值。代码实现：```pythondefcoinChange(coins,amount):dp=[float('inf')](amount+1)dp[0]=0forcoinincoins:foriinrange(coin,amount+1):dp[i]=min(dp[i],dp[i-coin]+1)returndp[amount]ifdp[amount]!=float('inf')else-1```复杂度分析：-时间复杂度：O(amountlen(coins))，其中amount是总金额，len(coins)是硬币的数量。-空间复杂度：O(amount)，我们需要一个大小为amount+1的数组来存储中间结果。5.贪心算法5.1分发饼干题目描述：假设你是一位很棒的家长，想要给你的孩子们一些小饼干。每个孩子都有一个贪心胃口值g，这是能让孩子们满足胃口的饼干的最小尺寸。并且每块饼干j，都有一个尺寸s[j]。如果s[j]>=g[i]，我们可以将这个饼干j分配给孩子i，这个孩子会得到满足。你的目标是尽可能满足越多的孩子，并输出这个最大数值。示例：```输入:g=[1,2,3],s=[1,1]输出:1解释:你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。虽然你有两块小饼干，由于尺寸都是1，你只能让胃口值是1的孩子满足。所以你应该输出1。```解题思路：我们可以使用贪心算法来解决分发饼干的问题。首先，将孩子的胃口值和饼干的大小都排序。然后，我们使用两个指针，一个指向孩子，一个指向饼干。如果当前饼干的大小满足当前孩子的胃口，我们就将饼干分配给孩子，并移动两个指针；否则，我们只移动饼干指针，尝试更大的饼干。代码实现：```pythondeffindContentChildren(g,s):g.sort()s.sort()child_ptr=cookie_ptr=0satisfied_children=0whilechild_ptr<len(g)andcookie_ptr<len(s):ifs[cookie_ptr]>=g[child_ptr]:satisfied_children+=1child_ptr+=1cookie_ptr+=1else:cookie_ptr+=1returnsatisfied_children```复杂度分析：-时间复杂度：O(mlogm+nlogn)，其中m和n分别是孩子数量和饼干数量。这是排序的时间复杂度。-空间复杂度：O(1)，我们只使用了常数个额外空间。5.2摆动排序题目描述：给定一个无序的数组nums，将它重新排列成nums[0]<nums[1]>nums[2]<nums[3]...的顺序。示例：```输入:nums=[1,5,1,1,6,4]输出:[1,6,1,5,1,4]```解题思路：我们可以使用贪心算法来解决摆动排序问题。首先，我们对数组进行排序。然后，我们将数组分成两部分，前一部分是较小的元素，后一部分是较大的元素。最后，我们从后一部分中取一个元素，从前一部分中取一个元素，交替地放入新数组中。代码实现：```pythondefwiggleSort(nums):nums.sort()n=len(nums)mid=(n+1)//2left=nums[:mid]right=nums[mid:]result=[]i,j=0,0forkinrange(n):ifk%2==0:result.append(left[i])i+=1else:result.append(right[j])j+=1nums[:]=result```复杂度分析：-时间复杂度：O(nlogn)，这是排序的时间复杂度。-空间复杂度：O(n)，我们需要额外的空间来存储排序后的数组和结果。6.回溯算法6.1全排列题目描述：给定一个没有重复数字的序列，返回其所有可能的全排列。示例：```输入:[1,2,3]输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]```解题思路：我们可以使用回溯算法来解决全排列问题。我们使用一个路径数组来记录当前的排列，使用一个集合来记录已经使用过的数字。然后，我们遍历所有数字，如果数字没有被使用过，我们就将其加入路径，并标记为已使用。然后，我们递归地生成排列。当路径的长度等于输入数组的长度时，我们就找到了一个全排列，将其加入结果中。代码实现：```pythondefpermute(nums):defbacktrack(path,used):iflen(path)==len(nums):result.append(path[:])returnforiinrange(len(nums)):ifnotused[i]:path.append(nums[i])used[i]=Truebacktrack(path,used)path.pop()used[i]=Falseresult=[]backtrack([],[False]len(nums))returnresult```复杂度分析：-时间复杂度：O(n!)，其中n是输入数组的长度。全排列的数量是n!。-空间复杂度：O(n)，我们需要存储路径和已使用的标记。6.2N皇后题目描述：n皇后问题研究的是如何将n个皇后放置在n×n的棋盘上，并且皇后彼此之间不能相互攻击。示例：```输入:4输出:[[".Q..",//解法1"...Q","Q...","..Q."],["..Q.",//解法2"Q...","...Q",".Q.."]]解释:4皇后问题存在两个不同的解法。```解题思路：我们可以使用回溯算法来解决N皇后问题。我们使用一个数组来记录每一行皇后的位置。然后，我们从第一行开始，尝试在每个位置放置皇后，并检查是否与之前放置的皇后冲突。如果不冲突，我们就继续放置下一行的皇后；如果冲突，我们就尝试下一个位置。当所有行都放置完皇后时，我们就找到了一个解。代码实现：```pythondefsolveNQueens(n):defbacktrack(row,cols,diag1,diag2):ifrow==n:result.append(["".join(row)forrowinboard])returnforcolinrange(n):d1=row-cold2=row+colifcolincolsord1indiag1ord2indiag2:continueboard[row][col]='Q'cols.add(col)diag1.add(d1)diag2.add(d2)backtrack(row+1,cols,diag1,diag2)board[row][col]='.'cols.remove(col)diag1.remove(d1)diag2.remove(d2)board=[['.'for_inrange(n)]for_inrange(n)]result=[]backtrack(0,set(),set(),set())returnresult```复杂度分析：-时间复杂度：O(n!)，在最坏的情况下，我们需要尝试所有可能的排列。-空间复杂度：O(n)，我们需要存储每一行皇后的位置。7.位运算7.1汉明距离题目描述：两个整数之间的汉明距离指的是这两个数字的二进制数对应位不同的数量。给你两个整数x和y，计算它们之间的汉明距离。示例：```输入:x=1,y=4输出:2解释:1(0001)4(0100)↑↑上面的箭头指出了对应二进制位不同的位置。```解题思路：我们可以使用位运算来计算汉明距离。首先，计算x和y的异或结果，异或结果中为1的位就是x和y不同的位。然后，统计异或结果中1的个数。代码实现：```pythondefhammingDistance(x,y):xor=x^ydistance=0whilexor:distance+=xor&1xor>>=1returndistance```复杂度分析：-时间复杂度：O(1)，因为x和y都是32位整数，最多需要循环32次。-空间复杂度：O(1)，我们只使用了常数个额外空间。7.2颠倒二进制位题目描述：颠倒给定的32位无符号整数的二进制位。示例：```输入:00000010100101000001111010011100输出:00111001011110000010100101000000解释:输入的二进制串00000010100101000001111010011100表示无符号整数43261596，因此返回964176192，其二进制表示形式为00111001011110000010100101000000。```解题思路：我们可以使用位运算来颠倒二进制位。具体来说，我们可以从原数的最低位开始，依次取出每一位，然后将其放到新数的对应位置上。具体步骤如下：1.初始化结果为0；2.循环32次，每次将原数的最低位取出，放到结果的最高位，然后原数右移一位，结果左移一位；3.返回结果。代码实现：```pythondefreverseBits(n):result=0foriinrange(32):result=(result<<1)|(n&1)n>>=1returnresult```复杂度分析：-时间复杂度：O(1)，因为n是32位整数，最多需要循环32次。-空间复杂度：O(1)，我们只使用了常数个额外空间。三、实际应用类题目1.数学问题1.1阶乘后的零题目描述：给定一个整数n，返回n!结果中尾随零的数量。示例：```输入：n=5输出：1解释：5!=120，尾随零的数量是1。```解题思路：阶乘后的零的数量等于质因数2和5的对数中的较小值。由于质因数2的数量通常比5多，所以我们只需要计算质因数5的数量。具体来说，我们需要计算从1到n的所有数中5的倍数、25的倍数、125的倍数等的数量，然后求和。代码实现：```pythondeftrailingZeroes(n):count=0whilen>0:n=n//5count+=nreturncount```复杂度分析：-时间复杂度：O(logn)，因为每次循环都将n除以5。-空间复杂度：O(1)，我们只使用了常数个额外空间。1.2快乐数题目描述：编写一个算法来判断一个数n是不是快乐数。「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为1，也可能是无限循环但始终变不到1。如果可以变为1，那么这个数就是快乐数。示例：```输入：n=19输出：true解释：1^2+9^2=828^2+2^2=686^2+8^2=1001^2+0^2+0^2=1```解题思路：我们可以使用哈希表来检测循环。在计算数字的平方和的过程中，如果出现重复的数字，说明进入了循环，这个数不是快乐数；如果最终得到1，说明这个数是快乐数。代码实现：```pythondefisHappy(n):seen=set()whilen!=1andnnotinseen:seen.add(n)n=sum(int(digit)2fordigitinstr(n))returnn==1```复杂度分析：-时间复杂度：O(logn)，因为每次迭代都将n替换为它的数字平方和，这个值通常比n小。-空间复杂度：O(logn)，因为我们需要存储已经出现过的数字。2.字符串处理2.1最长回文子串题目描述：给定一个字符串s，找到s中最长的回文子串。你可以假设s的最大长度为1000。示例：```输入:"babad"输出:"bab"注意:"aba"也是一个有效答案。```解题思路：我们可以使用动态规划或中心扩展法来寻找最长回文子串。中心扩展法的思路是：遍历字符串的每个字符，以该字符为中心向两边扩展，找到最长的回文子串。同时，我们还需要考虑回文子串的长度可能是奇数或偶数的情况。代码实现：```pythondeflongestPalindrome(s):ifnots:return""start=end=0foriinrange(len(s)):len1=expandAroundCenter(s,i,i)len2=expandAroundCenter(s,i,i+1)max_len=max(len1,len2)ifmax_len>end-start:start=i-(max_len-1)//2end=i+max_len//2returns[start:end+1]defexpandAroundCenter(s,left,right):whileleft>=0andright<len(s)ands[left]==s[right]:left-=1right+=1returnright-left-1```复杂度分析：-时间复杂度：O(n^2)，对于每个中心点，我们需要向两边扩展。-空间复杂度：O(1)，我们只使用了常数个额外空间。2.2正则表达式匹配题目描述：给你一个字符串s和一个字符规律p，请你来实现一个支持'.'和''的正则表达式匹配。'.'匹配任意单个字符''匹配零个或多个前面的那一个元素示例：```输入：s="aa",p="a"输出：false解释："a"无法匹配"aa"整个字符串。```解题思路：我们可以使用动态规划来解决正则表达式匹配问题。定义一个二维数组dp，其中dp[i][j]表示字符串s的前i个字符和正则表达式p的前j个字符是否匹配。然后，我们根据p[j-1]的值来更新dp[i][j]。代码实现：```pythondefisMatch(s,p):m,n=len(s),len(p)dp=[[False](n+1)for_inrange(m+1)]dp[0][0]=Trueforjinrange(1,n+1):ifp[j-1]=='':dp[0][j]=dp[0][j-2]foriinrange(1,m+1):forjinrange(1,n+1):ifp[j-1]=='.'orp[j-1]==s[i-1]:dp[i][j]=dp[i-1][j-1]elifp[j-1]=='':dp[i][j]=dp[i][j-2]or(dp[i-1][j]and(p[j-2]=='.'orp[j-2]==s[i-1]))returndp[m][n]```复杂度分析：-时间复杂度：O(mn)，其中m和n分别是字符串s和正则表达式p的长度。-空间复杂度：O(mn)，我们需要一个二维数组来存储中间结果。3.数组处理3.1旋转图像题目描述：给定一个n×n的二维矩阵matrix表示一个图像。请你将图像顺时针旋转90度。你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。示例：```输入：matrix=[[1,2,3],[4,5,6],[7,8,9]]输出：[[7,4,1],[8,5,2],[9,6,3]]```解题思路：我们可以使用两步来旋转图像：1.先转置矩阵；2.然后反转每一行。转置矩阵是指将矩阵的第i行第j列的元素与第j行第i列的元素交换。反转每一行是指将每一行的元素顺序反转。代码实现：```pythondefrotate(matrix):n=len(matrix)转置矩阵foriinrange(n):forjinrange(i,n):matrix[i][j],matrix[j][i]=matrix[j][i],matrix[i][j]反转每一行foriinrange(n):matrix[i]=matrix[i][::-1]```复杂度分析：-时间复杂度：O(n^2)，其中n是矩阵的大小。我们需要遍历矩阵的所有元素。-空间复杂度：O(1)，我们只使用了常数个额外空间。3.2搜索二维矩阵II题目描述：编写一个高效的算法来搜索mxn矩阵matrix中的一个目标值target。该矩阵具有以下特性：-每行的元素从左到右升序排列。-每列的元素从上到下升序排列。示例：```输入:matrix=[[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]],target=5输出:true```解题思路：我们可以从矩阵的右上角开始搜索。如果当前元素等于目标值，则返回true；如果当前元素大于目标值，则向左移动；如果当前元素小于目标值，则向下移动。如果搜索过程中超出了矩阵的边界，则说明目标值不存在。代码实现：```pythondefsearchMatrix(matrix,target):ifnotmatrixornotmatrix[0]:returnFalserows,cols=len(matrix),len(matrix[0])row,col=0,cols-1whilerow<rowsandcol>=0:ifmatrix[row][col]==target:returnTrueelifmatrix[row][col]>target:col-=1else:row+=1returnFalse```复杂度分析：-时间复杂度：O(m+n)，其中m和n分别是矩阵的行数和列数。在最坏的情况下，我们需要从右上角走到左下角。-空间复杂度：O(1)，我们只使用了常数个额外空间。4.模拟问题4.1括号生成题目描述：数字n代表生成括号的对数，请你设计一个函数，能够生成所有可能的并且有效的括号组合。示例：```输入：n=3输出：["((()))","(()())","(())()","()(())","()()()"]```解题思路：我们可以使用回溯算法来生成有效的括号组合。我们使用两个计数器left和right来记录左括号和右括号的数量。在每一步，如果左括号的数量小于n，我们可以添加一个左括号；如果右括号的数量小于左括号的数量，我们可以添加一个右括号。代码实现：```pythondefgenerateParenthesis(n):defbacktrack(current,left,right):iflen(current)==2n:result.append(current)