本文目录
数列
两数之和
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
# 利用hash表，O(n)时间复杂度，O(n)空间复杂度
d = {}
for i, n in enumerate(nums):
m = target - n
if m in d:
return [d[m], i]
else:
d[n] = i
三数之和
思路：先排序，然后固定一个数再使用双指针。
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
res = []
nums.sort()
for i in range(len(nums)-2):
if i > 0 and nums[i] == nums[i-1]:
continue
l, r = i+1, len(nums)-1
while l < r:
s = nums[i] + nums[l] + nums[r]
if s < 0:
l += 1
elif s > 0:
r -= 1
else:
res.append((nums[i], nums[l], nums[r]))
while l < r and nums[l] == nums[l+1]: # 跳过相等的元素
l += 1
while l < r and nums[r] == nums[r-1]:
r -= 1
l += 1
r -= 1
return res
四数之和
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
def findNsum(l, r, target, N, result, results):
# early termination
if r-l+1 < N or N < 2 or target < nums[l]*N or target > nums[r]*N:
return
if N == 2: # two pointers solve sorted 2-sum problem
while l < r:
s = nums[l] + nums[r]
if s == target:
results.append(result + [nums[l], nums[r]])
l += 1
while l < r and nums[l] == nums[l-1]:
l += 1
elif s < target:
l += 1
else:
r -= 1
else: # recursively reduce N
for i in range(l, r+1):
if i == l or (i > l and nums[i-1] != nums[i]):
findNsum(i+1, r, target-nums[i],
N-1, result+[nums[i]], results)
nums.sort()
results = []
findNsum(0, len(nums)-1, target, 4, [], results)
return results
除自身以外数组的乘积
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
qian_zhui = [] # 前缀乘积，qian_zhui[i]表示nums[:i]的累积
s = 1
for i in range(len(nums)):
qian_zhui.append(s)
s *= nums[i]
hou_zhui = [] # hou_zhui[i]表示nums[i+1:]的累积
s = 1
for x in reversed(nums):
hou_zhui.append(s)
s *= x
hou_zhui.reverse()
return [x*y for x, y in zip(qian_zhui, hou_zhui)]
删除排序数组中的重复项
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
if not nums:
return 0
i = 0
for j in range(1, len(nums)):
if nums[j] != nums[i]:
i += 1
nums[i] = nums[j]
return i+1
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
i = 0
for n in nums:
if i < 2 or n > nums[i-2]:
nums[i] = n
i += 1
return i
盛最多水的容器
使用贪心的思路，每次将短板移动一个单位。
class Solution:
def maxArea(self, height: List[int]) -> int:
i, j, res = 0, len(height)-1, 0
while i < j:
if height[i] >= height[j]:
res = max(res, height[j]*(j-i))
j -= 1
elif height[i] < height[j]:
res = max(res, height[i]*(j-i))
i += 1
return res
螺旋矩阵
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
res = []
while matrix:
res += matrix.pop(0)
matrix = list(map(list, zip(*matrix)))[::-1]
return res
合并两个有序数组
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
p1 = m - 1
p2 = n - 1
# set pointer for nums1
p = m + n - 1
# while there are still elements to compare
while p1 >= 0 and p2 >= 0:
if nums1[p1] < nums2[p2]:
nums1[p] = nums2[p2]
p2 -= 1
else:
nums1[p] = nums1[p1]
p1 -= 1
p -= 1
# add missing elements from nums2
nums1[:p2 + 1] = nums2[:p2 + 1]
接雨水
class Solution:
def trap(self, height: List[int]) -> int:
if not height:
return 0
left_max = [0]*len(height)
right_max = [0]*len(height)
left_max[0] = height[0]
for i in range(1, len(height)):
left_max[i] = max(height[i], left_max[i-1])
right_max[-1] = height[-1]
for i in range(len(height)-2, -1, -1):
right_max[i] = max(height[i], right_max[i+1])
res = 0
for l, r, h in zip(left_max, right_max, height):
res += (min(l, r) - h)
return res
乘积最大子序列
class Solution:
def maxProduct(self, nums: List[int]) -> int:
# 如果序列中没有0存在，那么乘积最大子序列必定是从开头开始的 或者终点在数组末尾
nums_reversed = nums[::-1]
for i in range(1, len(nums)):
nums[i] *= nums[i-1] or 1
nums_reversed[i] *= nums_reversed[i-1] or 1
return max(nums+nums_reversed)
求众数
class Solution:
def majorityElement(self, nums: List[int]) -> int:
nums.sort()
mid = len(nums)//2
return nums[mid]
旋转数组
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
# 进行k次旋转
# n = len(nums)
# k %= n
# for _ in range(k):
# nums.insert(0, nums.pop())
n = len(nums)
k %= n
self.reverse(nums, 0, n-1)
self.reverse(nums, 0, k-1)
self.reverse(nums, k, n-1)
def reverse(self, nums, start, end):
while start < end:
nums[start], nums[end] = nums[end], nums[start]
start += 1
end -= 1
递增的三元子序列
class Solution:
def increasingTriplet(self, nums: List[int]) -> bool:
first = second = float('inf')
for n in nums:
if n <= first:
first = n
elif n <= second:
second = n
else:
return True
return False
数组中的第K个最大元素
import heapq
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
# 1.直接排序 O(NlogN)
# return sorted(nums, reverse=True)[k-1]
# 2.1利用堆 O(nlogk)
# 创建一个大顶堆，遍历所有的元素，在保持堆的大小为k
# 的情况下尝试将遍历的元素加入堆中
# 最后堆顶的元素就是正确答案。
# return heapq.nlargest(k, nums)[-1]
# 2.2不利用nlargest这个函数的话
# max_heap = nums[:k]
# heapq.heapify(max_heap) # 这个操作O(k)
# for num in nums[k:]: # 这个操作是 O((n-k)*logk)
# if num > max_heap[0]: # 大于最大堆中的最小元素
# heapq.heappop(max_heap)
# heapq.heappush(max_heap, num)
# return max_heap[0]
# 2.3还可以对全体元素建堆
# nums = [-num for num in nums]
# heapq.heapify(nums) # O(n)
# res = None
# for _ in range(k): # O(k*logn)
# res = heapq.heappop(nums)
# return -res
# 3.1递归，利用快排的思想，平均情况下为O(n),
# 平均情况就是每次取的val刚好能把数列分为两半
# 最坏的情况下要达到 O(n^2)
# if k == 1:
# return max(nums)
# partion操作
# val = nums[0]
# less, bigger = [], []
# for n in nums[1:]:
# if n >= val:
# bigger.append(n)
# else:
# less.append(n)
# m = len(bigger)
# if m == (k-1):
# return val
# elif m > (k-1):
# return self.findKthLargest(bigger, k)
# else:
# return self.findKthLargest(less, k-m-1)
# 3.2 直接在nums在操作，不使用额外的空间
pos = self.partition(nums, 0, len(nums)-1)
if pos > len(nums) - k:
return self.findKthLargest(nums[:pos], k-(len(nums)-pos))
elif pos < len(nums) - k:
return self.findKthLargest(nums[pos+1:], k)
else:
return nums[pos]
def partition(self, nums, left, right):
pivot = left
for i in range(left, right+1):
if nums[i] < nums[left]:
pivot += 1
nums[i], nums[pivot] = nums[pivot], nums[i]
nums[left], nums[pivot] = nums[pivot], nums[left]
return pivot
字符串
无重复字符的最长子串
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
used = {} # 保存字符到其索引的映射
max_length = start = 0
for i, c in enumerate(s):
if c in used and start <= used[c]:
start = used[c] + 1
else:
max_length = max(max_length, i - start + 1)
used[c] = i
return max_length
字符串中的第一个唯一字符
import collections
class Solution:
def firstUniqChar(self, s: str) -> int:
count = collections.Counter(s)
# find the index
for i, ch in enumerate(s):
if count[ch] == 1:
return i
return -1
最长公共前缀
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
res = ""
for chars in zip(*strs):
if len(set(chars)) == 1:
res += chars[0]
else:
break
return res
字符串的排列
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列：
from collections import Counter
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
c1 = Counter(s1)
for i in range(len(s2)-len(s1)+1):
c2 = Counter(s2[i:i+len(s1)])
if c1 == c2:
return True
return False
字符串相加
class Solution:
def addStrings(self, num1: str, num2: str) -> str:
res = ""
i, j, carry = len(num1) - 1, len(num2) - 1, 0
while i >= 0 or j >= 0:
n1 = int(num1[i]) if i >= 0 else 0
n2 = int(num2[j]) if j >= 0 else 0
tmp = n1 + n2 + carry
carry = tmp // 10
res = str(tmp % 10) + res
i, j = i - 1, j - 1
return "1" + res if carry else res
字符串相乘
class Solution:
def multiply(self, num1: str, num2: str) -> str:
res = [0] * (len(num1) + len(num2))
for i, e1 in enumerate(reversed(num1)):
for j, e2 in enumerate(reversed(num2)):
res[i+j] += int(e1) * int(e2)
res[i+j+1] += res[i+j]//10
res[i+j] %= 10
while len(res) > 1 and res[-1] == 0:
res.pop()
return ''.join(map(str, res[::-1]))
简化路径
class Solution:
def simplifyPath(self, path: str) -> str:
stack = []
path = path.split("/")
for item in path:
if item == "..":
if stack:
stack.pop()
elif item and item != ".":
stack.append(item)
return "/" + "/".join(stack)
复原IP地址
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
res = []
self.helper(s, 0, "", res)
return res
def helper(self, s, index, path, res):
if index == 4:
if not s:
res.append(path[:-1])
return
for i in range(1, 4):
if i <= len(s):
if int(s[:i]) < 256:
self.helper(s[i:], index+1, path+s[:i]+'.', res)
if s[0] == '0':
break