【leetcode10-21】子串、普通数组、矩阵
子串560.和为K的子数组【没理解】
https://img-blog.csdnimg.cn/direct/beabf5e888ce4a25914444ed46d1cbde.png
什么是前缀和：前缀和指一个数组的某下标之前的所有数组元素的和（包含其自身）
通常，会在前缀和首位放一个0。比如数组
前缀和通常可以帮助我们快速计算某个区间内的和。比如我们要算i,ji,ji,j之间的和，那么就是nums+nums+⋯+numsnums
[*]nums + \cdots +numsnums+nums+⋯+nums。他可以看作是nums+nums+⋯+nums+nums+⋯+numsnums
[*]nums + \cdots + nums + nums + \cdots +numsnums+nums+⋯+nums+nums+⋯+nums减去nums+nums+⋯+numsnums
[*]nums + \cdots + numsnums+nums+⋯+nums。这个式子也是preSum−preSumpreSum
[*]preSumpreSum−preSum。
class Solution:
def subarraySum(self, nums: List, k: int) -> int:
# 要求的连续子数组
count = 0
n = len(nums)
preSum =
# 求前缀和数组，第i位置代表nums前面i个相加，共有len(nums)+1长
tmp = 0
for i in range(n):
tmp += nums
preSum.append(tmp)
# 求和为k的连续子数组，求i到j之间的和
for i in range(1, n+1):
for j in range(i, n+1):
if preSum - preSum == k:# preSum - preSum代表着在nums数组中，前j个数之和减去前i-1个数之和
count += 1
return count
class Solution:
def subarraySum(self, nums: List, k: int) -> int:
# 要求的连续子数组
count = 0
n = len(nums)
preSums = collections.defaultdict(int) #其键是前缀和，值是该前缀和出现的次数。
preSums = 1
presum = 0
for i in range(n):
presum += nums
# if preSums != 0:
count += preSums # 利用defaultdict的特性，当presum-k不存在时，返回的是0。这样避免了判断
preSums += 1# 给前缀和为presum的个数加1
return count
【暴力解法】
class Solution:
def subarraySum(self, nums: List, k: int) -> int:
# 要求的连续子数组
count = 0
n = len(nums)
for i in range(n):
sum = 0
for j in range(i, n):
sum += nums
if sum == k:
count += 1
return count
239.滑动窗口最大值【大顶堆】
https://img-blog.csdnimg.cn/direct/df254fcd650b4910b0218cec7372cc4f.png
代码随机录写过这道题：使用大顶堆
from collections import deque
class MyQueue: #单调队列（从大到小
def __init__(self):
self.queue = deque() #这里需要使用deque实现单调队列，直接使用list会超时
#每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出。
#同时pop之前判断队列当前是否为空。
def pop(self, value):
if self.queue and value == self.queue:
self.queue.popleft()#list.pop()时间复杂度为O(n),这里需要使用collections.deque()
#如果push的数值大于入口元素的数值，那么就将队列后端的数值弹出，直到push的数值小于等于队列入口元素的数值为止。
#这样就保持了队列里的数值是单调从大到小的了。
def push(self, value):
while self.queue and value > self.queue[-1]:
self.queue.pop()
self.queue.append(value)
#查询当前队列里的最大值 直接返回队列前端也就是front就可以了。
def front(self):
return self.queue
class Solution:
def maxSlidingWindow(self, nums: List, k: int) -> List:
que = MyQueue()
result = []
for i in range(k): #先将前k的元素放进队列
que.push(nums)
result.append(que.front()) #result 记录前k的元素的最大值
for i in range(k, len(nums)):
que.pop(nums) #滑动窗口移除最前面元素
que.push(nums) #滑动窗口前加入最后面的元素
result.append(que.front()) #记录对应的最大值
return result
76.最小覆盖子串【双指针|滑动窗口】【困难】
https://img-blog.csdnimg.cn/direct/f135c009a7fd4f08837f5653814a77e3.png
[*]用need字典维护，当前还需要的字符以及个数，need为负数，代表无需求，need代表需要
[*]滑动串口，先让right动起来，左指针指向队首，如果能cover字符T；就开始紧缩窗口，让left滑动，直至不能coverT
[*]在窗口滑动过程中，维护的need也要变，参加字符，就–，减去字符就+
如果实验访问一个在 defaultdict 中不存在的键，它会自动创建一个新键，并将其值设置为默认值（在这个例子中是 0）。但是{}不支持自动创建键
def minWindow(self, s: str, t: str) -> str:
need=collections.defaultdict(int)
for c in t:
need+=1
needCnt=len(t)
left=0
res=(0,float('inf'))
for index,c in enumerate(s):
if need>0:#如果需要字母c
needCnt-=1
need-=1
if needCnt==0: #步骤一：滑动窗口包含了所有T元素
while True: #步骤二：增加left，排除多余元素
c=s
if need==0:
break
need+=1
left+=1
if index-left<res-res: #记录结果，当前窗口左指针left，右指针index
res=(left,index)
need]+=1#步骤三：left增加一个位置，寻找新的满足条件滑动窗口
needCnt+=1
left+=1
return '' if res>len(s) else s:res+1] #如果res始终没被更新过，代表无满足条件的结果
普通数组
53.最大子数组和【动态规划】
https://img-blog.csdnimg.cn/direct/ba2f3c86a4914fcd9fb7a20c17eddc8e.png
https://img-blog.csdnimg.cn/direct/816b14bc6aa245d4b9871fdf1ef41aed.png
由于dp只与dp和nums有关，因此直接在nums原地修改，空间复杂度O(1)
class Solution:
def maxSubArray(self, nums: List) -> int:
for i in range(1,len(nums)):
nums = max(nums+nums,nums)
return max(nums)
56.合并区间
https://img-blog.csdnimg.cn/direct/48d834e9d6f24c9a9e47f7f37f55fc8f.png
[*]先对左节点排序
[*]判断当前合并区间和候选区间，是否重叠
class Solution:
def merge(self, intervals: List]) -> List]:
ans = []
intervals.sort()# 按照所有区间的左端点进行排序
for interval in intervals:
if not ans or ans[-1] < interval: #当ans为空，或者 当前区间的右节点 在 候选区间的左边【无重叠】
ans.append(interval)
else: #当前并区间和候选区间有重叠
ans[-1] = max(interval,ans[-1]) #取最大右区间
return ans
189.轮转数组
https://img-blog.csdnimg.cn/direct/6e8ce50def3d4ed8a1b62145d29d6910.png
直接用nums会报错？？
修改nums[:]不会影响到nums,nums[;]是一个新列表，是nums的副本，她两指向差别内存地点
class Solution:
def rotate(self, nums: List, k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
k = k % len(nums)
nums[:] = nums + nums[:len(nums)-k]
return nums
238.除自身以外数组的乘积
https://img-blog.csdnimg.cn/direct/875b13f4bdc74e4eb69918e3df41dbc5.png
https://img-blog.csdnimg.cn/direct/cf1c79dab25340f092ce181d2cd00712.png
[*]先初始化ans，ans=1；辅助变量temp=1
[*]计算下三角，计算上三角乘积temp，并乘以上三角
索引容易搞错，可以看个图，根据图写索引
class Solution:
def productExceptSelf(self, nums: List) -> List:
ans = * len(nums)
temp = 1
for i in range(1,len(nums)):
ans = ans * nums#下三角
for j in range(len(nums)-2,-1,-1):
temp *= nums #上三角
ans *= temp #下三角 * 上三角
return ans
41.缺失的第一个正数【困难】
https://img-blog.csdnimg.cn/direct/fcaeaef2eb3a4637a38ba1ba56c30169.png
最后的结果肯定是在 内
修改 nums，使对应的下标 里 nums 第一个不是 i+1 的，i+1 就是答案
也就是，让 nums 里的数字，在 内的，都去他们对应的 位置上去的
class Solution:
def firstMissingPositive(self, nums: List) -> int:
n = len(nums)
for i in range(n):
while 1 <= nums <= n and nums - 1] != nums:
# 这是错误的
# nums, nums - 1] = nums - 1], nums
#先计算右边的值，也就是nums和nums - 1]的值，然后将他们赋值给一个临时元祖；
#然后按顺序赋值给左边，也就是说会先修改nums的值，这样一来，nums - 1就不是原来想要修改的下标了。
nums - 1], nums = nums, nums - 1]
for i in range(n):
if nums != i + 1:
return i + 1
return n + 1
矩阵
73.矩阵置0
https://img-blog.csdnimg.cn/direct/ac17cd5bd77242e7bd4d55e84e95243d.png
两遍扫matrix,第一遍用集合记录哪些行,哪些列有0;第二遍置0
class Solution:
def setZeroes(self, matrix: List]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
row = len(matrix)
col = len(matrix)
row_zero = set()
col_zero = set()
for i in range(row):
for j in range(col):
if matrix == 0:
row_zero.add(i)
col_zero.add(j)
for i in range(row):
for j in range(col):
if i in row_zero or j in col_zero:
matrix = 0
54.螺旋矩阵
https://img-blog.csdnimg.cn/direct/7cb2da980a2848a4844925ee6e28a498.png
https://img-blog.csdnimg.cn/direct/b757d7b659534668b424fe417141bf66.png
class Solution:
def spiralOrder(self, matrix: List]) -> List:
if not matrix: return []
left, right, top, bottom = 0, len(matrix) - 1, 0, len(matrix) - 1
res = []
while True:
for i in range(left, right + 1):
res.append(matrix) #从左上角 到 右上角
top += 1
if top > bottom:
break
for i in range(top, bottom + 1):
res.append(matrix) # 从右上角 到 右下角
right -= 1
if left > right:
break
for i in range(right, left - 1, -1):
res.append(matrix) # 从右下角 到左下角
bottom -= 1
if top > bottom:
break
for i in range(bottom, top - 1, -1):
res.append(matrix) #从左下角 到 左上角
left += 1
if left > right:
break
return res
48.旋转图像
https://img-blog.csdnimg.cn/direct/3a5ab915934c491dade1d2750952a47e.png
https://img-blog.csdnimg.cn/direct/74e061dfa5b244dea4bd1b0fa813d12f.png
方法一：借助一个辅助矩阵temp暂存原矩阵
方法二：原地修改。一轮可以完成矩阵 4 个元素的旋转。因而，只要分别以矩阵左上角 1/41/41/4 的各元素为起始点实行以上旋转操纵，即可完整实现矩阵旋转。【当矩阵大小n为偶数，就取n//2行，n//2列原始为起始点；矩阵大小n为奇数，取前n//2行，(n+1)//2列为起始点
https://img-blog.csdnimg.cn/direct/7052e35853014e0b9d4c0b20002ed11a.png
class Solution:
def rotate(self, matrix: List]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
n = len(matrix)
temp = copy.deepcopy(matrix) # 深拷贝 matrix -> tmp
for i in range(n):
for j in range(n):
matrix = temp # 根据元素旋转公式，遍历修改原矩阵 matrix 的各元素
class Solution:
def rotate(self, matrix: List]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
n = len(matrix)
for i in range(n//2):
for j in range((n+1)//2):
temp = matrix
matrix = matrix
matrix = matrix
matrix = matrix
matrix = temp
240.搜刮二维矩阵||
https://img-blog.csdnimg.cn/direct/270b19c19e274530a1d74b3776e21ee0.png
https://img-blog.csdnimg.cn/direct/5f705eabfa5441d9b589beade6ec7185.png
class Solution:
def searchMatrix(self, matrix: List], target: int) -> bool:
i, j = len(matrix)-1, 0
while i>=0 and j < len(matrix):
if matrix < target:
j += 1
elif matrix > target:
i -= 1
else:
return True
return False
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]