Drafts of Leetcode June 2022

2022年6月力扣, 296场手速题全部AC🎆, 发布了两篇题解🐉, 学习了nonlocal等用法.

💛 473. 火柴拼正方形

Wrong Answer - Carlos

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:  # 对撞指针, 观察后认为数字的分组不存在交错, 而这个观察使错误的
def makesquare(self, matchsticks: List[int]) -> bool:
if (perimeter := sum(matchsticks)) % 4:
return False
length = perimeter // 4 # 找一组数字凑齐length
matchsticks = sorted(matchsticks)
i, j, k = 0, 0, len(matchsticks) - 1 # k表示length中的大头, [i:j]这i-j个数字用来补零头
while j <= k:
temp = sum(matchsticks[i:j]) + matchsticks[k]
if temp > length:
return False
elif temp == length: # 正好, 凑下一组数
i = j
k -= 1
else: # 不够, 多看一个数
j += 1
return True

对于实例[2, 2, 2, 2, 3, 3, 3, 5, 5, 5, 6, 10], 分组为[2, 10], [3, 3, 6], [2, 5, 5], [2, 2, 3, 5], 存在数字间的交错, 与我的观察不符.

火柴拼正方形 - 力扣官方题解

🌟 方法一: 回溯 (时O4^n空On)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def makesquare(self, matchsticks: List[int]) -> bool:
totalLen = sum(matchsticks)
if totalLen % 4:
return False
matchsticks.sort(reverse=True) # 降序排列, 节省搜索空间
edges = [0] * 4
def dfs(idx: int) -> bool: # 当前edges下, 从第idx根火柴开始放, 是否能拼成正方形
if idx == len(matchsticks): # 火柴都放完了, 且没有出现超出边长的情况
return True
for i in range(4): # 往四条边上都放放试试看
edges[i] += matchsticks[idx]
if edges[i] <= totalLen // 4 and dfs(idx + 1): # 先判断会不会超出边长约束, 再递归判断从下一根开始放能不能拼成正方形
return True
edges[i] -= matchsticks[idx] # 因为放不了, 所以把edges还原!!
return False
return dfs(0)

🌟 方法二: 状态压缩 + 动态规划 (时n2^ n空2^n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def makesquare(matchsticks):
totalLen = sum(matchsticks) # e.g. 8
if totalLen % 4:
return False
tLen = totalLen // 4
dp = [-1] * (1 << len(matchsticks)) # {list: 32}; 索引表示记录哪些火柴已被放入, 值代表未放满边的当前长度
dp[0] = 0
for s in range(1, len(dp)):
for k, v in enumerate(matchsticks): # 尝试去掉一条边, 从之前的状态做转移, 这里不会出现多个状态s1以不同的值转移到s, 因为放火柴时遵循不放满不放下一条边, 因此不论怎么做转移, 值都是相同的
if s & (1 << k) == 0: # s从右往左数第k个位置没有放火柴
continue
s1 = s & ~(1 << k) # 去掉从右往左数的第k跟火柴所对应的状态
if dp[s1] >= 0 and dp[s1] + v <= tLen: # s1的火柴取法能够填满部分的正方形, 且未填满的部分的长未dp[s1]>=0; 填了v后不超出边长
dp[s] = (dp[s1] + v) % tLen # 由于dp[s]可能正好等于tLen, 因此要取模将其变为0
break
return dp[-1] == 0 # 全放满时, 未放满边长是否为0

💛 450. 删除二叉搜索树中的节点

输入[5,3,8,2,4,6,9], 要求删除根节点, 预期输出为[6,3,8,2,4,null,9], 竟然把一个叶子节点挪到根节点了, 不知道怎么做.

秒懂就完事了! - Terry

根据二叉搜索树的性质

  • 如果目标节点大于当前节点值,则去右子树中删除;
  • 如果目标节点小于当前节点值,则去左子树中删除;
  • 如果目标节点就是当前节点,分为以下三种情况:
    • 其无左子:其右子顶替其位置,删除了该节点;
    • 其无右子:其左子顶替其位置,删除了该节点;
    • 其左右子节点都有:其左子树转移到其右子树的最左节点的左子树上,然后右子树顶替其位置,由此删除了该节点。

左右子节点都有的情况, 树的转移是我没有想到的. 但注意这个回答树的高度变了!

删除二叉搜索树中的节点 - 力扣官方题解

方法一:递归 (时On空On)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]: # e.g. root: [4, 2, 6, 1, 3, 2, 7], key: 4
if root is None:
return None
if root.val > key: # 要删的节点在root的左分支
root.left = self.deleteNode(root.left, key)
elif root.val < key: # 要删的节点在root的右分支
root.right = self.deleteNode(root.right, key)
elif root.left is None or root.right is None: # 有一个节点是None, 可以直接删除
root = root.left if root.left else root.right
else: # 难想的情况, 涉及到子树的拼接!!
successor = root.right
while successor.left:
successor = successor.left # e.g. 5
successor.right = self.deleteNode(root.right, successor.val) # 右边连上右子树删去自己的值!!
successor.left = root.left
return successor
return root
# 4
# 2 6
# 1 3 2 7

方法二:迭代 (时On空O1)

829. 连续整数求和

逐个检查 - Carlos

1
2
3
4
5
6
7
8
9
10
class Solution:
def consecutiveNumbersSum(self, n: int) -> int:
i, result = 1, 0
while n / i - (i + 1) / 2 >= 0: # i个数相加, 这i个数的最小值至少是1, n/i是这i个数的均值, 该值一定要比长度的一半大, e.g. n: 15, 5数和是临界状态
if i % 2 and not n % i: # 若i是奇数, 则n必被i整除, 且商为i个数的中位数
result += 1
elif not i % 2 and abs(n / i - 0.5 - n // i) < 1e-6: # 若i是偶数, 则i个数的中位数必为n/i, 且n/i必须是某个整数+0.5
result += 1
i += 1
return result

💚 929. 独特的电子邮件地址

split + replace - Carlos

1
2
3
4
5
6
7
8
class Solution:
def numUniqueEmails(self, emails: List[str]) -> int:
result = set()
for email in emails:
local, domain = email.split('@') # 分离本地名和域名
true_local = local.split('+')[0] # 取加号前面的字符串
result.add(true_local.replace('.', '') + '@' + domain) # 添加真实的发送地址
return len(result)

🎯 第 296 场周赛 - 上海诺基亚贝尔股份有限公司

18 / 18, 893 / 5721.

💚 2293. 极大极小游戏

模拟 - Carlos

1
2
3
4
5
6
7
8
class Solution:  # 按题目意思来, 不要想数学思路
def minMaxGame(self, nums: List[int]) -> int:
if len(nums) == 1: return nums[0]
newNums = [0] * (len(nums) // 2)
for i in range(len(newNums)):
if i % 2: newNums[i] = max(nums[2 * i], nums[2 * i + 1])
else: newNums[i] = min(nums[2 * i], nums[2 * i + 1])
return self.minMaxGame(newNums)

💛 2294. 划分数组使最大差为 K

模拟 - Carlos

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:  # 排序后, 维护一个子列的最大和最小值, 然后按顺序判断是否能加入这个子列
def partitionArray(self, nums: List[int], k: int) -> int:
sorted_nums = sorted(nums)
result = 1
min_temp, max_temp = sorted_nums[0], sorted_nums[0]
for n in sorted_nums[1:]:
if min_temp <= n <= max_temp: # 在区间内, 直接可以放入
continue
if n > max_temp:
if n - min_temp <= k: # 在区间外, 但能接受, 需要更新最大值
max_temp = n
else: # 在区间外, 不能接受, 更新子序列, 看下一个
min_temp, max_temp = n, n
result += 1
elif n < min_temp:
if max_temp - n <= k:
min_temp = n
else:
min_temp, max_temp = n, n
result += 1
return result

💛 2295. 替换数组中的元素

模拟 - Carlos

1
2
3
4
5
6
7
8
9
class Solution:  # 存一个值到序号映射的字典, 按题目意思来
def arrayChange(self, nums: List[int], operations: List[List[int]]) -> List[int]:
d = {n: i for i, n in enumerate(nums)}
for old, new in operations:
i = d[old]
del d[old]
d[new] = i
nums[i] = new
return nums

2296. 设计一个文本编辑器

模拟 - Carlos

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class TextEditor:  # 字符串练习题, 细心就好
def __init__(self):
self.text = '|'
self.len = 0
self.pos = 0
def addText(self, text: str) -> None:
self.text = self.text[:self.pos] + text + self.text[self.pos:]
self.len += len(text)
self.pos += len(text)
def deleteText(self, k: int) -> int:
deleted_len = min(self.pos, k)
self.text = self.text[:self.pos-deleted_len] + self.text[self.pos:]
self.len -= deleted_len
self.pos -= deleted_len
return deleted_len
def cursorLeft(self, k: int) -> str:
temp = max(0, self.pos - k)
self.text = self.text[:temp] + '|' + self.text[temp:self.pos] + self.text[self.pos+1:]
self.pos = temp
return self.text[max(0, self.pos - 10):self.pos]
def cursorRight(self, k: int) -> str:
temp = min(self.len, self.pos + k)
self.text = self.text[:self.pos] + self.text[self.pos+1:temp+1] + '|' + self.text[temp+1:] # 注意中间项的temp+1, 这是由于光标右移产生的位置偏差
self.pos = temp
return self.text[max(0, self.pos - 10):self.pos]

💛 478. 在圆内随机生成点

Wrong Answer - Carlos

1
2
3
4
5
6
7
8
9
10
class Solution:  # 思路正确, 但是在乘法时会损失精度, 应该直接一步到位用random.uniform()
def __init__(self, radius: float, x_center: float, y_center: float):
self.radius = radius
self.x_center = x_center
self.y_center = y_center
def randPoint(self) -> List[float]:
while True:
a, b = random.random(), random.random()
if (a - 0.5) ** 2 + (b - 0.5) ** 2 <= 0.25: break
return [self.x_center + self.radius * (a - 0.5), self.y_center + self.radius * (b - 0.5)]

在圆内随机生成点 - 力扣官方题解

方法一:拒绝采样 (时O1空O1)

1
2
3
4
5
6
7
8
9
class Solution:
def __init__(self, radius: float, x_center: float, y_center: float):
self.xc = x_center
self.yc = y_center
self.r = radius
def randPoint(self) -> List[float]:
while True:
x, y = random.uniform(-self.r, self.r), random.uniform(-self.r, self.r)
if x * x + y * y <= self.r * self.r: return [self.xc + x, self.yc + y]

方法二:计算分布函数 (时O1空O1)

1
2
3
4
5
6
7
8
9
class Solution:  # 计算单位圆中随机生成一点, 离圆心距离<=r的概率分布函数
def __init__(self, radius: float, x_center: float, y_center: float):
self.xc = x_center
self.yc = y_center
self.r = radius
def randPoint(self) -> List[float]:
u, theta = random.random(), random.random() * 2 * math.pi
r = sqrt(u)
return [self.xc + r * math.cos(theta) * self.r, self.yc + r * math.sin(theta) * self.r]

732. 我的日程安排表 III

探针模拟 - Carlos

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class MyCalendarThree:
def __init__(self):
self.events = [] # 记录所有的区间
self.needles = dict() # 在区间两端处做探针穿刺, 穿的层数最多的就是答案
def book(self, start: int, end: int) -> int:
self.events.append([start, end]) # 更新区间
for needle in self.needles.keys(): # 在新增区间内更新已有探针
if start <= needle < end: # 除了正好等于end时不处理, 其余都加1
self.needles[needle] += 1
for needle in [start, end]:
if not needle in self.needles.keys(): # 处理新增探针, 对所有区间做穿刺
for s, e in self.events:
if s <= needle < e:
self.needles[needle] = self.needles.get(needle, 0) + 1
return max(self.needles.values())

💛 875. 爱吃香蕉的珂珂

Bisect - Carlos

1
2
3
4
5
6
7
class Solution:
def minEatingSpeed(self, piles: List[int], h: int) -> int:
if len(piles) == 1: # 这个特殊情况是由于输入为一堆香蕉时, idx索引会越界
return math.ceil(piles[0] / h)
temp = range(1, max(piles) + 1)[::-1] # 注意到bisect函数只能处理升序的序列, 因此把速度降序排列, 这样所用时间就是升序了
idx = bisect.bisect_right(temp, h, key=lambda x: sum(int(math.ceil(_ / x)) for _ in piles))
return temp[idx]+1

爱吃香蕉的珂珂 - 力扣官方题解

1
2
3
class Solution:  # 为了满足bisect的降序要求, 使用-h作为目标, 不容易想, 仅放这里与Benhao的解法对比
def minEatingSpeed(self, piles: List[int], h: int) -> int:
return bisect_left(range(max(piles)), -h, 1, key=lambda k: -sum((pile + k - 1) // k for pile in piles))

[Python/Java/TypeScript/Go] 二分 - Benhao

1
2
3
class Solution:  # 与我的原始思路相同, 巧妙地构造条件判断运用了True作为二分查找目标
def minEatingSpeed(self, piles: List[int], h: int) -> int:
return bisect_left(range(1, max(piles) + 1), True, key=lambda x: sum(ceil(p / x) for p in piles) <= h) + 1

💚 1037. 有效的回旋镖

数学 - Carlos

1
2
3
4
class Solution:  # 等价于判断三点构成的区域是否为0
def isBoomerang(self, points: List[List[int]]) -> bool:
(x1, y1), (x2, y2), (x3, y3) = points[0], points[1], points[2]
return True if x1 * y2 + x2 * y3 + x3 * y1 - x3 * y2 - x2 * y1 - x1 * y3 else False

💛 497. 非重叠矩形中的随机点

前缀和 + 二分 - Carlos

1
2
3
4
5
6
7
8
class Solution:
def __init__(self, rects: List[List[int]]):
self.rects = [{'coord': (a, b, x, y), 'area': (x - a + 1) * (y - b + 1)} for a, b, x, y in rects] # 注意算面积时要+1, 因为考虑的是整数点的个数!!
self.cumsum_area = [_ / sum(temp) for _ in accumulate(temp)] if (temp := [_['area'] for _ in self.rects]) else None # [How to find the cumulative sum of numbers in a list?](https://stackoverflow.com/a/53754768/12224183)
def pick(self) -> List[int]:
idx = bisect_left(self.cumsum_area, random.random())
a, b, x, y = self.rects[idx]['coord']
return [random.randint(a, x), random.randint(b, y)]

🐉 [一行Python] 按面积抽样+二分 - Carlos

1
2
3
4
5
class Solution:
def __init__(self, rects: List[List[int]]):
self.rects = [{'coord': (a, b, x, y), 'area': (x - a + 1) * (y - b + 1)} for a, b, x, y in rects]
def pick(self) -> List[int]:
return [random.randint(abxy[0], abxy[2]), random.randint(abxy[1], abxy[3])] if (abxy := self.rects[bisect_left([_ / sum(temp) for _ in accumulate(temp)] if (temp := [_['area'] for _ in self.rects]) else [], random.random())]['coord']) else [0, 0]

==730. 统计不同回文子序列==

想到动态规划但没做出来, 和美团一面面试的题很像.

💛 926. 将字符串翻转到单调递增

循环统计 - Carlos

1
2
3
4
5
6
7
8
9
10
import numpy as np
class Solution: # 思路简单, 但需要优化数据的存储和更新方式, 见官方的前缀和解法
def minFlipsMonoIncr(self, s: str) -> int:
temp = np.zeros([2, len(s) + 1]) # 给一个分割线, 统计其后面有多少0, 前面有多少1
for i, _ in enumerate(s):
if _ == '0':
temp[0, :i+1] += 1
else:
temp[1, i+1:] += 1
return int(min(temp[0] + temp[1]))

将字符串翻转到单调递增 - 力扣官方题解

方法一:动态规划 (时On空O1)

将字符串翻转到单调递增 - 力扣 (LeetCode)

方法一:前缀和 (时On空On)

🎯 第 80 场双周赛 - TP-LINK

7/19, 1635 / 3949.

💚 2299. 强密码检验器 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
def strongPasswordCheckerII(self, password):
temp = [False] * 4
if len(password) >= 8:
for i, s in enumerate(password):
if ord('a') <= ord(s) <= ord('z'):
temp[0] = True
if ord('A') <= ord(s) <= ord('Z'):
temp[1] = True
if ord('0') <= ord(s) <= ord('9'):
temp[2] = True
if s in "!@#$%^&*()-+":
temp[3] = True
if i >=1 and s == password[i - 1]:
return False
return sum(temp) == 4
return False

💛 2300. 咒语和药水的成功对数

1
2
3
4
5
6
7
8
class Solution:
def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
potions = sorted(potions)
result = []
for s in spells:
idx = bisect.bisect_left(potions, 1, key=lambda x: x * s >= success)
result.append(len(potions) - idx)
return result

这一题由于没有把Python切换成Python3, 使用带keybisect_left时一直报错, 浪费了很多时间.

==2301. 替换字符后匹配== - TLE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def matchReplacement(self, s: str, sub: str, mappings: List[List[str]]) -> bool:
temp = {_:[_] for _ in s}
for a, b in mappings:
temp[a] = temp.get(a, [])
temp[a].append(b)
for i in range(len(s) - len(sub) + 1):
myiter = list(range(len(sub)))
random.shuffle(myiter)
for j in myiter:
if s[i + j] not in temp.get(sub[j], []):
break
else:
return True
return False

==2302. 统计得分小于 K 的子数组数目==

🎯 第 297 场周赛 - 地平线

8 / 19, 1585 / 5915.

💚 2303. 计算应缴税款总额

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def calculateTax(self, brackets: List[List[int]], income: int) -> float:
last_upper = 0
result = 0
for upper, percent in brackets:
if income >= upper:
result += (upper - last_upper) * percent / 100
elif income >= last_upper:
result += (income - last_upper) * percent / 100
else:
break
last_upper = upper
return result

💛 2304. 网格中的最小路径代价

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
def move(grid1, grid2):
return [min(grid1[j] + moveCost[grid1[j]][i] for j in range(n)) for i in range(n)]

grid1 = grid[0]
for i in range(1, m):
grid2 = grid[i]
temp = move(grid1, grid2)
for j in range(n):
for k in range(n):
moveCost[grid2[j]][k] += temp[j]
grid1 = grid2
return min(grid[-1][_] + temp[_] for _ in range(n))

💛 ==2305. 公平分发饼干==

卜算上讲过k=2的特殊情况, 转化为背包问题然后动态规划, 但这一题为k的一般情况, 不知道怎么处理.

暴力两行不解释 - 不造轮子

1
2
3
4
class Solution:
def distributeCookies(self, cookies: List[int], k: int) -> int:
part = list(range(1, n := len(cookies)))
return min(max(sum(t[l: r]) for l, r in pairwise((0, ) + cm + (n,))) for t in permutations(cookies) for cm in combinations(part, k - 1))

观察参数范围: 2 <= cookies.length <= 8以及2 <= k <= cookies.length, 孩子数量至多为8, 且每个孩子必能分到饼干, 这样问题就转化为了全排列饼干后, 对这个列表切k-1刀. 具体地说, 我们要获得的是求和的索引, 初始的0和末尾的len(cookies)是确定的, 中间有len(cookies)-1个位置, 要从中选取k-1个位置切开. 对于输入[8,15,10,20,8] 3, 拆解算法后得到如下输出:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:  # cookies: [8,15,10,20,8], k: 3
def distributeCookies(self, cookies: List[int], k: int) -> int:
part = range(1, n := len(cookies))
for cm in combinations(part, k - 1):
print((0,) + cm + (n,), list(pairwise((0, ) + cm + (n,))))
pass
return 0
# (0, 1, 2, 5) [(0, 1), (1, 2), (2, 5)]
# (0, 1, 3, 5) [(0, 1), (1, 3), (3, 5)]
# (0, 1, 4, 5) [(0, 1), (1, 4), (4, 5)]
# (0, 2, 3, 5) [(0, 2), (2, 3), (3, 5)]
# (0, 2, 4, 5) [(0, 2), (2, 4), (4, 5)]
# (0, 3, 4, 5) [(0, 3), (3, 4), (4, 5)]

==2306. 公司命名== - WA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution:
def distinctNames(self, ideas: List[str]) -> int:
n = len(ideas)
temp = dict()
temp2 = dict()
count = dict()
for idea in ideas:
temp[idea[1:]] = temp.get(idea[1:], [])
temp[idea[1:]].append(idea[0])
temp2[idea[0]] = temp2.get(idea[0], [])
temp2[idea[0]].append(idea[1:])
print(temp)
print(temp2)
# {'offee': ['c', 't'], 'onuts': ['d'], 'ime': ['t']}
# coffee和toffee不行
# 和所有c打头的不行
# 和所有t打头的不行, coffee和time换后变成toffee, toffee和time也不行
result = n * (n - 1)
for key, value in temp.items():
result -= len(value) * (len(value)) -1
#print('self', result)
if len(value) > 1:
for s in value:
if s in temp2:
print(s, len(temp2[s]) - 1, len(value))
result -= (len(temp2[s]) - 1) * len(value)
print('>1', result)
else:
#print(value[0])
#print(temp2[value[0]])
#print([len(temp[_]) for _ in temp2[value[0]]])
result -= sum(len(temp[_]) for _ in temp2[value[0]] if len(temp[_]) > 1)
#print('=1', result)
return result

数学统计题, 熬到最后一刻, 没对.

💛 890. 查找和替换模式

维护一一映射 - Carlos

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def findAndReplacePattern(self, words: List[str], pattern: str) -> List[str]:
result = []
for word in words:
temp = dict() # 维护一个一一映射, 把pattern中的字符映到word中
for i in range(len(pattern)):
if pattern[i] in temp: # 该元素已经在映射中出现过了
if temp[pattern[i]] != word[i]: # 若检查到待构造的映射是一映多的, break
break
else:
if word[i] in temp.values(): # 这一行是为了防止把ccc判为abb, 即防止映射多映一!!
break
else:
temp[pattern[i]] = word[i] # 构造映射
else:
result.append(word)
return result

💚 1051. 高度检查器

排序 - Carlos

1
2
3
class Solution:  # 即返回与递增排序不同位置得元素个数, 写了个排序糊弄, 时间满足要求
def heightChecker(self, heights: List[int]) -> int:
return sum(_ != heights[i] for i, _ in enumerate(sorted(heights)))

💛 498. 对角线遍历

🐉 [一行Python] 二级排序 - Carlos

  • 排序第一级: 索引和
  • 排序第二级: 观查到对角线顺序是交替的, 因此在索引和相同的情况下, 使用索引第二维乘上-1的索引和次方
1
2
3
class Solution:
def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
return [mat[a][b] for a, b in sorted(itertools.product(range(len(mat)), range(len(mat[0]))), key=lambda x: (x[0] + x[1], x[1] * (-1) ** (x[0] + x[1])))]

==719. 找出第 K 小的数对距离==

Time Limit Error - Carlos

1
2
3
4
class Solution:  # 暴力组合排序, 时间复杂度应为2n^2logn
def smallestDistancePair(self, nums: List[int], k: int) -> int:
temp = sorted(itertools.combinations(nums, 2), key=lambda x: abs(x[0] - x[1]))[k-1]
return abs(temp[0] - temp[1])

后续我的思路为: 先对nums排序, 最小的距离组肯定在索引差为1的组合中产生, 选取之后, 第二小的距离组在其余的索引差为1的组合, 以及上述选取了的组合扩大一个索引的组合中产生. 可以构造一个下三角矩阵, 行为索引差, 列为升序排列的nums, 最小距离组为对角线的最小值, 第二小的距离组为对角线的剩余元素, 以及被选取的元素的下方中产生.

找出第 K 小的数对距离 - 力扣官方题解

方法一: 排序 + 二分查找

方法二: 排序 + 二分查找 + 双指针

💛 532. 数组中的 k-diff 数对

排序后模拟 - Carlos

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def findPairs(self, nums: List[int], k: int) -> int:
nums = sorted(nums)
n = len(nums)
temp = []
result = 0
for i in range(n):
for j in range(i + 1, n):
if nums[j] - nums[i] == k and (nums[i], nums[j]) not in temp:
result += 1
temp.append((nums[i], nums[j]))
elif nums[j] - nums[i] > k:
break
return result

数组中的 k-diff 数对 - 力扣官方题解

方法一: 哈希表 (时On空On)

1
2
3
4
5
6
7
8
9
10
class Solution:  # 核心观察是目标数组的同位置元素是各不相同的, 因此便利一边, 观察其为最小元素时, 左侧所有元素是否有满足的
def findPairs(self, nums: List[int], k: int) -> int:
visited, res = set(), set()
for num in nums:
if num - k in visited:
res.add(num - k) # 加入最小的!!
if num + k in visited:
res.add(num) # 加入最小的!!
visited.add(num)
return len(res)

为什么不直接把visited设置为set(nums)? 这是因为看左边元素时已经把所有元素对看过一遍了. 当实例为[3,1,4,1,5] 2时, 输出为:

1
2
3
when i: 1, num: 1, add (1, 3)
when i: 3, num: 1, add (1, 3)
when i: 4, num: 5, add (3, 5)

visited=set(nums), 输出如下, 可以看到有许多重复.

1
2
3
4
5
when i: 0, num: 3, add (1, 3)
when i: 0, num: 3, add (3, 5)
when i: 1, num: 1, add (1, 3)
when i: 3, num: 1, add (1, 3)
when i: 4, num: 5, add (3, 5)

方法二:排序 + 双指针 (时Onlogn空On)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:  # x为小数下表, y为大数下标
def findPairs(self, nums: List[int], k: int) -> int:
nums.sort()
n, y, res = len(nums), 0, 0
for x in range(n):
if x == 0 or nums[x] != nums[x - 1]:
while y < n and (nums[y] < nums[x] + k or y <= x): # y<=x是为了保证k=0时下标不同
y += 1
if y < n and nums[y] == nums[x] + k:
res += 1
return res
=======
# :yellow_heart: [875. 爱吃香蕉的珂珂](https://leetcode.cn/problems/koko-eating-bananas/)

## Bisect - Carlos

```python
class Solution:
def minEatingSpeed(self, piles: List[int], h: int) -> int:
if len(piles) == 1: # 这个特殊情况是由于输入为一堆香蕉时, idx索引会越界
return math.ceil(piles[0] / h)
temp = range(1, max(piles) + 1)[::-1] # 注意到bisect函数只能处理升序的序列, 因此把速度降序排列, 这样所用时间就是升序了
idx = bisect.bisect_right(temp, h, key=lambda x: sum(int(math.ceil(_ / x)) for _ in piles))
return temp[idx]+1

💚 1089. 复写零

列表操作 - Carlos

1
2
3
4
5
6
7
8
class Solution:
def duplicateZeros(self, arr: List[int]) -> None:
num = 0
for i in range(len(arr)):
if i + num < len(arr) and arr[i + num] == 0:
arr.insert(i + num, 0)
arr.pop()
num += 1

💛 剑指 Offer II 029. 排序的循环链表

模拟 - Carlos

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def insert(self, head: 'Node', insertVal: int) -> 'Node':
if not head:
temp = Node(val=insertVal, next=None)
temp.next = temp
return temp
if head.next == head:
temp = Node(val=insertVal, next=head)
head.next = temp
return head
node1, node2 = head, head.next
while True:
if node1.val <= insertVal <= node2.val or node2.val < node1.val <= insertVal or insertVal <= node2.val < node1.val or node2 == head: # 第2,3个条件分别是判断最大元素 (如[1,3,3] 4) 和最小元素 (如[3,3,5] 0) 插入, 不等号是严格的, 否则会在两个相等元素中插入, 但对于 [3,3,3] 0 这种输入, 加入第4个条件, 当转完一轮后还没返回, 则在末尾插入!!
temp = Node(val=insertVal, next=node2)
node1.next = temp
return head
node1, node2 = node1.next, node2.next

🎯 第 298 场周赛 - 趋势科技

7 / 18, 2039 / 6228.

💚 2309. 兼具大小写的最好英文字母

1
2
3
4
5
6
class Solution:  # 字母表挨个检查就完了
def greatestLetter(self, s: str) -> str:
for i in range(26)[::-1]:
if chr(65 + i) in s and chr(97 + i) in s:
return chr(65 + i)
return ""

💛 2310. 个位数字为 K 的整数之和

1
2
3
4
5
6
7
class Solution:  # 观察到所求只与num的个位数有关, num=0和k=0时分别WA一发, 都特殊处理就好了
def minimumNumbers(self, num: int, k: int) -> int:
if num == 0: return 0
if k == 0: return -1 if num % 10 else 1
for i in range(1, int(num // k + 1)):
if (i * k) % 10 == num % 10: return i
return -1

💛 2311. 小于等于 K 的最长二进制子序列 - TLE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:  # 气死了, TLE优化了一小时没过, 应该贪心做, 贪左侧的0
@cache # 优化1, 记忆化DC
def longestSubsequence(self, s: str, k: int) -> int:
if len(s) == 1:
# print(s, k, 1 if int(s) <= k else 0)
return 1 if int(s) <= k else 0
if int(s, 2) <= k: # 优化2, 节少调用次数
return len(s)
if (k - int(s[-1])) // 2 < 0: # 否则结果会比标准输出大1
return self.longestSubsequence(s[:-1], k)
return max(
self.longestSubsequence(s[:-1], k),
self.longestSubsequence(s[:-1], (k - int(s[-1])) // 2) + 1
)

==2312. 卖木头块==

💛 508. 出现次数最多的子树元素和

DC - Carlos

1
2
3
4
5
6
7
8
9
10
class Solution:  # 递推地计算子树元素和列表
def findFrequentTreeSum(self, root: TreeNode) -> List[int]:
def f(root):
if not root: return []
left_list = [] if not root.left else f(root.left)
right_list = [] if not root.right else f(root.right)
return left_list + right_list + [root.val + (0 if not len(left_list) else left_list[-1]) + (0 if not len(right_list) else right_list[-1])]
counter = Counter(f(root))
value = max(counter.values())
return [k for k, v in counter.items() if v == value]

==715. Range 模块==

改了一天简历, 摸了.

💚 1108. IP 地址无效化

replace - Carlos

1
2
3
class Solution:
def defangIPaddr(self, address: str) -> str:
return address.replace('.', '[.]')

💛 513. 找树左下角的值

DFS - Carlos

1
2
3
4
5
6
7
8
class Solution:  # 一种DFS, 然而速度和官方的DFS没有显著差异
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
def f(root):
l_depth, l_node = (1, root) if not root.left else f(root.left)
r_depth, r_node = (1, root) if not root.right else f(root.right)
if l_depth >= r_depth: return l_depth + 1, l_node
return r_depth + 1, r_node
return f(root)[1].val

找树左下角的值 - 力扣官方题解

典型的搜索题, 熟悉一下两类搜索写法.

方法一: 深度优先搜索 (时On空On)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
curVal = curHeight = 0
def dfs(node: Optional[TreeNode], height: int) -> None:
if node is None: return
height += 1 # 记录遍历到的节点的高度
dfs(node.left, height)
dfs(node.right, height)
nonlocal curVal, curHeight
if height > curHeight:
curHeight = height # 记录最大高度
curVal = node.val # 记录高度在curHeight的最左节点的值
dfs(root, 0)
return curVal

🛠 The nonlocal statement

Python nonlocal Keyword的例子说明了nonlocal必须使用于局部变量, 以及多次复写时值的变化情况.

方法二: 广度优先搜索 (时On空On)

1
2
3
4
5
6
7
8
9
class Solution:
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
q = deque([root]) # 维护一个队列, 先进先出
while q:
node = q.popleft() # 节点是从右侧加入的, 因此要从左侧删去
if node.right: q.append(node.right)
if node.left: q.append(node.left)
ans = node.val
return ans

30. 串联所有单词的子串

逐个检查 - Carlos

1
2
3
4
5
6
7
8
9
10
11
class Solution:
def findSubstring(self, s: str, words: List[str]) -> List[int]:
length = len(words[0])
result = []
for i in range(len(s) - length * len(words) + 1): # 一定要+1, 否则会漏掉一个
temp = words[:] # 记录一个words的拷贝, 逐个检查, 查到一个删掉一个
for j in range(len(words)):
if (word := s[i+j*length:i+(j+1)*length]) in temp: temp.remove(word)
else: break
else: result.append(i) # 此时temp为空, 符合条件
return result

[Python/Java/TypeScript/Go] 哈希计数暴力 - Benhao

1
2
3
4
class Solution:  # [i for i in 起始位置 if Counter相同]
def findSubstring(self, s: str, words: List[str]) -> List[int]:
cnts, step = Counter(words), len(words[0])
return [i for i in range(len(s) - step * len(words) + 1) if Counter([s[i+j*step:i+(j+1)*step] for j in range(len(words))]) == cnts]

思路和我的一致, 但使用Counter避免了拷贝再检查的循环.

💛 515. 在每个树行中找最大值

BFS层序遍历 - Carlos

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def largestValues(self, root: Optional[TreeNode]) -> List[int]:
if not root: return []
queue, result = [root], []
while queue:
result.append(max(_.val for _ in queue))
temp = []
for n in queue:
if n.left: temp.append(n.left)
if n.right: temp.append(n.right)
queue = temp
return result

💛 剑指 Offer II 091. 粉刷房子

DC, 贪心, DP - Carlos

1
2
3
4
5
6
7
8
class Solution:  # DC, 考虑第一个房间涂成idx色后, 剩下的该怎么涂
def minCost(self, costs: List[List[int]]) -> int:
def f(costs, idx):
if not costs: return 0
return min(costs[0][idx] + f(costs[1:], _) for _ in range(3) if _ != idx)
return min(f(costs, _) for _ in range(3))
# WA: 对于[[3,5,3],[6,17,6],[7,13,18],[9,10,18]], 初始化条件不能是if len(costs) == 1
# TLE: [[4,20,19],[12,12,19],[10,11,20],[1,7,20],[4,20,1],[7,19,17],[4,18,16],[16,6,10],[5,2,4],[9,8,5],[13,18,15],[12,10,14],[11,16,3],[13,1,14],[13,4,6],[17,1,10],[7,3,16],[20,7,3],[3,9,19],[17,17,14],[14,1,14]]
1
2
3
4
5
6
7
8
9
10
11
class Solution:  # 贪心, 每次贪可选的两个颜色中价格最低的
def minCost(self, costs: List[List[int]]) -> int:
result = [0, 0, 0]
for i in range(3):
result[i] = min(costs[0])
idx = i
for cost in costs[1:]:
idx, temp = min([(j, _) for j, _ in enumerate(cost) if j != idx], key=lambda x: x[1])
result[i] += temp
return min(result)
# WA: 对于[[5,8,6],[19,14,13],[7,5,12],[14,15,17],[3,20,10]], 得到result为[47, 47, 44], 而答案为43
1
2
3
4
5
6
class Solution:  # DP, 第i个房间, 分别涂成颜色c的最低花费为, 该花费加上第i个房间涂成非c颜色的最小值
def minCost(self, costs: List[List[int]]) -> int:
for i in range(1, len(costs)):
for j in range(3):
costs[i][j] += min(costs[i - 1][_] for _ in range(3) if _ != j)
return min(costs[-1])

🎯 第 81 场双周赛 - BOE 京东方

3 / 19, 1735 / 3847.

💚 2315. 统计星号

1
2
3
4
5
6
7
8
9
10
class Solution:  # 判断成对括号外的*, 设置一个state标志逐个统计就好
def countAsterisks(self, s: str) -> int:
state = True
result = 0
for _ in s:
if _ == '|':
if not state: state = True
else: state = False
if state and _ == '*': result += 1
return result

💛 ==2316. 统计无向图中无法互相到达点对数== - TLE

首先考虑用edges非空的条件做外层循环, 由于在删边的过程中连通性考虑不周, 对于以下实例出错:

1
2
3
# 11
# [[5,0],[1,0],[10,7],[9,8],[7,2],[1,3],[0,2],[8,5],[4,6],[4,2]]
# output: 0

之后想到要利用邻接表.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:  # 我理解为统计各个连通分支的顶点个数, 然后考虑怎么算出答案就好, 最后在1e5的最大实例上TLE了
def countPairs(self, n: int, edges: List[List[int]]) -> int:
adj_list = {_: set() for _ in range(n)}
for a, b in edges:
adj_list[a].add(b)
adj_list[b].add(a)
ccs_num = [] # connected component的顶点个数列表, 且顶点个数时
nodes = set(range(n)) # 未访问的顶点集合
while nodes: # 整体思路和贪吃蛇3v3和奥林匹克环境的spread函数比较像
start_node = nodes.pop()
visited = {start_node}
cc = {start_node}
while visited:
# temp = set()
# for v in visited:
# for u in adj_list[v]:
# if u not in cc:
# temp.add(u)
# temp = {u for u in adj_list[v] if u not in cc for v in visited}
temp = {u for v in visited for u in adj_list[v] if u not in cc} # 不在连通分支的1邻居
visited = temp
cc = cc.union(temp)
ccs_num.append(len(cc))
nodes -= cc
return sum(_ * (n - _) for _ in ccs_num) // 2 # 每个连通分支上的点都和其余所有点不相连, 遍历每个连通分支, 最后因为每个点对被算了两边, 因此要除以2

💛 ==2317. 操作后的最大异或和==

概念不懂.

==2318. 不同骰子序列的数目==

好难, 考虑三维DP, 不会做.

🎯 第 299 场周赛 - 神策数据

7 / 18, 2168 / 6108.

💚 2319. 判断矩阵是否是一个 X 矩阵

1
2
3
4
5
6
7
8
class Solution:  # 逐个判断即可
def checkXMatrix(self, grid: List[List[int]]) -> bool:
n = len(grid)
for i in range(n):
for j in range(n):
if (i == j or i + j == n - 1) and grid[i][j] == 0: return False
if i != j and i + j != n - 1 and grid[i][j] != 0: return False
return True

💛 2320. 统计放置房子的方式数

1
2
3
4
5
6
7
8
9
class Solution:  # DP, 利用temp[i][1]的对称性省去1/4的存储和计算
def countHousePlacements(self, n: int) -> int:
temp = [[0, 0, 0] for _ in range(n)] # 00, 01, 11
temp[0] = [1, 1, 1]
for i in range(1, n):
temp[i][0] = temp[i-1][0] + 2 * temp[i-1][1] + temp[i-1][2]
temp[i][1] = temp[i-1][0] + temp[i-1][1]
temp[i][2] = temp[i-1][0]
return (temp[-1][0] + 2 * temp[-1][1] + temp[-1][2]) % int(1e9 + 7)

提交时一直报错OverflowError: int too large to convert to float, 浪费了很长时间💢, 实际上只要在1e9+7作用int就行了.

2321. 拼接数组的最大分数 - TLE

一开始以为是计算最长的连续非负数或非正数, 后来发现不对, 若中间夹着一个绝对值小的数, 是能把相邻区间打通的. 因此考虑作差后作用accumulate计算前缀和, 然后暴力遍历 (共(n+1)*n/2次). 下面用[60,60,60] [10,90,10]作为例子说明.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:
n = len(nums1) # 3
diff = [nums1[_] - nums2[_] for _ in range(n)] # [50, -30, 50]
temp = [list(itertools.accumulate(diff[_:])) for _ in range(n)] # [[50, 20, 70], [-30, 20], [50]], 正数表明第二个数组换进第二个数组的元素后获得的增量, 负数表明第一个数组换进第二个数组的元素后获得的增量, 因为这个没想清楚浪费了很长时间, 之后只要找temp里的最大和最小值, 然后还原出其对应替换元素的索引
p_value, p_idx1, p_idx2 = 0, None, None # 储存positive的最大值和索引
n_value, n_idx1, n_idx2 = 0, None, None # 储存negative的最大值和索引
for i, acc in enumerate(temp):
for j, v in enumerate(acc):
if v > p_value:
p_value = v
p_idx1 = i
p_idx2 = i + j + 1
if v < n_value:
n_value = v
n_idx1 = i
n_idx2 = i + j + 1
result1 = sum(nums2) + p_value # 正数是作用于第二个数列的
result2 = sum(nums1) - n_value # 负数时作用于第一个数列的
# p_value: 70, p_idx1: 0, p_idx2: 3, result1: 180
# n_value: -30, n_idx1: 1, n_idx2: 2, result2: 210
return max(result1, result2)

看解析后发现我的思路没问题, 而其子问题卜算时学过, 即53. 最大子数组和, 可以使用DP或者DC加速.

==2322. 从树中删除边的最小分数==

710. 黑名单中的随机数

Time Limit Error - Carlos

1
2
3
4
5
class Solution:  # 从长为len(blacklist)-n的列表里随机选择
def __init__(self, n: int, blacklist: List[int]):
self.whitelist = [_ for _ in range(n) if _ not in blacklist]
def pick(self) -> int:
return random.choice(self.whitelist)
1
2
3
4
5
6
class Solution:  # 在0到len(blacklist)-n-1范围内随机生成索引
def __init__(self, n: int, blacklist: List[int]):
self.whitelist = {i: _ for i, _ in enumerate(set(range(n)) - set(blacklist))}
self.len = len(self.whitelist)
def pick(self) -> int:
return self.whitelist.get(random.randint(0, self.len - 1))

黑名单中的随机数 - 力扣官方题解

方法一: 黑名单映射 (时Om空Om)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def __init__(self, n: int, blacklist: List[int]):
m = len(blacklist)
self.bound = w = n - m
black = {b for b in blacklist if b >= self.bound}
self.b2w = {}
for b in blacklist:
if b < self.bound:
while w in black:
w += 1
self.b2w[b] = w
w += 1
def pick(self) -> int:
x = randrange(self.bound)
return self.b2w.get(x, x)

观察一个简单的例子: n = 8, blacklist = [0, 3, 5], 表示为0, 1, 2, 3, 4 | 5, 6, 7. 设m为黑名单长度, 其中竖线为前n-m和元素和后m个元素的分割线, 可以发现竖线前黑名单元素个数与竖线后白名单元素个数相等, 构造一个映射. 最坏情况下竖线后均为黑名单, 此时复杂度为O(m), 比O(n-m)小.

💛 522. 最长特殊序列 II

模拟 - Carlos

Given two strings, find if first string is a subsequence of second: isSubSequence(string1, string2, len(string1), len(string2))输出string1是否为string2的子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def findLUSlength(self, strs: List[str]) -> int:
def isSubSequence(string1, string2, m, n):
# Base Cases
if m == 0: return True
if n == 0: return False
# If last characters of two strings are matching
if string1[m-1] == string2[n-1]: return isSubSequence(string1, string2, m-1, n-1)
# If last characters are not matching
return isSubSequence(string1, string2, m, n-1)
strs.sort(key=len, reverse=True) # 最长的特殊序列更可能在最长的序列产生, 排序后逐个判断
counter = Counter(strs) # 计数一下, 若最长序列只出现过一次, 那就是要找的特殊序列
temp = set() # 储存非特殊序列, 用来判断序列s是否是它们的子序列
for s in strs: # 遍历每个序列, 当其计数为1且非前面所有序列的子序列时, 返回其长度
if counter[s] == 1 and all([not isSubSequence(s, t, len(s), len(t)) for t in temp]): return len(s)
temp.add(s)
return -1

💛 324. 摆动排序 II

排序后列表操作调整 - Carlos

1
2
3
4
5
6
7
8
9
10
class Solution:  # 从大到小排列后, 把后半部分的序列逐个插入前半部分即可
def wiggleSort(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
nums.sort(reverse=True)
count = 0
for i in range(n := len(nums) // 2):
nums.insert(i + count, nums.pop(n + i))
count += 1

[Python/Java/TypeScript/Go] 排序贪心 - Benhao

1
2
3
4
5
6
7
class Solution:  # 思路与我一致, 写法更优雅
def wiggleSort(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
nums.sort()
nums[::2], nums[1::2] = nums[:(len(nums) + 1) // 2][::-1], nums[(len(nums) + 1)//2:][::-1]

💛 535. TinyURL 的加密与解密

练习Return - Carlos

1
2
3
4
5
6
7
8
9
10
11
12
class Codec:  # 不搞后端, 乱做一通
def encode(self, longUrl: str) -> str:
"""Encodes a URL to a shortened URL.
"""
return longUrl
def decode(self, shortUrl: str) -> str:
"""Decodes a shortened URL to its original URL.
"""
return shortUrl
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.decode(codec.encode(url))

TinyURL 的加密与解密 - 力扣官方题解

方法一:自增

方法二:哈希生成

方法三:随机生成

[Python/Java/TypeScript/Go] 模拟 - Benhao

高级方法, 指出用rsa库, 但平台没有, 转而使用了hashlib库.

💚 1175. 质数排列

判断质数 - Carlos

1
2
3
4
5
6
7
8
9
10
class Solution:
def numPrimeArrangements(self, n: int) -> int:
# [How to Check if a Number is Prime in Python]
# (https://geekflare.com/prime-number-in-python/#geekflare-toc-o-n-algorithm-to-check-for-prime-number-in-python)
def is_prime(n):
for i in range(2,int(math.sqrt(n))+1):
if (n % i) == 0: return False
return True if n > 1 else False
temp = sum(is_prime(_) for _ in range(1, n+1))
return (math.factorial(temp) * math.factorial(n - temp)) % (10 ** 9 + 7)