leetcode刷题,使用python
1, 两数之和—— 0001 数组
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
#用len()方法取得nums列表的长度
n = len(nums)
#x取值从0一直到n（不包括n）
for x in range(n):
#y取值从x+1一直到n（不包括n）
#用x+1是减少不必要的循环,y的取值肯定是比x大
for y in range(x+1,n):
#假如 target-nums[x]的某个值存在于nums中
if nums[y] == target - nums[x]:
#返回x和y
return x,y
class Solution2:
def twoSum(self, nums, target):
n = len(nums)
for i in range(n):
delt = target - nums[i]
if delt in nums:
y = nums.index(delt)
if y != i:
return [i, y]
#求差值、把差值存进字典里作为键、索引作为值，第一次循环理解：d[7]=0 即字典d={7:0}，表示为索引0需要数组里值为7的元素配对。
# if 判断是否为前面元素所需要配对的值 ， 是则返回两个索引值。（补充：nums[x] in d 是判断值是否在字典某个key里面）
class Solution3:
def twoSum(self, nums, target):
d = {}
n = len(nums)
for i in range(n):
rest = target - nums[i]
if nums[i] in d:
return d[nums[i]], i
else:
d[rest] = i
S = Solution3()
result = S.twoSum([1,2,3,4], 3)
print(result)
2, 寻找两个正序数组的中位数——0004 数组
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
from typing import List
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
nums = sorted(nums1 + nums2)
index1 = len(nums) // 2
if len(nums) % 2 == 0:
return (nums[index1] + nums[index1-1])/2
else:
return nums[index1]
S = Solution()
result = S.findMedianSortedArrays([1,3], [2])
print(result)
3, 解盛水最多的容器——0011 数组 双指针
题目描述
给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器。
示例1:
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
from typing import List
class Solution:
#双指针
def maxArea(self, height: List[int]) -> int:
left = 0
right = len(height) - 1
max_area = 0
while True:
if left == right:
break
cur_area = min(height[left], height[right]) * (right - left)
if height[left] > height[right]:
right -= 1
else:
left += 1
max_area = max(cur_area, max_area)
return max_area
S = Solution()
result = S.maxArea([1,8,6,2,5,4,8,3,7])
print(result)
4, 三数之和 —— 0015 数组 双指针+排序
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
from typing import List
class Solution:
#排序 + 双指针
def threeSum(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
nums.sort()
ans = list()
#枚举a
for first in range(n):
#a不重复
if first > 0 and nums[first] == nums[first-1]:
continue
third = n - 1
target = -nums[first]
#枚举b
for second in range(first+1, n):
# b不重复
if second > first+1 and nums[second] == nums[second-1]:
continue
while second < third and nums[second] + nums[third] > target:
third -= 1
if second == third:
break
if nums[second] + nums[third] == target:
ans.append([nums[first], nums[second], nums[third]])
return ans
S = Solution()
result = S.threeSum([-1,0,1,2,-1,-4])
print(result)
5, 最接近的三数之和——0016 数组 排序+双指针
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。
示例 1：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
from typing import List
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
nums.sort()
n = len(nums)
best = 10**7
# 根据差值的绝对值来更新答案
def update(cur):
nonlocal best
if abs(cur-target) < abs(best-target):
best = cur
#枚举a
for i in range(n):
if i > 0 and nums[i] == nums[i-1]:
continue
# 使用双指针枚举 b 和 c
j, k = i+1, n-1
while j<k:
s = nums[i] + nums[j] + nums[k]
if s == target:
return target
update(s)
if s > target:
# 如果和大于 target，移动 c 对应的指针
k0 = k - 1
while j < k0 and nums[k0] == nums[k]:
k0 -= 1
k = k0
else:
# 如果和小于 target，移动 b 对应的指针
j0 = j + 1
while j0 < k and nums[j0] == nums[j]:
j0 += 1
j = j0
return best
S = Solution()
nums = [-1,2,1,-4]
target = 1
result = S.threeSumClosest(nums, target)
print(result)
6 四数之和 —— 0018 数组+双指针 基本和三数之和相同
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：
输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]
from typing import List
class Solution:
def fourSum(self, nums:List[int], target:int) -> List[List[int]]:
n = len(nums)
if n < 4:
return []
elif n == 4:
return [nums,] if sum(nums) == target else []
res = []
nums.sort()
for i in range(n-3):
if i > 0 and nums[i] == nums[i-1]:
continue
if sum(nums[i:i+4]) > target:
break
if nums[i] + sum(nums[n-3:]) < target:
continue
for j in range(i+1, n-2):
if j > i+1 and nums[j]==nums[j-1]:
continue
if nums[i] + sum(nums[j:j+3]) > target:
break
if nums[i] + nums[j] + sum(nums[n-2:]) < target:
continue
# 双指针模板写法
left, right = j+1, n-1
while left < right:
total = nums[i] + nums[j] + nums[left] + nums[right]
if total == target:
res.append([nums[i], nums[j], nums[left], nums[right]])
while left < right and nums[left] == nums[left+1]:
left += 1
left += 1
while left < right and nums[right] == nums[right-1]:
right -= 1
right -= 1
elif total < target:
left += 1
elif total > target:
right -= 1
return res
S = Solution()
nums = [1,0,-1,0,-2,2]
target = 0
result = S.fourSum(nums, target)
print(result)
7, [删除有序数组中的重复项]——0026 快慢指针 数组
给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。
将最终结果插入 nums 的前 k 个位置后返回 k 。
不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例 1：
输入：nums = [1,1,2]
输出：2, nums = [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]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
from typing import List
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
if not nums:
return 0
n = len(nums)
fast = slow = 1
while fast < n:
if nums[fast] != nums[fast-1]:
nums[slow] = nums[fast]
slow += 1
fast += 1
return slow
S = Solution()
nums = [1,1,2]
result = S.removeDuplicates(nums)
print(result)
8,移除元素——0027 快慢指针 数组
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1：
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
示例 2：
输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
if not nums:
return -1
n = len(nums)
slow = -1
fast = 0
while fast < n:
if nums[fast] != val:
slow += 1
nums[slow] = nums[fast]
fast += 1
return slow+1
网友评论