LeetCode Hot100 刷题笔记（2）—— 子串、普通数组、矩阵

目录

前言

一、子串

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 = 0
        res = 0
        for i in range(n):
            sums +=nums[i]
            res += dicts.get(sums-k, 0)
            dicts[sums] = dicts.get(sums, 0) + 1
        return 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 Counter
        cnt_t = Counter(t)
        cnt_s = Counter()
        for key in cnt_t:
            if key not in cnt_s:
                cnt_s[key] = 0
        def is_exist(cnt_s, cnt_t):
            for key in cnt_t:
                if cnt_s[key] < cnt_t[key]:
                    return False
            return True

        res = ""
        left = 0
        min_len = float("inf")
        for right in range(len(s)):
            if s[right] in cnt_s:
                cnt_s[s[right]] += 1
            while is_exist(cnt_s, cnt_t):
                if right - left + 1 < min_len:
                    min_len =  right - left + 1
                    res = s[left: right+1]
                if s[left] in cnt_s:
                    cnt_s[s[left]] -= 1
                left += 1
        return 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 = 1
        for i in range(n):
            answer[i] *= prefix
            prefix *= nums[i]
        # 后缀积
        suffix = 1
        for i in range(n-1, -1, -1):
            answer[i] *= suffix
            suffix *= 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 i
        return 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 True
        return False