力扣题库20题答案

力扣题库20题答案一、数组操作类题目1.两数之和（简单）题目描述：给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。示例：```输入：nums=[2,7,11,15],target=9输出：[0,1]解释：因为nums[0]+nums[1]==9，返回[0,1]。```解答思路：这道题可以使用哈希表来高效解决。我们可以遍历数组，对于每个元素，检查其补数（target-nums[i]）是否已经存在于哈希表中。如果存在，则直接返回当前元素和补数的索引；如果不存在，则将当前元素及其索引存入哈希表中，继续遍历。代码实现：```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个元素。2.盛最多水的容器（中等）题目描述：给定一个长度为n的整数数组height。有n条垂线，第i条线的两个端点是(i,0)和(i,height[i])。找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。示例：```输入：[1,8,6,2,5,4,8,3,7]输出：49解释：图中垂直线代表输入数组[1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为49。```解答思路：可以使用双指针法来解决这个问题。初始化两个指针，一个在数组的最左端，一个在数组的最右端。计算两个指针所指向的线段构成的容器容量，然后移动较短的那根指针向中间移动，继续计算新的容器容量，直到两个指针相遇。代码实现：```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)，我们只需要遍历数组一次。-空间复杂度：O(1)，我们只使用了常数个额外的空间。3.搜索旋转排序数组（中等）题目描述：整数数组nums按升序排列，数组中的值互不相同。在传递给函数之前，nums在预先未知的某个下标k（0<=k<nums.length）进行了旋转，使数组变为[nums[k],nums[k+1],...,nums[n-1],nums[0],nums[1],...,nums[k-1]]（下标从0开始计数）。例如，[0,1,2,4,5,6,7]在下标3处经旋转后可能变为[4,5,6,7,0,1,2]。给你旋转后的数组nums和一个整数target，如果nums中存在这个目标值target，则返回它的下标，否则返回-1。示例：```输入：nums=[4,5,6,7,0,1,2],target=0输出：4```解答思路：可以使用二分查找来解决这个问题。由于数组是旋转排序的，我们可以通过比较中间元素与最右端元素来确定哪一部分是有序的。如果中间元素小于最右端元素，则右半部分是有序的；否则左半部分是有序的。然后判断目标值是否在有序的部分中，如果在，则在该部分继续二分查找；否则在另一部分继续查找。代码实现：```pythondefsearch(nums,target):left,right=0,len(nums)-1whileleft<=right:mid=(left+right)//2ifnums[mid]==target:returnmid检查右半部分是否有序ifnums[mid]<nums[right]:目标值在右半部分ifnums[mid]<target<=nums[right]:left=mid+1else:right=mid-1else:左半部分有序ifnums[left]<=target<nums[mid]:right=mid-1else:left=mid+1return-1```复杂度分析：-时间复杂度：O(logn)，我们使用了二分查找，每次都将搜索范围减半。-空间复杂度：O(1)，我们只使用了常数个额外的空间。二、字符串处理类题目4.最长公共前缀（简单）题目描述：编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串""。示例：```输入：strs=["flower","flow","flight"]输出："fl"```解答思路：可以逐个字符比较所有字符串的相同位置字符，直到找到不匹配的字符为止。具体步骤如下：1.如果数组为空，返回空字符串2.取第一个字符串作为基准3.遍历基准字符串的每个字符位置4.检查其他字符串在该位置是否都有相同的字符5.如果有，则将该字符加入公共前缀；如果没有，则停止遍历代码实现：```pythondeflongestCommonPrefix(strs):ifnotstrs:return""prefix=""foriinrange(len(strs[0])):char=strs[0][i]forjinrange(1,len(strs)):ifi>=len(strs[j])orstrs[j][i]!=char:returnprefixprefix+=charreturnprefix```复杂度分析：-时间复杂度：O(S)，其中S是所有字符串中字符数量的总和。在最坏情况下，我们需要比较所有字符串的所有字符。-空间复杂度：O(1)，我们只使用了常数个额外的空间。5.最长回文子串（中等）题目描述：给定一个字符串s，找到s中最长的回文子串。你可以假设s的最大长度为1000。示例：```输入：s="babad"输出："bab"注意："aba"也是一个有效答案。```解答思路：可以使用中心扩展法来解决这个问题。回文串的中心可以是字符（如"aba"的中心是'b'），也可以是两个字符之间的位置（如"abba"的中心是两个'b'之间的位置）。我们可以遍历字符串，以每个字符和每个字符之间的位置作为中心，向两边扩展，寻找最长的回文子串。代码实现：```pythondeflongestPalindrome(s):ifnots:return""start=0end=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(n)的时间。-空间复杂度：O(1)，我们只使用了常数个额外的空间。6.正则表达式匹配（困难）题目描述：给你一个字符串s和一个字符规律p，请你来实现一个支持'.'和''的正则表达式匹配。'.'匹配任意单个字符''匹配零个或多个前面的那一个元素所谓匹配，是要涵盖整个字符串s，而不是部分字符串。示例：```输入：s="aa",p="a"输出：true解释：因为''代表可以匹配零个或多个前面的元素,在这里前面的元素是'a'。因此，字符串"aa"可以被视为'a'重复了一次。```解答思路：可以使用动态规划来解决这个问题。定义dp[i][j]表示s的前i个字符和p的前j个字符是否匹配。状态转移方程如下：1.如果p[j-1]不是''，则dp[i][j]=dp[i-1][j-1]and(s[i-1]==p[j-1]orp[j-1]=='.')2.如果p[j-1]是''，则有两种情况：-匹配零个前面的元素：dp[i][j]=dp[i][j-2]-匹配一个或多个前面的元素：dp[i][j]=dp[i-1][j]and(s[i-1]==p[j-2]orp[j-2]=='.')代码实现：```pythondefisMatch(s,p):m,n=len(s),len(p)dp=[[False](n+1)for_inrange(m+1)]dp[0][0]=True处理p以开头的情况forjinrange(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]匹配一个或多个前面的元素ifp[j-2]=='.'orp[j-2]==s[i-1]:dp[i][j]=dp[i][j]ordp[i-1][j]returndp[m][n]```复杂度分析：-时间复杂度：O(mn)，其中m和s是字符串s和p的长度。-空间复杂度：O(mn)，我们使用了一个二维数组来存储中间结果。三、链表操作类题目7.合并两个有序链表（简单）题目描述：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的节点组成的。示例：```输入：1->2->4,1->3->4输出：1->1->2->3->4->4```解答思路：可以使用递归或迭代的方法来解决这个问题。迭代的方法如下：1.创建一个哑节点作为新链表的头部2.使用两个指针分别遍历两个链表3.比较两个指针所指节点的值，将较小的节点连接到新链表，并移动相应的指针4.重复上述步骤，直到其中一个链表遍历完毕5.将另一个链表的剩余部分连接到新链表代码实现：```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(n+m)，其中n和m是两个链表的长度。-空间复杂度：O(1)，我们只使用了常数个额外的空间。8.环形链表（简单）题目描述：给定一个链表，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪next指针再次到达该节点，则链表中存在环。为了表示给定链表中的环，我们使用整数pos来表示链表尾连接到链表中的位置（索引从0开始）。如果pos是-1，则在该链表中没有环。注意：pos不作为参数传递，仅仅是为了标识链表的实际情况。示例：```输入：head=[3,2,0,-4],pos=1输出：true解释：链表中有一个环，其尾部连接到第二个节点。```解答思路：可以使用快慢指针法来检测环。初始化两个指针，一个慢指针每次移动一步，一个快指针每次移动两步。如果链表中有环，快指针最终会追上慢指针；如果没有环，快指针会先到达链表末尾。代码实现：```pythonclassListNode:def__init__(self,x):self.val=xself.next=NonedefhasCycle(head):ifnotheadornothead.next:returnFalseslow=headfast=head.nextwhileslow!=fast:ifnotfastornotfast.next:returnFalseslow=slow.nextfast=fast.next.nextreturnTrue```复杂度分析：-时间复杂度：O(n)，在最坏情况下，我们需要遍历整个链表。-空间复杂度：O(1)，我们只使用了常数个额外的空间。9.反转链表（中等）题目描述：反转一个单链表。示例：```输入:1->2->3->4->5->NULL输出:5->4->3->2->1->NULL```解答思路：可以使用迭代或递归的方法来反转链表。迭代的方法如下：1.初始化三个指针：prev（前一个节点，初始为None）、current（当前节点，初始为head）、next（下一个节点，初始为None）2.遍历链表，对于每个节点：-保存下一个节点：next=current.next-反转当前节点的指针：current.next=prev-移动prev和current：prev=current，current=next3.当遍历完成时，prev指向新的链表头代码实现：```pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefreverseList(head):prev=Nonecurrent=headwhilecurrent:next_node=current.nextcurrent.next=prevprev=currentcurrent=next_nodereturnprev```复杂度分析：-时间复杂度：O(n)，其中n是链表的长度。-空间复杂度：O(1)，我们只使用了常数个额外的空间。四、树和二叉树类题目10.二叉树的最大深度（简单）题目描述：给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。示例：```给定二叉树[3,9,20,null,null,15,7]，3/\920/\157返回它的最大深度3。```解答思路：可以使用递归或迭代的方法来计算二叉树的最大深度。递归的方法如下：1.如果当前节点为空，深度为02.否则，递归计算左子树和右子树的最大深度3.返回左右子树最大深度的较大值加1代码实现：```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)。11.验证二叉搜索树（中等）题目描述：给定一个二叉树，判断其是否是一个有效的二叉搜索树。一个二叉搜索树具有以下特征：-节点的左子树只包含小于当前节点的数。-节点的右子树只包含大于当前节点的数。-所有左子树和右子树自身也必须是二叉搜索树。示例：```输入:5/\14/\36输出:false解释:输入为:[5,1,4,null,null,3,6]。根节点的值为5，但是其右子节点的值为4。```解答思路：可以使用中序遍历的方法来验证二叉搜索树。二叉树的中序遍历结果是一个递增序列。我们可以进行中序遍历，并检查每个节点的值是否大于前一个节点的值。代码实现：```pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefisValidBST(root):stack=[]prev=Nonewhilerootorstack:whileroot:stack.append(root)root=root.leftroot=stack.pop()ifprevandroot.val<=prev.val:returnFalseprev=rootroot=root.rightreturnTrue```复杂度分析：-时间复杂度：O(n)，其中n是二叉树的节点数。-空间复杂度：O(h)，其中h是二叉树的高度。在最坏情况下，二叉树退化为链表，空间复杂度为O(n)。12.二叉树的层序遍历（中等）题目描述：给你一个二叉树，请你返回其按层序遍历得到的节点值。（即逐层地，从左到右访问所有节点）。示例：```二叉树：[3,9,20,null,null,15,7],3/\920/\157返回其层次遍历结果：[[3],[9,20],[15,7]]```解答思路：可以使用广度优先搜索（BFS）的方法来实现二叉树的层序遍历。具体步骤如下：1.使用队列来存储每一层的节点2.首先将根节点入队3.当队列不为空时：-获取当前队列的大小，即当前层的节点数-创建一个列表来存储当前层的节点值-遍历当前层的所有节点：-将节点值加入当前层列表-将节点的左右子节点入队-将当前层列表加入结果列表代码实现：```pythonfromcollectionsimportdequeclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdeflevelOrder(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)，在最坏情况下，队列中可能存储O(n)个节点。五、动态规划类题目13.爬楼梯（简单）题目描述：假设你正在爬楼梯。需要n阶你才能到达楼顶。每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢？示例：```输入：2输出：2解释：有两种方法可以爬到楼顶。1.1阶+1阶2.2阶```解答思路：这是一个典型的动态规划问题。定义dp[i]为爬到第i阶楼梯的方法数。根据题意，每次可以爬1或2个台阶，因此：dp[i]=dp[i-1]+dp[i-2]初始条件：dp[0]=1（一种方法：不爬）dp[1]=1（一种方法：爬1阶）可以使用动态规划或递归加记忆化的方法来解决这个问题。这里使用动态规划的方法。代码实现：```pythondefclimbStairs(n):ifn<=1:return1dp=[0](n+1)dp[0]=1dp[1]=1foriinrange(2,n+1):dp[i]=dp[i-1]+dp[i-2]returndp[n]```复杂度分析：-时间复杂度：O(n)，我们需要计算从2到n的每个值。-空间复杂度：O(n)，我们使用了一个数组来存储中间结果。14.零钱兑换（中等）题目描述：给定不同面额的硬币coins和一个总金额amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回-1。示例：```输入：coins=[1,2,5],amount=11输出：3解释：11=5+5+1```解答思路：这是一个典型的动态规划问题。定义dp[i]为凑成金额i所需的最少硬币数。对于每个金额i，我们可以遍历所有硬币，如果硬币的面额小于等于i，则：dp[i]=min(dp[i],dp[i-coin]+1)初始条件：dp[0]=0（凑成金额0不需要任何硬币）dp[i]=amount+1（一个足够大的数，表示初始时无法凑成）代码实现：```pythondefcoinChange(coins,amount):dp=[amount+1](amount+1)dp[0]=0foriinrange(1,amount+1):forcoinincoins:ifcoin<=i:dp[i]=min(dp[i],dp[i-coin]+1)returndp[amount]ifdp[amount]<=amountelse-1```复杂度分析：-时间复杂度：O(amountn)，其中n是硬币的种类数。-空间复杂度：O(amount)，我们使用了一个数组来存储中间结果。15.最长递增子序列（中等）题目描述：给定一个无序的整数数组，找到其中最长递增子序列的长度。示例：```输入:[10,9,2,5,3,7,101,18]输出:4解释:最长的递增子序列是[2,3,7,101]，它的长度是4。```解答思路：可以使用动态规划来解决这个问题。定义dp[i]为以nums[i]结尾的最长递增子序列的长度。对于每个i，我们需要遍历所有j<i，如果nums[j]<nums[i]，则：dp[i]=max(dp[i],dp[j]+1)最终结果是dp数组中的最大值。代码实现：```pythondeflengthOfLIS(nums):ifnotnums:return0n=len(nums)dp=[1]nforiinrange(1,n):forjinrange(i):ifnums[j]<nums[i]:dp[i]=max(dp[i],dp[j]+1)returnmax(dp)```复杂度分析：-时间复杂度：O(n^2)，我们需要两层循环来计算每个dp[i]。-空间复杂度：O(n)，我们使用了一个数组来存储中间结果。六、回溯算法类题目16.全排列（中等）题目描述：给定一个没有重复数字的序列，返回其所有可能的全排列。示例：```输入:[1,2,3]输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]```解答思路：可以使用回溯算法来生成所有可能的排列。具体步骤如下：1.使用一个列表来存储当前的排列2.使用一个集合或数组来标记哪些数字已经被使用3.递归地构建排列：-如果当前排列的长度等于输入数组的长度，则将当前排列加入结果列表-否则，遍历所有数字，如果数字未被使用，则将其加入当前排列，并标记为已使用，然后递归调用，最后回溯（从当前排列中移除该数字，并标记为未使用）代码实现：```pythondefpermute(nums):defbacktrack(first=0):所有数字都填入排列iffirst==n:output.append(nums[:])returnforiinrange(first,n):动态维护数组nums[first],nums[i]=nums[i],nums[first]继续填充下一个位置backtrack(first+1)回溯nums[first],nums[i]=nums[i],nums[first]n=len(nums)output=[]backtrack()returnoutput```复杂度分析：-时间复杂度：O(nn!)，其中n是输入数组的长度。有n!个排列，每个排列需要O(n)的时间来构建。-空间复杂度：O(n)，除了输出数组外，我们只使用了常数个额外的空间。17.组合总和（中等）题目描述：给定一个无重复元素的数组candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。candidates中的数字可以无限制重复被选取。示例：```输入：candidates=[2,3,6,7],target=7所求解集为：[[7],[2,2,3]]```解答思路：可以使用回溯算法来找到所有可能的组合。具体步骤如下：1.对数组进行排序（可选，但可以提前终止不必要的搜索）2.使用回溯算法，从数组的第一个元素开始尝试：-如果当前和等于目标，则将当前组合加入结果列表-如果当前和大于目标，则返回-否则，从当前元素开始（允许重复使用），递归地尝试添加元素代码实现：```pythondefcombinationSum(candidates,target):defbacktrack(start,path,target):iftarget==0:result.append(path[:])returniftarget<0:returnforiinrange(start,len(candidates)):path.append(candidates[i])backtrack(i,path,target-candidates[i])path.pop()result=[]backtrack(0,[],target)returnresult```复杂度分析：-时间复杂度：O(2^t)，其中t是目标值。在最坏情况下，我们需要尝试所有可能的组合。-空间复杂度：O(t)，递归调用栈的深度最多为t。18.N皇后问题（困难）题目描述：n皇后问题研究的是如何将n个皇后放置在n×n的棋盘上，并且皇后彼此之间不能相互攻击。给定一个整数n，返回所有不同的n皇后问题的解决方案。每一种解法包含一个明确的n皇后问题的棋子放置方案，该方案中'Q'和'.'分别代表了皇后和空位。示例：```输入：4输出：[[".Q..",//解法1"...Q","Q...","..Q."],["..Q.",//解法2"Q...","...Q",".Q.."]]解释:4皇后问题存在两个不同的解法。```解答思路：可以使用回溯算法来解决N皇后问题。具体步骤如下：1.使用一个数组来存储每一行皇后的列位置2.使用三个集合来标记哪些列、主对角线和副对角线上已经有皇后3.递归地尝试在每个位置放置皇后：-如果当前位置可以放置皇后（即不在已占用的列、主对角线和副对角线上），则放置皇后，并标记相应的位置-然后递归地在下一行尝试放置皇后-如果成功放置了所有皇后，则将当前方案加入结果列表-回溯：移除当前皇后，并取消标记代码实现：```pythondefsolveNQueens(n):defbacktrack(row):ifrow==n:result.append(["".join(row)forrowinboard])returnforcolinrange(n):ifcolincolsorrow-colindiag1orrow+colindiag2:continuecols.add(col)diag1.add(row-col)diag2.add(row+col)board[row][col]='Q'backtrack(row+1)board[row][col]='.'cols.remove(col)diag1.remove(row-col)diag2.remove(row+col)result=[]board=[['.'for_inrange(n)]for_inrange(n)]cols=set()diag1=set()主对角线，差值相同diag2=set()副对角线，和相同backtrack(0)returnresult```复杂度分析：-时间复杂度：O(n!)，虽然最坏情况下有n^n种可能，但通过剪枝，实际运行时间会大大减少。-空间复杂度：O(n)，我们使用了一些额外的空间来存储中间结果。七、哈希表类题目19.无重复字符的最长子串（中等）题目描述：给定一个字符串s，请你找出其中不含有重复字符的最长子串的长度。示例：```输入:s="abcabcbb"输出:3解释:因为无重复字符的最长子串是"abc"，所以其长度为3。```解答思路：可以使用滑动窗口和哈希表来解决这个问题。具体步骤如下：1.使用两个指针表示滑动窗口的左右边界2.使用一个哈希表来存储字符及其最近出现的位置3.遍历字符串，右指针向右移动：-如果当前字符不在哈希表中或不在当前窗口内，则将其加入哈希表，并更新最大长度-如果当前字符在窗口内，则移动左指针到哈希表中该字符的下一个位置，并更新哈希表中该字符的位置代码实现：```pythondeflengthOfLongestSubstring(s):char_map={}left=0max_length=0forrightinrange(len(s)):ifs[right]inchar_mapandchar_map[s[right]]>=left:left=char_map[s[right]]+1char_map[s[right]]=rightmax_length=max(max_length,right-left+1)returnmax_length```复杂度分析：-时间复杂度：O(n)，其中n是字符串的长度。我们只需要遍历字符串一次。-空间复杂度：O(min(m,n))，其中m是字符集的大小。在最坏情况下，我们需要存储所有字符。20.字母异位词分组（中等）题目描述：给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。示例：```输入:strs=["eat","tea","tan","ate","nat","bat"]输出:[["bat"],["nat","tan"],["ate","eat","tea"]]```解答思路：可以使用哈希表来分组字母异位词。具体步骤如下：1.遍历字符串数组，对每个字符串进行排序，得到排序后的字符串作为键2.将原字符串添加到以排序后字符串为键的列表中3.返回哈希表中的所有值代码实现：```pythonfromcollectionsimportdefaultdictdefgroupAnagrams(strs):groups=defaultdict(list)forsinstrs:sorted_s=''.join(sorted(s))groups[sorted_s].append(s)returnlist(groups.values())```复杂度分析：-时间复杂度：O(nklogk)，其中n是字符串数组的长度，k是字符串的最大长度。我们需要对每个字符串进行排序。-空间复杂度：O(nk)，我们需要存储所有字符串。八、贪心算法类题目21.跳跃游戏（中等）题目描述：给定一个非负整数数组nums，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。示例：```输入：nums=[2,3,1,1,4]输出：true解释：可以先跳1步，从下标0到达下标1,然后再从下标1跳3步到达最后一个下标。```解答思路：可以使用贪心算法来解决这个问题。我们维护一个变量max_reach，表示当前能够到达的最远位置。遍历数组，对于每个位置i：1.如果i>max_reach，表示无法到达当前位置，返回false2.否则，更新max_reach=max(max_reach,i+nums[i])3.如果max_reach已经能够到达数组的最后一个位置，返回true代码实现：```pythondefcanJump(nums):max_reach=0n=len(nums)foriinrange(n):ifi>max_reach:returnFalsemax_reach=max(max_reach,i+nums[i])ifmax_reach>=n-1:returnTruereturnmax_reach>=n-1```复杂度分析：-时间复杂度：O(n)，其中n是数组的长度。我们只需要遍历数组一次。-空间复杂度：O(1)，我们只使用了常数个额外的空间。22.加油站（中等）题目描述：在一条环路上有n个加油站，其中第i个加油站有汽油gas[i]升。你有一辆油箱容量无限的汽车，从第i个加油站开往第i+1个加油站需要消耗汽油cost[i]升。你从其中的一个加油站出发，油箱为空。如果你可以绕环路行驶一周，则返回出发时加油站的索引，否则返回-1。示例：```输入:gas=[1,2,3,4,5],cost=[3,4,5,1,2]输出:3解释:从3号加油站出发，可获得4升汽油。此时油箱有=0+4=4升汽油开往4号加油站，消耗1升汽油，油箱有=4-1=3升汽油开往0号加油站，消耗2升汽油，油箱有=3-2=1升汽油开往1号加油站，消耗3升汽油，油箱有=1-3=-2升汽油开往2号加油站，你无法到达，因为它需要消耗5升汽油，但此时油箱只有-2升汽油。```解答思路：可以使用贪心算法来解决这个问题。首先，如果总汽油量小于总消耗量，那么无论如何都无法绕环路一周，直接返回-1。否则，一定存在一个起点可以从那里出发绕环路一周。我们可以遍历每个加油站，尝试从那里出发：1.初始化当前油量为02.遍历每个加油站：-更新当前油量：current_gas+=gas[i]-cost[i]-如果当前油量小于0，则无法到达下一个加油站，重置当前油量为0，并尝试从下一个加油站出发代码实现：```pythondefcanCompleteCircuit(gas,cost):total_gas=sum(gas)total_cost=sum(cost)iftotal_gas<total_cost:return-1current_gas=0start_index=0foriinrange(len(gas)):current_gas+=gas[i]-cost[i]ifcurrent_gas<0:current_gas=0start_index=i+1returnstart_index```复杂度分析：-时间复杂度：O(n)，其中n是加油站的个数。我们只需要遍历数组一次。-空间复杂度：O(1)，我们只使用了常数个额外的空间。23.分发糖果（困难）题目描述：老师想给孩子们分发糖果，有n个孩子站成一条直线，老师会根据每个孩子的表现来给他们打分。你需要按照以下要求，给这些孩子分发糖果：每个孩子至少分配到1个糖果。相邻的孩子中，评分高的孩子必须获得更多的糖果。那么这样老师至少需要准备多少颗糖果呢？示例：```输入:[1,0,2]输出:5解释:你可以分别给这三个孩子分发2、1、2颗糖果。```解答思路：可以使用贪心算法来解决这个问题。我们需要考虑两个方向：1.从左到右遍历，如果当前孩子的评分高于前一个孩子，则当前孩子的糖果数=前一个孩子的糖果数+12.从右到左遍历，如果当前孩子的评分高于后一个孩子，则当前孩子的糖果数=max(当前孩子的糖果数,后一个孩子的糖果数+1)最终结果是所有孩子糖果数的和。代码实现：```pythondefcandy(ratings):n=len(ratings)candies=[1]n从左到右遍历foriinrange(1,n):ifratings[i]>ratings[i-1]:candies[i]=candies[i-1]+1从右到左遍历foriinrange(n-2,-1,-1):ifratings[i]>ratings[i+1]:candies[i]=max(candies[i],candies[i+1]+1)returnsum(candies)```复杂度分析：-时间复杂度：O(n)，其中n是孩子的数量。我们需要两次遍历数组。-空间复杂度：O(n)，我们使用了一个数组来存储每个孩子的糖果数。九、位运算类题目24.只出现一次的数字（简单）题目描述：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现一次的元素。示例：```输入:[4,1,2,1,2]输出:4```解答思路：可以使用异或运算来解决这个问题。异或运算有以下性质：-a^a=0-a^0=a-异或运算满足交换律和结合律因此，我们可以将数组中的所有元素进行异或运算，最终的结果就是只出现一次的数字。代码实现：```pythondefsingleNumber(nums):result=0fornuminnums:result^=numreturnresult```复杂度分析：-时间复杂度：O(n)，其中n是数组的长度。我们只需要遍历数组一次。-空间复杂度：O(1)，我们只使用了常数个额外的空间。25.数字的补数（简单）题目描述：给定一个正整数，输出它的补数。补数是对该数的二进制表示取反。示例：```输入:5输出:2解释:5的二进制表示为101（没有前导零），其补数为010。所以你需要输出2。```解答思路：可以使用位运算来解决这个问题。首先找到与给定数字位数相同的全1的数，然后与给定数字进行异或运算，得到补数。具体步骤如下：1.找到与给定数字位数相同的全1的数：mask=12.当mask小于给定数字时，将mask左移一位3.将mask减1，得到全1的数4.将给定数字与这个全1的数进行异或运算，得到补数代码实现：```pythondeffindComplement(num):mask=1whilemask<num:mask=(mask<<1)|1returnnum^mask```复杂度分析：-时间复杂度：O(logn)，其中n是给定数字的大小。我们需要找到与给定数字位数相同的全1的数。-空间复杂度：O(1)，我们只使用了常数个额外的空间。26.两个整数之和（中等）题目描述：不使用运算符+和-，计算两整数a、b之和。示例：```输入:a=1,b=2输出:3```解答思路：可以使用位运算来模拟加法运算。具体步骤如下：1.计算不考虑进位的和：a^b2.计算进位：a&b，然后左移一位3.将不考虑进位的和与进位相加，重复上述步骤，直到进位为0代码实现：```pythondefgetSum(a,b):32位整数掩码mask=0xFFFFFFFF循环直到进位为0whileb!=0:计算不考虑进位的和sum_without_carry=a^b计算进位carry=(a&b)<<1更新a和ba=sum_without_carry&maskb=carry&mask处理负数情况ifa>0x7FFFFFFF:a=~(a^mask)returna```复杂度分析：-时间复杂度：O(1)，虽然有一个循环，但循环次数最多为32次（32位整数）。-空间复杂度：O(1)，我们只使用了常数个额外的空间。十、栈和队列类题目27.有效的括号（简单）题目描述：给定一个只包括'('，')'，'{'，'}'，'['，']'的字符串，判断字符串是否有效。有效字符串需满足：-左括号必须用相同类型的右括号闭合。-左括号必须以正确的顺序闭合。-注意空字符串可被认为是有效字符串。示例：```输入:"()[]{}"输出:true```解答思路：可以使用栈来解决这个问题。具体步骤如下：1.创建一个栈2.遍历字符串，对于每个字符：-如果是左括号，则将其入栈-如果是右括号，则检查栈顶元素是否是匹配的左括号：-如果是，则弹出栈顶元素-如果不是，则返回false3.遍历完成后，如果栈为空，则返回true；否则返回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)，最坏情况下，栈中可能存储O(n)个字符。28.最小栈（中等）题目描述：设计一个支持push，pop，top操作，并能在常数时间内检索到最小元素的栈。-push(x)——将元素x推入栈中。-pop()——删除栈顶的元素。-top()——获取栈顶元素。-getMin()——检索栈中的最小元素。示例：```MinStackminStack=newMinStack();minStack.push(-2);minStack.push(0);minStack.push(-3);minStack.getMin();-->返回-3.minStack.pop();minStack.top();-->返回0.minStack.getMin();-->返回-2.```解答思路：可以使用两个栈来实现最小栈：一个主栈用于存储所有元素，一个辅助栈用于存储最小值。具体步骤如下：1.push(x)：将x压入主栈；如果辅助栈为空或x小于等于辅助栈顶元素，则将x压入辅助栈2.pop()：从主栈弹出元素；如果弹出的元素等于辅助栈顶元素，则从辅助栈弹出元素3.top()：返回主栈顶元素4.getMin()：返回辅助栈顶元素代码实现：```pythonclassMinStack:def__init__(self):self.stack=[]self.min_stack=[]defpush(self,x):self.stack.append(x)ifnotself.min_stackorx<=self.min_stack[-1]:self.min_stack.append(x)defpop(self):ifself.stack[-1]==self.min_stack[-1]:self.min_stack.pop()returnself.