LeetCode刷题记录

dummy

滑动窗口

1004. 最大连续1的个数 III

给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。

返回仅包含 1 的最长（连续）子数组的长度。

滑动窗口模板题，有点类似于快慢指针？

N = len(A)
        res = 0
        left, right = 0, 0
        zeros = 0 
        while right < N:
            if A[right] == 0:
                zeros += 1
            while zeros > K:
                if A[left] == 0:
                    zeros -= 1
                left += 1
            res = max(res, right - left + 1)
            right += 1
        return res

697. 数组的度

给定一个非空且只包含非负数的整数数组 nums，数组的度的定义是指数组里任一元素出现频数的最大值。

你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。

简单题

def findShortestSubArray(nums: List[int]) -> int:
truefreq = {}
trues_e = {}
truefor i, num in enumerate(nums):
truetrueif freq.get(num):
truetruetruefreq[num] += 1
truetruetrues_e[num][1] = i
truetrueelse:
truetruetruefreq[num] = 1
truetruetrues_e[num] = [i, i]
truefreq = sorted(freq.items(), key=lambda x:x[1])
truemax_freq = freq[-1][1]
truemax_freq_list = []
truei = -1
truewhile True:
truetrueif len(freq) >= abs(i) and freq[i][1] == max_freq:
truetruetruemax_freq_list.append(freq[i][0])
truetruetruei -= 1
truetrueelse:
truetruetruebreak
truemin_len = s_e[max_freq_list[0]][1] - s_e[max_freq_list[0]][0]
truefor i in max_freq_list:
truetruemin_len = min(min_len, s_e[i][1] - s_e[i][0])
truereturn min_len + 1

1438. 绝对差不超过限制的最长连续子数组

给你一个整数数组 nums ，和一个表示限制的整数 limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。

如果不存在满足条件的子数组，则返回 0 。

这个方法很妙，维护了两个极值的双向队列，这样能够快速判断当前极值，核心思想还是滑动窗口。

class Solution:
    def longestSubarray(self, nums, limit):
        r = l = res = 0
        min_q = collections.deque()
        max_q = collections.deque()
        for num in nums:
            while len(min_q) and num < min_q[-1]: min_q.pop()
            while len(max_q) and num > max_q[-1]: max_q.pop()
            min_q.append(num)
            max_q.append(num)
            r += 1;
            while max_q[0] - min_q[0] > limit:
                if min_q[0] == nums[l]: min_q.popleft() 
                if max_q[0] == nums[l]: max_q.popleft()
                l += 1
            res = max(res, r - l)
        return res

766. 托普利茨矩阵

给你一个 m x n 的矩阵 matrix 。如果这个矩阵是托普利茨矩阵，返回 true ；否则，返回 false 。

如果矩阵上每一条由左上到右下的对角线上的元素都相同，那么这个矩阵是 托普利茨矩阵 。

简单题

class Solution:
    def isToeplitzMatrix(self, matrix: List[List[int]]) -> bool:
        from collections import deque
        dq = deque(matrix[0])
        for i in range(1, len(matrix)):
            dq.pop()
            if list(dq) != matrix[i][1:]:
                return False
            dq.appendleft(matrix[i][0])
        return True

1052. 爱生气的书店老板

今天，书店老板有一家店打算试营业 customers.length 分钟。每分钟都有一些顾客（customers[i]）会进入书店，所有这些顾客都会在那一分钟结束后离开。

在某些时候，书店老板会生气。如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。当书店老板生气时，那一分钟的顾客就会不满意，不生气则他们是满意的。

书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 X 分钟不生气，但却只能使用一次。

请你返回这一天营业下来，最多有多少客户能够感到满意的数量。

还算比较简单

class Solution:
    def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
        plain_customer = 0
        N = len(customers)
        for i in range(N):
            if not grumpy[i]:
                plain_customer += customers[i]
        max_add = 0
        for i in range(X):
            if grumpy[i]:
                max_add += customers[i]
        l = 1
        tmp_add = max_add
        while l <= N-X:
            tmp_add = tmp_add - grumpy[l-1]*customers[l-1] + grumpy[l+X-1] * customers[l+X-1]
            max_add = max(max_add, tmp_add)
            l += 1
        return max_add + plain_customer

模拟

832. 翻转图像

给定一个二进制矩阵 A，我们想先水平翻转图像，然后反转图像并返回结果。

水平翻转图片就是将图片的每一行都进行翻转，即逆序。例如，水平翻转 [1, 1, 0] 的结果是 [0, 1, 1]。

反转图片的意思是图片中的 0 全部被 1 替换， 1 全部被 0 替换。例如，反转 [0, 1, 1] 的结果是 [1, 0, 0]。

找规律就可以

class Solution:
    def flipAndInvertImage(self, A: List[List[int]]) -> List[List[int]]:
        for line in A:
            l, r = 0, len(line) - 1
            while l < r:
                if line[l] == line[r]:
                    line[l] = line[r] = (1 ^ line[l])
                l += 1
                r -= 1
            if l == r:
                line[l] ^= 1
        return A

1178. 猜字谜

外国友人仿照中国字谜设计了一个英文版猜字谜小游戏，请你来猜猜看吧。

字谜的迷面 puzzle 按字符串形式给出，如果一个单词 word 符合下面两个条件，那么它就可以算作谜底：

单词 word 中包含谜面 puzzle 的第一个字母。

单词 word 中的每一个字母都可以在谜面 puzzle 中找到。
例如，如果字谜的谜面是 "abcdefg"，那么可以作为谜底的单词有 "faced", "cabbage", 和 "baggage"；而 "beefed"（不含字母 "a"）以及 "based"（其中的 "s" 没有出现在谜面中）。

返回一个答案数组 answer，数组中的每个元素 answer[i] 是在给出的单词列表 words 中可以作为字谜迷面 puzzles[i] 所对应的谜底的单词数目。

写了一个位运算的，但是看到n2的时间复杂度心里就觉得过不了了，结果确实没有，官方解给出了子集的做法、

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        for i in range(len(puzzles)):
            tmp = 0
            for ch in puzzles[i]:
                tmp |= (1 << ord(ch) - ord('a'))
            puzzles[i] = (tmp, puzzles[i][0])
        for i in range(len(words)):
            tmp = 0
            for ch in words[i]:
                tmp |= (1 << ord(ch) - ord('a'))
            words[i] = tmp
        for i in range(len(puzzles)):
            p = puzzles[i]
            match = 0
            for w in words:
                if (w >> (ord(p[1]) - ord('a'))) & 1 and w == (w & p[0]):
                    match += 1
            puzzles[i] = match
        return puzzles

正解：

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        frequency = collections.Counter()

        for word in words:
            mask = 0
            for ch in word:
                mask |= (1 << (ord(ch) - ord("a")))
            if str(mask).count("1") <= 7:
                frequency[mask] += 1
        
        ans = list()
        for puzzle in puzzles:
            total = 0

            # 枚举子集方法一
            # for choose in range(1 << 6):
            #     mask = 0
            #     for i in range(6):
            #         if choose & (1 << i):
            #             mask |= (1 << (ord(puzzle[i + 1]) - ord("a")))
            #     mask |= (1 << (ord(puzzle[0]) - ord("a")))
            #     if mask in frequency:
            #         total += frequency[mask]

            # 枚举子集方法二
            mask = 0
            for i in range(1, 7):
                mask |= (1 << (ord(puzzle[i]) - ord("a")))
            
            subset = mask
            while subset:
                s = subset | (1 << (ord(puzzle[0]) - ord("a")))
                if s in frequency:
                    total += frequency[s]
                subset = (subset - 1) & mask
            
            # 在枚举子集的过程中，要么会漏掉全集 mask，要么会漏掉空集
            # 这里会漏掉空集，因此需要额外判断空集
            if (1 << (ord(puzzle[0]) - ord("a"))) in frequency:
                total += frequency[1 << (ord(puzzle[0]) - ord("a"))]

            ans.append(total)
        
        return ans

递归

395. 至少有 K 个重复字符的最长子串

给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串，要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。

class Solution(object):
    def longestSubstring(self, s, k):
        if len(s) < k:
            return 0
        for c in set(s):
            if s.count(c) < k:
                return max(self.longestSubstring(t, k) for t in s.split(c))
        return len(s)

前缀和

303. 区域和检索 - 数组不可变

给定一个整数数组 nums，求出数组从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j两点。

实现 NumArray 类：

NumArray(int[] nums) 使用数组 nums 初始化对象

int sumRange(int i, int j) 返回数组 nums 从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j两点（也就是 sum(nums[i], nums[i + 1], ... , nums[j])）

class NumArray:

    def __init__(self, nums: List[int]):
        self.sum = [0]
        # sum[i] = Sum(nums[0]...nums[i-1])
        for num in nums:
            self.sum.append(num + self.sum[-1])

    def sumRange(self, i: int, j: int) -> int:
        # Sum(nums[i]...nums[j]) = sum[j+1] - sum[i]
        return self.sum[j+1] - self.sum[i]



# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(i,j)

304. 二维区域和检索 - 矩阵不可变

给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。

上图子矩阵左上角 (row1, col1) = (2, 1) ，右下角(row2, col2) = (4, 3)，该子矩形内元素的总和为 8。

跟上题思路类似，不过需要多一点想法。

class NumMatrix:

    def __init__(self, matrix: List[List[int]]):
        m, n = len(matrix), (len(matrix[0]) if matrix else 0)
        self.sums = [[0] * (n + 1) for _ in range(m + 1)]
        _sums = self.sums

        for i in range(m):
            for j in range(n):
                _sums[i + 1][j + 1] = _sums[i][j + 1] + _sums[i + 1][j] - _sums[i][j] + matrix[i][j]

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        _sums = self.sums

        return _sums[row2 + 1][col2 + 1] - _sums[row1][col2 + 1] - _sums[row2 + 1][col1] + _sums[row1][col1]

动态规划

338. 比特位计数

给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。

由于对于一个二进制数i，其结果必为i >> 1再加上i是否为奇数，所以可以使用动态规划

class Solution:
    def countBits(self, num):
        res = [0] * (num + 1)
        for i in range(1, num + 1):
            res[i] = res[i >> 1] + (i & 1)
        return res

354. 俄罗斯套娃信封问题

给定一些标记了宽度和高度的信封，宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。

请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        if not envelopes:
            return 0
        
        n = len(envelopes)
        envelopes.sort(key=lambda x: (x[0], -x[1]))

        f = [1] * n
        for i in range(n):
            for j in range(i):
                if envelopes[j][1] < envelopes[i][1]:
                    f[i] = max(f[i], f[j] + 1)
        
        return max(f)

当然，可以使用二分查找优化算法

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        if not envelopes:
            return 0
        
        n = len(envelopes)
        envelopes.sort(key=lambda x: (x[0], -x[1]))

        f = [envelopes[0][1]]
        for i in range(1, n):
            if (num := envelopes[i][1]) > f[-1]:
                f.append(num)
            else:
                index = bisect.bisect_left(f, num)
                f[index] = num
        
        return len(f)

132. 分割回文串 II

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。

返回符合要求的 最少分割次数 。

瞟了一眼题解，发现是可以用dp做，返回到文档来想想dp怎么做。

如果我们用dp[i]表示前缀s[0..<i]中能够切分为回文串的最小次数。那么我们最后返回dp[len(s)]即可，即需要定义一个长度为len(s) + 1的dp数组。

接下来得思考如何构造状态转移方程

由于dp[i]是最小分割次数，所以肯定要从dp[0]到dp[i-1]中枚举，由于我们加入了一个新的字母，所以源字符串s[0..<i]中，存在一个下标j，使s[j..<i]也能是一个回文串。

这样的话就是dp[j] + 1（dp[j]就是s[0..<j]的分割为回文串的最小次数。

得到状态转移方程为\(dp[i] = min_{0..i}(dp[j]) + 1\)

此外，如果s[0..<i]为回文串的话，dp[i] = 0

至于判断是否为回文串，可以使用本文中回溯里的判断回文串的题目中的函数

@cache
def isPalindrome(i: int, j: int) -> int:
    if i >= j:
        return 1
    return isPalindrome(i + 1, j - 1) if s[i] == s[j] else -1

所以完整题解为

class Solution:
    def minCut(self, s: str) -> int:
        # 第0位不用
        dp = [0] * (len(s) + 1)
        @cache
        def isPalindrome(i: int, j: int) -> int:
            if i >= j:
                return 1
            return isPalindrome(i + 1, j - 1) if s[i] == s[j] else -1
        
        for i in range(1, len(s) + 1):
            if isPalindrome(0, i-1) == 1:
                dp[i] = 0
            else:
                minCnt = len(s)
                for j in range(1, i):
                    # 如果满足回文条件
                    if isPalindrome(j, i-1) == 1:
                        minCnt = min(minCnt, dp[j] + 1)
                dp[i] = minCnt

        return dp[len(s)]

115. 不同的子序列

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）

题目数据保证答案符合 32 位带符号整数范围。

这道题可以建立一个len(s) * len(t)的dp数组，其中dp[i][j]表示在t的前i个字符里，有s的前j个字符的组数。

因此如果s[i] == t[j], dp[i][j] = dp[i-1][j - 1]

栈

503. 下一个更大元素 II

给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        length = len(nums)
        ret = [-1] * length
        stack = []
        # 确定每个元素都能找到后一个更大的
        for i in range(length * 2):
            while stack and nums[stack[-1]] < nums[i % length]:
                ret[stack.pop()] = nums[i % length]
            stack.append(i % length)
        return ret

1047. 删除字符串中的所有相邻重复项

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

这不就是消消乐么，可以发现栈非常容易做这个啊。

class Solution:
    def removeDuplicates(self, S: str) -> str:
        stack = []
        for i in list(S):
            if stack and stack[-1] == i:
                stack.pop()
            else:
                stack.append(i)
        return ''.join(stack)

224. 基本计算器

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

class Solution:
    def calculate(self, s: str) -> int:
        ops = []
        nums = []
        for i in list(s):
            if i == ' ':
                continue
            elif i == '(' or i == '+' or i == '-':
                ops.append(i)
            elif i == ')':
                while ops[-1] != '(':
                    op = ops.pop()
                    n1, n2 = nums.pop(), nums.pop()
                    nums.append(n1 + n2 if op == '+' else n2 - n1)
                # 去掉(
                ops.pop()
            else:
                nums.append(int(i))
        n1, n2 = nums.pop(), nums.pop()
        ret = n1 + n2 if ops[0] else n2 - n1
        return ret

331. 验证二叉树的前序序列化

序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。
     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #
例如，上面的二叉树可以被序列化为字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#"，其中 # 代表一个空节点。

给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。

每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 '#' 。

你可以认为输入格式总是有效的，例如它永远不会包含两个连续的逗号，比如 "1,,3" 。

可以把一个叶子结点转为空节点

class Solution(object):
    def isValidSerialization(self, preorder):
        stack = []
        for node in preorder.split(','):
            stack.append(node)
            while len(stack) >= 3 and stack[-1] == stack[-2] == '#' and stack[-3] != '#':
                stack.pop(), stack.pop(), stack.pop()
                stack.append('#')
        return len(stack) == 1 and stack.pop() == '#'

回溯

131. 分割回文串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

可以使用记忆化搜索寻找回文串，然后就是dfs回溯即可。

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        n = len(s)

        ret = list()
        ans = list()

        @cache
        def isPalindrome(i: int, j: int) -> int:
            if i >= j:
                return 1
            return isPalindrome(i + 1, j - 1) if s[i] == s[j] else -1

        def dfs(i: int):
            if i == n:
                ret.append(ans[:])
                return
            
            for j in range(i, n):
                if isPalindrome(i, j) == 1:
                    ans.append(s[i:j+1])
                    dfs(j + 1)
                    ans.pop()

        dfs(0)
        isPalindrome.cache_clear()
        return ret

文章作者: X Mεl0n

文章链接: http://www.zrzz.site/posts/ba8c707b/

LeetCode