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, 使用带key的bisect_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)