目錄
前言
一、子串
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 res2. 滑動窗口最大值
原題鏈接：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 res3. 最小覆蓋子串
原題鏈接：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 merge6. 輪轉數組
原題鏈接：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 answer8. 缺失的第一個正數
原題鏈接：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] = 010. 螺旋矩陣
原題鏈接：54. 螺旋矩陣 - 力扣（LeetCode）
class Solution(object):def spiralOrder(self, matrix):res = []while matrix:res += matrix.pop(0)matrix = list(zip(*matrix))[::-1]return res11. 旋轉圖像
原題鏈接：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
)
