【leetcode10-21】子串、普通数组、矩阵

子串

560.和为K的子数组【没理解】

   什么是前缀和：前缀和指一个数组的某下标之前的所有数组元素的和（包含其自身）
通常，会在前缀和首位放一个0。比如数组[1,2,3。其前缀和是[0,1,3,6]
前缀和通常可以帮助我们快速计算某个区间内的和。比如我们要算i,ji,ji,j之间的和，那么就是nums+nums[i+1]+⋯+nums[j]nums
  

• nums[i+1] + \cdots +nums[j]nums+nums[i+1]+⋯+nums[j]。他可以看作是nums[0]+nums[1]+⋯+nums+nums[i+1]+⋯+nums[j]nums[0]
  
• nums[1] + \cdots + nums + nums[i+1] + \cdots +nums[j]nums[0]+nums[1]+⋯+nums+nums[i+1]+⋯+nums[j]减去nums[0]+nums[1]+⋯+nums[i−1]nums[0]
  
• nums[1] + \cdots + nums[i-1]nums[0]+nums[1]+⋯+nums[i−1]。这个式子也是preSum[j]−preSum[i−1]preSum[j]
  

  

• preSum[i-1]preSum[j]−preSum[i−1]。
  

1. class Solution:
2.     def subarraySum(self, nums: List[int], k: int) -> int:
3.         # 要求的连续子数组
4.         count = 0
5.         n = len(nums)
6.         preSum = [0]
8.         # 求前缀和数组，第i位置代表nums前面i个相加，共有len(nums)+1长
9.         tmp = 0
10.         for i in range(n):
11.             tmp += nums[i]
12.             preSum.append(tmp)
13.         
14.         # 求和为k的连续子数组，求i到j之间的和
15.         for i in range(1, n+1):
16.             for j in range(i, n+1):
17.                 if preSum[j] - preSum[i-1] == k:  # preSum[j] - preSum[i-1]代表着在nums数组中，前j个数之和减去前i-1个数之和
18.                     count += 1
19.         
20.         return count

复制代码

1. class Solution:
2.     def subarraySum(self, nums: List[int], k: int) -> int:
3.         # 要求的连续子数组
4.         count = 0
5.         n = len(nums)
6.         preSums = collections.defaultdict(int)   #其键是前缀和，值是该前缀和出现的次数。
7.         preSums[0] = 1
9.         presum = 0
10.         for i in range(n):
11.             presum += nums[i]   
12.             # if preSums[presum - k] != 0:
13.             count += preSums[presum - k]   # 利用defaultdict的特性，当presum-k不存在时，返回的是0。这样避免了判断
14.             preSums[presum] += 1  # 给前缀和为presum的个数加1
15.         return count

复制代码

1. 【暴力解法】
2. class Solution:
3.     def subarraySum(self, nums: List[int], k: int) -> int:
4.         # 要求的连续子数组
5.         count = 0
6.         n = len(nums)
7.         
8.         for i in range(n):
9.             sum = 0
10.             for j in range(i, n):
11.                 sum += nums[j]
12.                 if sum == k:
13.                     count += 1
14.         return count

复制代码

239.滑动窗口最大值【大顶堆】

代码随机录写过这道题：使用大顶堆

1. from collections import deque
4. class MyQueue: #单调队列（从大到小
5.     def __init__(self):
6.         self.queue = deque() #这里需要使用deque实现单调队列，直接使用list会超时
7.    
8.     #每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出。
9.     #同时pop之前判断队列当前是否为空。
10.     def pop(self, value):
11.         if self.queue and value == self.queue[0]:
12.             self.queue.popleft()#list.pop()时间复杂度为O(n),这里需要使用collections.deque()
13.             
14.     #如果push的数值大于入口元素的数值，那么就将队列后端的数值弹出，直到push的数值小于等于队列入口元素的数值为止。
15.     #这样就保持了队列里的数值是单调从大到小的了。
16.     def push(self, value):
17.         while self.queue and value > self.queue[-1]:
18.             self.queue.pop()
19.         self.queue.append(value)
20.         
21.     #查询当前队列里的最大值 直接返回队列前端也就是front就可以了。
22.     def front(self):
23.         return self.queue[0]
24.    
25. class Solution:
26.     def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
27.         que = MyQueue()
28.         result = []
29.         for i in range(k): #先将前k的元素放进队列
30.             que.push(nums[i])
31.         result.append(que.front()) #result 记录前k的元素的最大值
32.         for i in range(k, len(nums)):
33.             que.pop(nums[i - k]) #滑动窗口移除最前面元素
34.             que.push(nums[i]) #滑动窗口前加入最后面的元素
35.             result.append(que.front()) #记录对应的最大值
36.         return result

复制代码

76.最小覆盖子串【双指针|滑动窗口】【困难】

   

• 用need字典维护，当前还需要的字符以及个数，need为负数，代表无需求，need代表需要
  
• 滑动串口，先让right动起来，左指针指向队首，如果能cover字符T；就开始紧缩窗口，让left滑动，直至不能coverT
  
• 在窗口滑动过程中，维护的need也要变，参加字符，就–，减去字符就+
  如果实验访问一个在 defaultdict 中不存在的键，它会自动创建一个新键，并将其值设置为默认值（在这个例子中是 0）。但是{}不支持自动创建键
  

1.     def minWindow(self, s: str, t: str) -> str:
2.         need=collections.defaultdict(int)
3.         for c in t:
4.             need[c]+=1
5.         needCnt=len(t)
6.         left=0
7.         res=(0,float('inf'))
8.         
9.         for index,c in enumerate(s):
10.             if need[c]>0:  #如果需要字母c
11.                 needCnt-=1
12.             need[c]-=1
13.             if needCnt==0:       #步骤一：滑动窗口包含了所有T元素
14.                 while True:      #步骤二：增加left，排除多余元素
15.                     c=s[left]
16.                     if need[c]==0:
17.                         break
18.                     need[c]+=1
19.                     left+=1
20.                 if index-left<res[1]-res[0]:   #记录结果，当前窗口左指针left，右指针index
21.                     res=(left,index)
22.                 need[s[left]]+=1  #步骤三：left增加一个位置，寻找新的满足条件滑动窗口
23.                 needCnt+=1
24.                 left+=1
25.         return '' if res[1]>len(s) else s[res[0]:res[1]+1]    #如果res始终没被更新过，代表无满足条件的结果

复制代码

普通数组

53.最大子数组和【动态规划】

   

由于dp只与dp[i-1]和nums有关，因此直接在nums原地修改，空间复杂度O(1)

1. class Solution:
2.     def maxSubArray(self, nums: List[int]) -> int:
3.         for i in range(1,len(nums)):
4.             nums[i] = max(nums[i-1]+nums[i],nums[i])
5.         return max(nums)

复制代码

56.合并区间

   

• 先对左节点排序
  
• 判断当前合并区间和候选区间，是否重叠
  

1. class Solution:
2.     def merge(self, intervals: List[List[int]]) -> List[List[int]]:
3.         ans = []
4.         intervals.sort()  # 按照所有区间的左端点进行排序
5.         for interval in intervals:
6.             if not ans or ans[-1][1] < interval[0]:   #当ans为空，或者 当前区间的右节点 在 候选区间的左边【无重叠】
7.                 ans.append(interval)
8.             else: #当前并区间和候选区间  有重叠
9.                 ans[-1][1] = max(interval[1],ans[-1][1])   #取最大右区间
10.         return ans

复制代码

189.轮转数组

   直接用nums会报错？？
修改nums[:]不会影响到nums,nums[;]是一个新列表，是nums的副本，她两指向差别内存地点

1. class Solution:
2.     def rotate(self, nums: List[int], k: int) -> None:
3.         """
4.         Do not return anything, modify nums in-place instead.
5.         """
6.         k = k % len(nums)
7.         nums[:] = nums[len(nums)-k:] + nums[:len(nums)-k]
8.         return nums

复制代码

238.除自身以外数组的乘积

   

  

• 先初始化ans，ans[0]=1；辅助变量temp=1
  
• 计算下三角，计算上三角乘积temp，并乘以上三角
  索引容易搞错，可以看个图，根据图写索引
  

1. class Solution:
2.     def productExceptSelf(self, nums: List[int]) -> List[int]:
3.         ans = [1] * len(nums)
4.         temp = 1
5.         for i in range(1,len(nums)):
6.             ans[i] = ans[i-1] * nums[i-1]  #下三角
7.         for j in range(len(nums)-2,-1,-1):
8.             temp *= nums[j+1]   #上三角
9.             ans[j] *= temp   #下三角 * 上三角
10.         return ans

复制代码

41.缺失的第一个正数【困难】

   最后的结果肯定是在 [1,n+1] 内
修改 nums，使对应的下标 [0,n] 里 nums 第一个不是 i+1 的，i+1 就是答案
也就是，让 nums 里的数字，在 [1,n] 内的，都去他们对应的 [0,n-1] 位置上去的

1. class Solution:
2.     def firstMissingPositive(self, nums: List[int]) -> int:
3.         n = len(nums)
4.         for i in range(n):
5.             while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
6.                 # 这是错误的
7.                 # nums[i], nums[nums[i] - 1] = nums[nums[i] - 1], nums[i]
8.          #先计算右边的值，也就是nums[i]和nums[nums[i] - 1]的值，然后将他们赋值给一个临时元祖；
9. #然后按顺序赋值给左边，也就是说会先修改nums[i]的值，这样一来，nums[i] - 1就不是原来想要修改的下标了。
10.                 nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
11.         for i in range(n):
12.             if nums[i] != i + 1:
13.                 return i + 1
14.         return n + 1

复制代码

矩阵

73.矩阵置0

   两遍扫matrix,第一遍用集合记录哪些行,哪些列有0;第二遍置0

1. class Solution:
2.     def setZeroes(self, matrix: List[List[int]]) -> None:
3.         """
4.         Do not return anything, modify matrix in-place instead.
5.         """
6.         row = len(matrix)
7.         col = len(matrix[0])
8.         row_zero = set()
9.         col_zero = set()
10.         for i in range(row):
11.             for j in range(col):
12.                 if matrix[i][j] == 0:
13.                     row_zero.add(i)
14.                     col_zero.add(j)
15.         for i in range(row):
16.             for j in range(col):
17.                 if i in row_zero or j in col_zero:
18.                     matrix[i][j] = 0
19.                

复制代码

54.螺旋矩阵

   

1. class Solution:
2.     def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
3.         if not matrix: return []
5.         left, right, top, bottom = 0, len(matrix[0]) - 1, 0, len(matrix) - 1
6.         res = []
7.         while True:
8.             for i in range(left, right + 1):
9.                 res.append(matrix[top][i]) #从左上角 到 右上角
10.             top += 1
11.             if top > bottom:
12.                 break
14.             for i in range(top, bottom + 1):
15.                 res.append(matrix[i][right]) # 从右上角 到 右下角
16.             right -= 1
17.             if left > right:
18.                 break
20.             for i in range(right, left - 1, -1):
21.                 res.append(matrix[bottom][i]) # 从右下角 到左下角
22.             bottom -= 1
23.             if top > bottom:
24.                 break
26.             for i in range(bottom, top - 1, -1):
27.                 res.append(matrix[i][left]) #从左下角 到 左上角
28.             left += 1
29.             if left > right:
30.                 break
31.         return res

复制代码

48.旋转图像

   

方法一：借助一个辅助矩阵temp暂存原矩阵
方法二：原地修改。一轮可以完成矩阵 4 个元素的旋转。因而，只要分别以矩阵左上角 1/41/41/4 的各元素为起始点实行以上旋转操纵，即可完整实现矩阵旋转。【当矩阵大小n为偶数，就取n//2行，n//2列原始为起始点；矩阵大小n为奇数，取前n//2行，(n+1)//2列为起始点

1. class Solution:
2.     def rotate(self, matrix: List[List[int]]) -> None:
3.         """
4.         Do not return anything, modify matrix in-place instead.
5.         """
6.         n = len(matrix)
7.         temp = copy.deepcopy(matrix)   # 深拷贝 matrix -> tmp
8.         for i in range(n):
9.             for j in range(n):
10.                 matrix[i][j] = temp[n-j-1][i]   # 根据元素旋转公式，遍历修改原矩阵 matrix 的各元素

复制代码

1. class Solution:
2.     def rotate(self, matrix: List[List[int]]) -> None:
3.         """
4.         Do not return anything, modify matrix in-place instead.
5.         """
6.         n = len(matrix)
7.         for i in range(n//2):
8.             for j in range((n+1)//2):
9.                 temp = matrix[i][j]
10.                 matrix[i][j] = matrix[n-j-1][i]
11.                 matrix[n-j-1][i] = matrix[n-i-1][n-j-1]
12.                 matrix[n-i-1][n-j-1] = matrix[j][n-i-1]
13.                 matrix[j][n-i-1] = temp

复制代码

240.搜刮二维矩阵||

   

1. class Solution:
2.     def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
3.         i, j = len(matrix)-1, 0
4.         while i>=0 and j < len(matrix[0]):
5.             if matrix[i][j] < target:
6.                 j += 1
7.             elif matrix[i][j] > target:
8.                 i -= 1
9.             else:
10.                 return True
11.         return False

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。