天津网站排名_平台公司和项目公司的区别_网络营销五种方法_网络推广求职招聘交流群

目录

前言

一、子串

1. 和为 K 的子数组

2. 滑动窗口最大值

3. 最小覆盖子串

二、普通数组

4. 最大子数组和

5. 合并区间

6. 轮转数组

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

8. 缺失的第一个正数

三、矩阵

9. 矩阵置零

10. 螺旋矩阵

11. 旋转图像

12. 搜索二维矩阵 II

---

前言

一、子串：和为 K 的子数组，滑动窗口最大值，最小覆盖子串；

二、普通数组：最大子数组和，合并区间，轮转数组，除自身以外数组的乘积，缺失的第一个正数；

三、矩阵：矩阵置零；螺旋矩阵；旋转图像；搜索二维矩阵 II。

---

一、子串

1. 和为 K 的子数组

原题链接：560. 和为 K 的子数组 - 力扣（LeetCode）

class Solution(object):def subarraySum(self, nums, k):dicts = {0: 1}n = len(nums)sums = 0res = 0for i in range(n):sums +=nums[i]res += dicts.get(sums-k, 0)dicts[sums] = dicts.get(sums, 0) + 1return res

2. 滑动窗口最大值

原题链接：239. 滑动窗口最大值 - 力扣（LeetCode）

class Solution(object):def maxSlidingWindow(self, nums, k):q = []res = []for i in range(len(nums)):# 1. 入栈while q and nums[q[-1]] <= nums[i]:q.pop()q.append(i)# 2.出栈while i - q[0] >= k:q.pop(0)# 3.记录结果if i + 1 >= k:res.append(nums[q[0]])return res

3. 最小覆盖子串

原题链接：76. 最小覆盖子串 - 力扣（LeetCode）

# 考点：滑窗（不定窗口），快慢指针 --> 对比滑动窗口题型第2题
class Solution(object):def minWindow(self, s, t):from collections import Countercnt_t = Counter(t)cnt_s = Counter()for key in cnt_t:if key not in cnt_s:cnt_s[key] = 0def is_exist(cnt_s, cnt_t):for key in cnt_t:if cnt_s[key] < cnt_t[key]:return Falsereturn Trueres = ""left = 0min_len = float("inf")for right in range(len(s)):if s[right] in cnt_s:cnt_s[s[right]] += 1while is_exist(cnt_s, cnt_t):if right - left + 1 < min_len:min_len =  right - left + 1res = s[left: right+1]if s[left] in cnt_s:cnt_s[s[left]] -= 1left += 1return res

二、普通数组

4. 最大子数组和

原题链接：53. 最大子数组和 - 力扣（LeetCode）

class Solution(object):def maxSubArray(self, nums):for i in range(1, len(nums)):nums[i] = max(nums[i-1]+nums[i], nums[i])  # 动态规划return max(nums)

5. 合并区间

原题链接：56. 合并区间 - 力扣（LeetCode）

class Solution(object):def merge(self, intervals):intervals = sorted(intervals, key = lambda x: x[0])merge = []for interval in intervals:if not merge or merge[-1][1] < interval[0]:merge.append(interval)else:merge[-1][1] = max(merge[-1][1], interval[1])return merge

6. 轮转数组

原题链接：189. 轮转数组 - 力扣（LeetCode）

class Solution(object):def rotate(self, nums, k):k = k % len(nums)nums[:] = nums[-k:] + nums[:-k]

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

原题链接：238. 除自身以外数组的乘积 - 力扣（LeetCode）

class Solution(object):def productExceptSelf(self, nums):n = len(nums)answer = [1] * n# 前缀积prefix = 1for i in range(n):answer[i] *= prefixprefix *= nums[i]# 后缀积suffix = 1for i in range(n-1, -1, -1):answer[i] *= suffixsuffix *= nums[i]return answer

8. 缺失的第一个正数

原题链接：41. 缺失的第一个正数 - 力扣（LeetCode）

class Solution(object):def firstMissingPositive(self, nums):# dicts处改成list会内存溢出dicts = {i:0 for i in nums}for i in range(1, len(nums)+1):if i not in dicts:return ireturn len(nums)+1

三、矩阵

9. 矩阵置零

原题链接：73. 矩阵置零 - 力扣（LeetCode）

class Solution(object):def setZeroes(self, matrix):setx, sety = set(), set()m, n = len(matrix), len(matrix[0])for i in range(m):for j in range(n):if matrix[i][j] == 0:setx.add(i)sety.add(j)for i in range(m):for j in range(n):if i in setx or j in sety:matrix[i][j] = 0

10. 螺旋矩阵

原题链接：54. 螺旋矩阵 - 力扣（LeetCode）

class Solution(object):def spiralOrder(self, matrix):res = []while matrix:res += matrix.pop(0)matrix = list(zip(*matrix))[::-1]return res

11. 旋转图像

原题链接：48. 旋转图像 - 力扣（LeetCode）

class Solution(object):def rotate(self, matrix):matrix[:] = matrix[::-1]matrix[:] = list(zip(*matrix))

12. 搜索二维矩阵 II

原题链接：240. 搜索二维矩阵 II - 力扣（LeetCode）

class Solution(object):def searchMatrix(self, matrix, target):matrix = sum(matrix, [])for m in matrix:if m == target:return Truereturn False