leetcode题目及答案解析

leetcode题目及答案解析引言LeetCode是一个广受欢迎的在线编程平台，它提供了大量的算法和数据结构相关的题目，涵盖了各种难度级别，从简单到困难。在这个平台上练习编程题目可以帮助我们提升算法思维、编程能力和解决实际问题的能力。本文将选取一些具有代表性的LeetCode题目进行详细的分析和解答，涉及数组、链表、树、动态规划等多个领域。数组相关题目题目1：两数之和-题目描述：给定一个整数数组`nums`和一个目标值`target`，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。-示例：```给定nums=[2,7,11,15],target=9因为nums[0]+nums[1]=2+7=9所以返回[0,1]```-解题思路：可以使用哈希表来解决这个问题。遍历数组，对于每个元素`num`，计算`target-num`的值，然后检查该值是否在哈希表中。如果存在，则说明找到了两个数的和为`target`，返回它们的下标；如果不存在，则将当前元素和其下标存入哈希表中。-代码实现：```pythondeftwoSum(nums,target):hashmap={}fori,numinenumerate(nums):complement=target-numifcomplementinhashmap:return[hashmap[complement],i]hashmap[num]=ireturn[]nums=[2,7,11,15]target=9print(twoSum(nums,target))```-复杂度分析：时间复杂度为$O(n)$，其中$n$是数组的长度。因为只需要遍历数组一次，每次查找哈希表的时间复杂度为$O(1)$。空间复杂度为$O(n)$，主要用于存储哈希表。题目2：删除排序数组中的重复项-题目描述：给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用$O(1)$额外空间的条件下完成。-示例：```给定数组nums=[1,1,2],函数应该返回新的长度2,并且原数组nums的前两个元素被修改为1,2。你不需要考虑数组中超出新长度后面的元素。```-解题思路：使用双指针法。定义两个指针`i`和`j`，`i`用于记录不重复元素的位置，`j`用于遍历数组。当`nums[j]`不等于`nums[i]`时，将`nums[j]`的值赋给`nums[i+1]`，然后`i`指针向后移动一位。-代码实现：```pythondefremoveDuplicates(nums):ifnotnums:return0i=0forjinrange(1,len(nums)):ifnums[j]!=nums[i]:i+=1nums[i]=nums[j]returni+1nums=[1,1,2]print(removeDuplicates(nums))```-复杂度分析：时间复杂度为$O(n)$，其中$n$是数组的长度。因为只需要遍历数组一次。空间复杂度为$O(1)$，只使用了常数级的额外空间。链表相关题目题目3：反转链表-题目描述：反转一个单链表。-示例：```输入:1->2->3->4->5->NULL输出:5->4->3->2->1->NULL```-解题思路：可以使用迭代或递归的方法来反转链表。迭代方法的思路是遍历链表，将每个节点的`next`指针指向前一个节点。-代码实现（迭代）：```pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefreverseList(head):prev=Nonecurr=headwhilecurr:next_node=curr.nextcurr.next=prevprev=currcurr=next_nodereturnprev创建链表1->2->3->4->5head=ListNode(1)head.next=ListNode(2)head.next.next=ListNode(3)head.next.next.next=ListNode(4)head.next.next.next.next=ListNode(5)new_head=reverseList(head)打印反转后的链表whilenew_head:print(new_head.val,end="->")new_head=new_head.nextprint("NULL")```-复杂度分析：时间复杂度为$O(n)$，其中$n$是链表的长度。因为需要遍历链表一次。空间复杂度为$O(1)$，只使用了常数级的额外空间。题目4：合并两个有序链表-题目描述：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。-示例：```输入：1->2->4,1->3->4输出：1->1->2->3->4->4```-解题思路：使用递归或迭代的方法。迭代方法的思路是创建一个虚拟头节点`dummy`，然后比较两个链表的节点值，将较小的节点添加到新链表中，直到其中一个链表遍历完，最后将另一个链表的剩余部分添加到新链表的末尾。-代码实现（迭代）：```pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefmergeTwoLists(l1,l2):dummy=ListNode(0)curr=dummywhilel1andl2:ifl1.val<l2.val:curr.next=l1l1=l1.nextelse:curr.next=l2l2=l2.nextcurr=curr.nextifl1:curr.next=l1ifl2:curr.next=l2returndummy.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_head=mergeTwoLists(l1,l2)打印合并后的链表whilemerged_head:print(merged_head.val,end="->")merged_head=merged_head.nextprint("NULL")```-复杂度分析：时间复杂度为$O(m+n)$，其中$m$和$n$分别是两个链表的长度。因为需要遍历两个链表。空间复杂度为$O(1)$，只使用了常数级的额外空间。树相关题目题目5：二叉树的中序遍历-题目描述：给定一个二叉树，返回它的中序遍历。-示例：```输入:[1,null,2,3]1\2/3输出:[1,3,2]```-解题思路：中序遍历的顺序是左子树->根节点->右子树。可以使用递归或迭代的方法实现。递归方法比较简单，直接按照中序遍历的顺序递归遍历左子树、根节点和右子树。迭代方法使用栈来模拟递归过程。-代码实现（递归）：```pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefinorderTraversal(root):result=[]definorder(root):ifroot:inorder(root.left)result.append(root.val)inorder(root.right)inorder(root)returnresult创建二叉树root=TreeNode(1)root.right=TreeNode(2)root.right.left=TreeNode(3)print(inorderTraversal(root))```-复杂度分析：时间复杂度为$O(n)$，其中$n$是二叉树的节点数。因为需要遍历每个节点一次。空间复杂度为$O(h)$，其中$h$是二叉树的高度。在最坏情况下，二叉树退化为链表，空间复杂度为$O(n)$。题目6：二叉树的最大深度-题目描述：给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。-示例：```给定二叉树[3,9,20,null,null,15,7]，3/\920/\157返回它的最大深度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创建二叉树root=TreeNode(3)root.left=TreeNode(9)root.right=TreeNode(20)root.right.left=TreeNode(15)root.right.right=TreeNode(7)print(maxDepth(root))```-复杂度分析：时间复杂度为$O(n)$，其中$n$是二叉树的节点数。因为需要遍历每个节点一次。空间复杂度为$O(h)$，其中$h$是二叉树的高度。在最坏情况下，二叉树退化为链表，空间复杂度为$O(n)$。动态规划相关题目题目7：爬楼梯-题目描述：假设你正在爬楼梯。需要$n$阶你才能到达楼顶。每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定$n$是一个正整数。-示例：```输入：2输出：2解释：有两种方法可以爬到楼顶。1.1阶+1阶2.2阶```-解题思路：这是一个经典的动态规划问题。定义一个数组`dp`，其中`dp[i]`表示爬到第`i`阶楼梯的方法数。状态转移方程为`dp[i]=dp[i-1]+dp[i-2]`，因为到达第`i`阶楼梯可以从第`i-1`阶爬1个台阶到达，也可以从第`i-2`阶爬2个台阶到达。-代码实现：```pythondefclimbStairs(n):ifn<=2:returnndp=[0](n+1)dp[1]=1dp[2]=2foriinrange(3,n+1):dp[i]=dp[i-1]+dp[i-2]returndp[n]print(climbStairs(2))```-复杂度分析：时间复杂度为$O(n)$，因为需要遍历数组一次。空间复杂度为$O(n)$，主要用于存储`dp`数组。可以将空间复杂度优化到$O(1)$，只需要使用两个变量来记录`dp[i-1]`和`dp[i-2]`的值。题目8：最大子序和-题目描述：给定一个整数数组`nums`，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。-示例：```输入:[-2,1,-3,4,-1,2,1,-5,4],输出:6解释:连续子数组[4,-1,2,1]的和最大，为6。```-解题思路：使用动态规划的思想。定义一个数组`dp`，其中`dp[i]`表示以第`i`个元素结尾的连续子数组的最大和。状态转移方程为`dp[i]=max(dp[i-1]+nums[i],nums[i])`。最终的结果为`dp`数组中的最大值。-代码实现：```pythondefmaxSubArray(nums):ifnotnums:return0n=len(nums)dp=[0]ndp[0]=nums[0]max_