avatar

LeetCode刷题记录
dummy

滑动窗口

1004. 最大连续1的个数 III

给定一个由若干 01 组成的数组 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,求出数组从索引 iji ≤ j)范围内元素的总和,包含 ij两点。

实现 NumArray 类:

  • NumArray(int[] nums) 使用数组 nums 初始化对象
  • int sumRange(int i, int j) 返回数组 nums 从索引 iji ≤ j)范围内元素的总和,包含 ij两点(也就是 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)

Range Sum Query 2D
上图子矩阵左上角 (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/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 X Mεl0n | 随手记

评论