算法题记录 31

438.找到字符串中所有字母异位词（中等）

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

涉及知识点

滑动窗口

解决思路

最基本的固定滑动窗口

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        ans=[]
        cnt_p=Counter(p)
        cnt_s=Counter()
        for right,c in enumerate(s):
            cnt_s[c]+=1
            left=right-len(p)+1
            if left<0:
                continue
            if cnt_s==cnt_p:
                ans.append(left)
            cnt_s[s[left]]-=1
        return ans

560.和为K的子数组（中等）

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

涉及知识点

子串

解决思路

前缀和求解

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        s = [0] * (len(nums) + 1)
        for i, x in enumerate(nums):
            s[i + 1] = s[i] + x

        ans = 0
        cnt = defaultdict(int)
        for sj in s:
            ans += cnt[sj - k]
            cnt[sj] += 1
        return ans

239.滑动窗口最大值（困难）

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

涉及知识点

子串

解决思路

双向单调队列求解

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        ans=[]
        q=deque()
        for i,x in enumerate(nums):
            while q and nums[q[-1]]<=x:
                q.pop()
            q.append(i)
            if i-q[0]>=k:
                q.popleft()
            if i>=k-1:
                ans.append(nums[q[0]])
        return ans

53.最大子数组和（中等）

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

涉及知识点

普通数组

解决思路

前缀和

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        ans = -inf
        min_pre_sum = pre_sum = 0
        for x in nums:
            pre_sum += x  # 当前的前缀和
            ans = max(ans, pre_sum - min_pre_sum)  # 减去前缀和的最小值
            min_pre_sum = min(min_pre_sum, pre_sum)  # 维护前缀和的最小值
        return ans

56.合并区间（中等）

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

涉及知识点

普通数组

解决思路

左端点排序

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda p: p[0])  # 按照左端点从小到大排序
        ans = []
        for p in intervals:
            if ans and p[0] <= ans[-1][1]:  # 可以合并
                ans[-1][1] = max(ans[-1][1], p[1])  # 更新右端点最大值
            else:  # 不相交，无法合并
                ans.append(p)  # 新的合并区间
        return ans

189.轮转数组（中等）

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

涉及知识点

普通数组

解决思路

原地切片，注意要nums[:]

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        # 计算有效的次数
        k = k%n
        # 原地切片即原地修改
        nums[:] =nums[-k:]+ nums[0:-k]

238.除自身以外数组的乘积（中等）

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

涉及知识点

普通数组

解决思路

前后缀

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        pre = [1] * n
        for i in range(1, n):
            pre[i] = pre[i - 1] * nums[i - 1]

        suf = [1] * n
        for i in range(n - 2, -1, -1):
            suf[i] = suf[i + 1] * nums[i + 1]

        return [p * s for p, s in zip(pre, suf)]

41.缺失的第一个正数（困难）

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

涉及知识点

普通数组

解决思路

哈希表，有难度，注意把原数组当哈希表来用。对于nums[i]，我们将其应该在的位置nums[i]%len(nums)-1的值加上len(nums)以作标记，同时不影响该位置的同样运算。最后遍历看哪个位置的值小于len(nums)即可，真实缺少的值是该位置下标+1。在所有操作之前记得对负数取0进行标记，后续判断nums[i] % max_len != 0再操作。

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        max_len = n+1

        for i in range(n):
            if nums[i] <= 0 or nums[i] >= max_len:
                nums[i] = 0
        
        for i in range(n):
            if nums[i] % max_len != 0:
                cur = (nums[i] % max_len) - 1
                nums[cur] = (nums[cur] % max_len) + max_len
        
        for i in range(n):
            if nums[i] < max_len:
                return i+1
        return max_len

73.矩阵置零（中等）

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

涉及知识点

矩阵

解决思路

二次遍历

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        row = len(matrix)
        col = len(matrix[0])
        row_zero = set()
        col_zero = set()
        for i in range(row):
            for j in range(col):
                if matrix[i][j] == 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[i][j] = 0

54.螺旋矩阵（中等）

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

涉及知识点

矩阵

解决思路

可以根据转向来找规律，也可以直接标记遍历过的数进行判断。

DIRS = (0, 1), (1, 0), (0, -1), (-1, 0)  # 右下左上

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        m, n = len(matrix), len(matrix[0])
        size = m * n
        ans = []
        i, j, di = 0, -1, 0  # 从 (0, -1) 开始
        while len(ans) < size:
            dx, dy = DIRS[di]
            for _ in range(n):  # 走 n 步（注意 n 会减少）
                i += dx
                j += dy  # 先走一步
                ans.append(matrix[i][j])  # 再加入答案
            di = (di + 1) % 4  # 右转 90°
            n, m = m - 1, n  # 减少后面的循环次数（步数）
        return ans

48.旋转图像（中等）

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

涉及知识点

矩阵

解决思路

直接找到更新后的位置赋值，每次更新四个数，从矩阵左上方的数开始更新即可。

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)
        for i in range(n // 2):
            for j in range((n + 1) // 2):
                tmp = matrix[i][j]
                matrix[i][j] = matrix[n - 1 - j][i]
                matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j]
                matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i]
                matrix[j][n - 1 - i] = tmp

声明

题目均来源于leetcode公开题库，部分方法解析来源于高赞题解，如有不妥请联系。