Fork me on GitHub

LeetCode题解-python

一、数组

1.两数之和

链接:https://leetcode-cn.com/problems/two-sum/

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

题解一(暴力):
最简单的思路就是通过两遍循环直接进行暴力破解,时间复杂度O(n^2),空间复杂度O(1)。

1
2
3
4
5
6
class Solution:
def twoSum(self,nums,target):
for i in range(0,len(nums)):
for j in range(i+1,len(nums)):
if nums[j]==target-nums[i]:
return i,j

题解二(hash):
接着思考如何进行优化,采用hash记录需要的key,遍历的时候找到需要的值。时间复杂度O(n),空间复杂度O(n)。

1
2
3
4
5
6
7
8
class Solution:
def twoSum(self,nums,target):
dicts={}
for i in range(len(nums)):
tmp=nums[i]
if target-tmp in dicts:
return (dicts[target-tmp],i)
dicts[tmp]=i

1
2
3
4
5
6
7
8
class Solution:
def twoSum(self,nums,target):
dicts={}
for i,num in enumerate(nums):
if num in dicts:
return [dicts[num],i]
else:
dicts[target-num]=i

题解三(切片):
判断target-nums[i]是否在nums[i+1:]中,时间复杂度O(n),空间复杂度O(1)。

1
2
3
4
5
class Solution:
def twoSum(self,nums,target):
for i in range(len(nums)):
if target-nums[i] in nums[i+1:]:
return [i,nums.index(target-nums[i],i+1)]

index()方法语法:list.index(x[, start[, end]])
参数:
x– 查找的对象。
start– 可选,查找的起始位置。
end– 可选,查找的结束位置。
返回值:该方法返回查找对象的索引位置,如果没有找到对象则抛出异常。

4.寻找两个有序数组的中位数

链接:https://leetcode-cn.com/problems/median-of-two-sorted-arrays/

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0
示例 2:

nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5

11.盛最多水的容器

链接:https://leetcode-cn.com/problems/container-with-most-water/

给定 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明:你不能倾斜容器,且 n 的值至少为 2。

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。

示例:

输入: [1,8,6,2,5,4,8,3,7]
输出: 49

思路:
矩阵的面积=矩阵长度 * 矩阵宽度
矩阵长度:两条垂直线的距离
矩阵宽度:两条垂直线中较短一条的长度
面积最大化:两条垂直线的距离越远越好,两条垂直线的最短长度也要越长越好。
解法一(暴力):
在这种情况下,我们将简单地考虑每对可能出现的线段组合并找出这些情况之下的最大面积。
时间复杂度O(n^2),计算n(n-1)/2种高度组合的面积,空间复杂度O(1)。

1
2
3
4
5
6
7
8
class Solution:
def maxArea(self, height: List[int]) -> int:
area=0

for i in range(len(height)):
for j in range(i+1,len(height)):
area=max(area,min(height[i],height[j])*(j-1))
return area

解法一(双指针):
设置两个指针 left 和 right,分别指向数组的最左端和最右端。此时,两条垂直线的距离是最远的,若要下一个矩阵面积比当前面积来得大,必须要把 height[left] 和 height[right] 中较短的垂直线往中间移动,看看是否可以找到更长的垂直线。
时间复杂度O(n),空间复杂度O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def maxArea(self, height: List[int]) -> int:
left=o
right=len(height)-1
area=0

while left < right:
cur=min(height[left],height[right]) * (right-left)
area=max(area,cur)

if height[left]<height[right]:
left+=1
else:
right-=1
return area

15.三数之和

链接:https://leetcode-cn.com/problems/3sum/

给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。

注意:答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4],

满足要求的三元组集合为:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

题解一(暴力):
使用三重循环进行暴力破解,时间复杂度为O(n^3),空间复杂度O(n)
题解二(排序+双指针):
继续思考如何优化,可以通过双指针动态消去无效解来优化效率。
铺垫:先将给定 nums 排序,复杂度为 O(nlogn)
思路:固定 3 个指针中最左(最小)数字的指针 k,双指针 i,j 分设在数组索引 (k, len(nums))两端,通过双指针交替向中间移动,记录对于每个固定指针 k 的所有满足 nums[k] + nums[i] + nums[j] == 0 的 i,j 组合。
时间复杂度O(n^2),空间复杂度O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
lens=len(nums)
res=[]

for k in range(lens):
if k>0 and nums[k]==nums[k-1]:
continue

i,j=k+1,lens-1
while i<j:
sum=nums[k]+nums[i]+nums[j]
if sum==0:
tmp=[nums[k],nums[i],nums[j]]
res.append(tmp)

while i<j and nums[i]==nums[i+1]:
i+=1
while i<j and nums[j]==nums[j-1]:
j-=1

i+=1
j-=1

elif sum<0:
i+=1
else:
j-=1

return res

16.最接近的三数之和

链接:https://leetcode-cn.com/problems/3sum-closest/

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

例如,给定数组 nums = [-1,2,1,-4], 和 target = 1.

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

题解一(排序+双指针):
思路类似于三数之和,首先将数组进行排序,同时在左右指针运动过程中,记录与 target 绝对值差值最小的三数之和。

时间复杂度:O(nlogn) + O(n^2) = O(n^2),空间复杂度O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
nums.sort()
length=len(nums)
res=float('inf')

for k in range(length):
# if k>0 and nums[k]==nums[k-1]:
# continue

i,j=k+1,length-1
while i<j:
sum=nums[k]+nums[i]+nums[j]
if sum==target:
return target

if abs(res-target)>abs(sum-target):
res=sum

if sum<target:
i+=1
else:
j-=1
return res

18.四数之和

链接:https://leetcode-cn.com/problems/4sum/

给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c + d 的值与 target 相等?找出所有满足条件且不重复的四元组。

注意:

答案中不可以包含重复的四元组。

示例:

给定数组 nums = [1, 0, -1, 0, -2, 2],和 target = 0。

满足要求的四元组集合为:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

题解一(排序+双指针):
和三数之和解法类似,先将数组排序固定两个元素,再用两个指针,一个指向头,一个指向尾,看四数之和为多少,太大了右指针左移,太小了左指针右移,因为有可能存在重复的数组,先将结果保存在set中,最后在转为list输出。

时间复杂度:O(n^3),空间复杂度O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
nums.sort()
length=len(nums)
res=[]
sets=set()

for i in range(length-3):
for j in range(i+1,length-2):
left,right=j+1,length-1

while left<right:
sum=nums[i]+nums[j]+nums[left]+nums[right]
if sum==target:
tmp=(nums[i],nums[j],nums[left],nums[right])
sets.add(tmp) # 去重
left+=1
right-=1
elif sum<target:
left+=1
else:
right-=1

for each in sets:
res.append(list(each))
return res

26.删除排序数组中的重复项

链接:https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/

给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。

不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1:

给定数组 nums = [1,1,2], 

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 

你不需要考虑数组中超出新长度后面的元素。
示例 2:

给定 nums = [0,0,1,1,1,2,2,3,3,4],

函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

你不需要考虑数组中超出新长度后面的元素。

题解一(双指针):
第一个指针 i :由于数组已完成排序,因为遍历数组,每遇到 nums[i] != nums[j
] ,就说明遇到了新的不同数字,记录之;
第二个指针 j :每遇到新的不同数字时,执行 j += 1 , j 指针有两个作用:

记录数组中不同数字的数量;
作为修改数组元素的索引index。

最终,返回 k+1 即可。
时间复杂度O(n),空间复杂福O(1)。

1
2
3
4
5
6
7
8
9
10
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
if not nums:
return 0
j=0
for i in range(1,len(nums)):
if nums[i]!=nums[j]:
nums[j+1]=nums[i]
j+=1
return j+1
1
2
3
4
5
6
7
8
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
pre,cur=0,1
while cur<len(nums):
if nums[pre]==nums[cur]:
nums.pop(cur)
else:
pre,cur=pre+1,cur+1

27.移除元素

链接:https://leetcode-cn.com/problems/remove-element/

给定一个数组 nums 和一个值 val,你需要原地移除所有数值等于 val 的元素,返回移除后数组的新长度。

不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1:

给定 nums = [3,2,2,3], val = 3,

函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。

你不需要考虑数组中超出新长度后面的元素。
示例 2:

给定 nums = [0,1,2,2,3,0,4,2], val = 2,

函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

注意这五个元素可为任意顺序。

你不需要考虑数组中超出新长度后面的元素。

题解一(双指针):
可以保留两个指针 i 和 j,其中 i 是慢指针,j 是快指针。当 nums[j]与val相等时,递增 j以跳过该元素。只要 nums[j] 不等于 val,我们就复制 nums[j]到 nums[i] 并同时递增两个索引。重复这一过程,直到 j 到达数组的末尾,该数组的新长度为 i。
时间复杂度O(n),空间复杂度O(1).

1
2
3
4
5
6
7
8
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
i=0
for j in range(0,len(nums)):
if nums[j] != val:
nums[i]=nums[j]
i+=1
return i

二、栈

链接:https://leetcode-cn.com/problems/trapping-rain-water/

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/youdao/water2.png

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。 感谢 Marcos 贡献此图。

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

思路: 求出每个柱子上面能够存多少水,然后将每根柱子的存水量相加便能得到总的存水量,为求出每根柱子上能够存多少水,就要求出每根柱子左边最高的和右边最高柱子,然后用两者的最小值减去当前柱子的高度。 例如图中从左到右第三根柱子的高度为0,它左边最高柱子的值为1,右边最高柱子的值为3,因此它的最大存水量为 Min(1,3)-0=1。

题解一(暴力):
利用上面的思路,从左到右遍历每根柱子,遍历的时候求出每根柱子左边最高和右边最高柱子的值,然后利用两者的最小值减去当前柱子的高度就行了。
时间复杂度O(n^2),空间复杂度O(1)。

注意:如果当前柱子大于它左右最大值的任何一个是存不了水的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
def trap(self, height: List[int]) -> int:
waters=0
length=len(height)

if height is None or length<2:
return 0

left,right=0,0
for i in range(length):
left,right=0,0
for j in range(i):
left=max(left,height[j])
for j in range(length-1,i,-1):
right=max(right,height[j])

tmp=min(left,right)
if tmp>height[i]:
waters+=tmp-height[i]
else:
waters+=0

return waters

题解二:
分析上面的算法发现算法的时间复杂度为O(n^2)。原因是对于每个元素都要从左到右,和从右到最左遍历其两边最大值,假如使用两个数组 left[ ] , right[ ]来保存每个元素左边最大值,右边最大值的话,这样就不用每次都遍历了,因此时间复杂度可以减少到O(n),但空间复杂度为O(n),典型的空间换时间算法。

对于数组[ 5, 2 , 6 , 2 , 4 ]
它的左数组:[5,5,6,6,6]
它的右数组:[4,4,6,6,6]

算法的流程:

从左到右遍历一次求出每个元素左边的最大值,保存在 left 数组中。 
从右到左遍历一次求出每个元素右边的最大值,保存在right数。
最后一次遍历求出每个元素(每根柱子)的存水量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
def trap(self, height: List[int]) -> int:
waters=0
length=len(height)

if height is None or length<2:
return 0
leftLargest,rightLargest=0,0
left,right=[0]*length,[0]*length

for i in range(length):
leftLargest=max(leftLargest,height[i])
left[i]=leftLargest

for i in range(length-1,-1,-1):
rightLargest=max(rightLargest,height[i])
right[i]=rightLargest

for i in range(length):
tmp=min(left[i],right[i])
if tmp>height[i]:
waters+=tmp-height[i]
else:
waters+=0

return waters

题解三:
改进解法2 :分析上面算法发现其实没有必要使用 left 数组,因为当从左到右遍历求存水量的过程中可以利用一个变量来保存当前元素左边的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
def trap(self, height: List[int]) -> int:
waters=0
length=len(height)

if height is None or length<2:
return 0
leftLargest,rightLargest=0,0
right=[0]*length

for i in range(length-1,-1,-1):
rightLargest=max(rightLargest,height[i])
right[i]=rightLargest

for i in range(length):
leftLargest=max(leftLargest,height[i])
tmp=min(leftLargest,right[i])
if tmp>height[i]:
waters+=tmp-height[i]
else:
waters+=0

return waters

题解四(双指针):
image

上面左右两边的黄色块分别表示当前元素左边最大值和右边最大值。

left ,right分别代表从左到右移动和从右到左移动的指针。

如果当前元素的左边最大值比右边最大值小,则left指针向右移动,否则right指针向左移动。

这种左右指针移动的目的是为了保证所求的左右最大值一定是当前元素的左右最大值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
def trap(self, height: List[int]) -> int:
waters=0
length=len(height)

if height is None or length<2:
return 0
leftLargest,rightLargest=0,0
left,right=0,length-1

while left<right:
leftLargest=max(leftLargest,height[left])
rightLargest=max(rightLargest,height[right])

if leftLargest > rightLargest:
waters+=rightLargest-height[right]
right-=1
else:
waters+=leftLargest-height[left]
left+=1

return waters
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def trap(height):
if not height: return 0
left = 0
right = len(height) - 1
res = 0
# 记录左右边最大值
left_max = height[left]
right_max = height[right]
while left < right:
if height[left] < height[right]:
if left_max > height[left]:
res += left_max - height[left]
else:
left_max = height[left]
left += 1
else:
if right_max > height[right]:
res += right_max - height[right]
else:
right_max = height[right]
right -= 1
return res

三、树

2.二叉树的中序遍历

链接:https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

给定一个二叉树,返回它的中序 遍历。

示例:

输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [1,3,2]
进阶: 递归算法很简单,你可以通过迭代算法完成吗?

支持,让我的文章更加优秀!