leetcode每日一题

2024年

3月

1号_2369. 检查数组是否存在有效划分

给你一个下标从 0 开始的整数数组 nums ，你必须将数组划分为一个或多个 连续 子数组。

如果获得的这些子数组中每个都能满足下述条件 之一 ，则可以称其为数组的一种 有效 划分：

1. 子数组 恰 由 2 个相等元素组成，例如，子数组 [2,2] 。
2. 子数组 恰 由 3 个相等元素组成，例如，子数组 [4,4,4] 。
3. 子数组 恰 由 3 个连续递增元素组成，并且相邻元素之间的差值为 1 。例如，子数组 [3,4,5] ，但是子数组 [1,3,5] 不符合要求。

如果数组 至少 存在一种有效划分，返回 true ，否则，返回 false 。

class Solution:
    def validPartition(self, nums: List[int]) -> bool:
        #动态规划,注意子数组为连续子数组，所以有效划分必须连在一起
        n = len(nums)
        f = [True] + [False] * n   #f(i+1)表示能有效划分0-i
        for i, x in enumerate(nums):
            if i > 0 and f[i-1] and x == nums[i-1] or \
               i > 1 and f[i-2] and (x == nums[i-1] == nums[i-2] or 
                                   x == nums[i-1]+1 == nums[i-2]+2):
                f[i+1] = True
        return f[n]

2号_2368. 受限条件下可到达节点的数目

现有一棵由 n 个节点组成的无向树，节点编号从 0 到 n - 1 ，共有 n - 1 条边。

给你一个二维整数数组 edges ，长度为 n - 1 ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条边。另给你一个整数数组 restricted 表示 受限 节点。

在不访问受限节点的前提下，返回你可以从节点 0 到达的 最多 节点数目*。*

注意，节点 0 不 会标记为受限节点。

class Solution:
    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:
        restricted = set(restricted)
        road = [[] for _ in range(n)]
        for x,y in edges:
            if x not in restricted and y not in restricted:   #如果路之间不含无效节点，则连通
                road[x].append(y)
                road[y].append(x)
        def dfs(x: int, rep:int) -> int:   #dfs遍历
            res = 1
            for y in road[x]:
                if y != rep:        #避免x,y与y,x重复递归
                    res += dfs(y,x)
            return res
        return dfs(0,-1)

3号_225. 用队列实现栈

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

class MyStack:
    def __init__(self):
        self.lst=[]

    def push(self, x: int) -> None:
        self.lst.append(int(x))

    def pop(self) -> int:
        return self.lst.pop()

    def top(self) -> int:
        return self.lst[-1]

    def empty(self) -> bool:
        return not self.lst

4号_232. 用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：
你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

class MyQueue:
    def __init__(self):
        self.stack1 = []   #输入栈
        self.stack2 = []   #输出栈

    def push(self, x: int) -> None:   
        self.stack1.append(x)
        
    def pop(self) -> int:
        if not self.stack2:     #如果输出栈为空，则将输入栈的元素放到输出栈，栈内元素的顺序逆转
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2.pop()

    def peek(self) -> int:
        if not self.stack2:     #如果输出栈为空，则将输入栈的元素放到输出栈，栈内元素的顺序逆转
            while self.stack1:
                self.stack2.append(self.stack1.pop())            
        return self.stack2[-1]   #输出栈的栈顶元素为队列开头的元素

    def empty(self) -> bool:
        return not self.stack1 and not self.stack2

5号_1976.到达目的地的方案数

你在一个城市里，城市由 n 个路口组成，路口编号为 0 到 n - 1 ，某些路口之间有 双向 道路。输入保证你可以从任意路口出发到达其他任意路口，且任意两个路口之间最多有一条路。

给你一个整数 n 和二维整数数组 roads ，其中 roads[i] = [ui, vi, timei] 表示在路口 ui 和 vi 之间有一条需要花费 timei 时间才能通过的道路。你想知道花费 最少时间 从路口 0 出发到达路口 n - 1 的方案数。

请返回花费 最少时间 到达目的地的 路径数目 。由于答案可能很大，将结果对 109 + 7 取余 后返回。

class Solution:
    def countPaths(self, n: int, roads: List[List[int]]) -> int:
        #不能用*定义矩阵，否者列表元素的内存地址相同
        #a = [[float('inf')] * n] * n  #inf表示无穷大
        a = [[float('inf') for _ in range(n)] for _ in range(n)]   
        #a[x][y]表示x节点到y节点的距离，如果给定了，则为d，如果没给定，则为inf
        for x,y,d in roads:
            a[x][y] = d     
            a[y][x] = d
        dis = [float('inf')] * n   #dis[x]表示0到x节点的最短距离
        dis[0] = 0   #0节点到0节点的距离为0
        f = [0] * n     #表示0到x节点共有f[x]种最短路径
        f[0] = 1      #默认0到0节点有一种路径
        done = [False] * n   #表示节点是否已计算最短距离
        while True:
            x = -1  #重置x，以便进行遍历
            #找出x节点邻点的最小dis[y]
            for i,do in enumerate(done):
                if not do and (x<0 or dis[i]<dis[x]):  
                    x = i
            if x == n-1:   #当所有的节点都done了
                return f[-1]   #输出n-1节点最短路径数
            dx = dis[x]     #减少循环中调用dis[x]的次数
            for y,d in enumerate(a[x]):   #将x节点的邻点y的dis(y)确认
                new_dis = dx + d    #从0到x再到y
                #如果从x走更短，更改dis[y]，并且令f[y]=f[x]
                if new_dis < dis[y]:   
                    dis[y] = new_dis
                    f[y] = f[x]
                #如果从x走的长度一样，则y节点的最短路径加上f[x]条
                elif new_dis == dis[y]:   
                    f[y] = (f[y] + f[x]) % 1_000_000_007
            done[x] = True   #x节点已完成，标记为done      

6号_2917. 找出数组中的 K-or 值

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。

nums 中的 K-or 是一个满足以下条件的非负整数：

• 只有在 nums 中，至少存在 k 个元素的第 i 位值为 1 ，那么 K-or 中的第 i 位的值才是 1 。

返回 nums 的 K-or 值。

注意 ：对于整数 x ，如果 (2i AND x) == 2i ，则 x 中的第 i 位值为 1 ，其中 AND 为按位与运算符。

class Solution:
    def findKOr(self, nums: List[int], k: int) -> int:
        output = 0    
        i = 0     #用来判断位置
        n = max(nums)   
        while n>>i:   #当i超过n的位数时终止循环
            k_judge = 0
            for item in nums:
                if item>>i & 1:  #判断item的第i位是否为1
                        k_judge += 1
            if k_judge >= k:
                output += 2**i
            i = i+1
        return output

7号_2575. 找出字符串的可整除数组

给你一个下标从 0 开始的字符串 word ，长度为 n ，由从 0 到 9 的数字组成。另给你一个正整数 m 。

word 的 可整除数组 div 是一个长度为 n 的整数数组，并满足：

• 如果 word[0,...,i] 所表示的 数值 能被 m 整除，div[i] = 1
• 否则，div[i] = 0

返回 word 的可整除数组。

class Solution:
    def divisibilityArray(self, word: str, m: int) -> List[int]:
        res = []
        rem = 0
        for i in range(len(word)):
            rem = (rem * 10 + int(word[i])) % m  #word[:i]*10+word[i]=word[:i+1]=(nm+res)*10+word[i],n为整数
            if rem: res.append(0)
            else: res.append(1)
        return res

8号_2834. 找出美丽数组的最小和

给你两个正整数：n 和 target 。

如果数组 nums 满足下述条件，则称其为 美丽数组 。

• nums.length == n.
• nums 由两两互不相同的正整数组成。
• 在范围 [0, n-1] 内，不存在 两个 不同 下标 i 和 j ，使得 nums[i] + nums[j] == target 。

返回符合条件的美丽数组所可能具备的 最小 和，并对结果进行取模 109 + 7。

class Solution:
    def minimumPossibleSum(self, n: int, target: int) -> int:
        k = target // 2
        if n <= k:
            return (n+1)*n//2 % (10**9+7)
        else:
            return ((k+1)*k//2 + (2*target+n-k-1)*(n-k)//2) % (10**9+7)

9号_2386. 找出数组的第 K 大和

给你一个整数数组 nums 和一个 正 整数 k 。你可以选择数组的任一 子序列 并且对其全部元素求和。

数组的 第 k 大和 定义为：可以获得的第 k 个 最大 子序列和（子序列和允许出现重复）

返回数组的 第 k 大和 。

子序列是一个可以由其他数组删除某些或不删除元素排生而来的数组，且派生过程不改变剩余元素的顺序。

**注意：**空子序列的和视作 0 。

class Solution:
    def kSum(self, nums: List[int], k: int) -> int:
        #求出最大值s，并且把所有负数转为正数，这样统一只需要做减法即可
        sum = 0
        for i, x in enumerate(nums):
            if x >= 0:
                sum += x
            else:
                nums[i] = -x
        nums.sort()

        #以累加和来排列子序列，排到第k个终止
        stack = [(0,0)]  #空子序列,一个用来装子序列和,一个装下标
        for _ in range(k-1):   #已经有一个（0,0）,所以只需要循环k-1次
            s, i = heappop(stack)
            if i < len(nums):   #子序列下标不超过原序列下标
                # 在子序列的末尾添加 nums[i]
                heappush(stack, (s + nums[i] , i+1) )  # 下一个添加/替换的元素下标为 i+1
                if i:   # 替换子序列的末尾元素为 nums[i]
                    heappush(stack, (s + nums[i] - nums[i-1], i+1) )
        return sum - stack[0][0]        

10号_299. 猜数字游戏

你在和朋友一起玩 猜数字（Bulls and Cows）游戏，该游戏规则如下：

写出一个秘密数字，并请朋友猜这个数字是多少。朋友每猜测一次，你就会给他一个包含下述信息的提示：

• 猜测数字中有多少位属于数字和确切位置都猜对了（称为 “Bulls”，公牛），
• 有多少位属于数字猜对了但是位置不对（称为 “Cows”，奶牛）。也就是说，这次猜测中有多少位非公牛数字可以通过重新排列转换成公牛数字。

给你一个秘密数字 secret 和朋友猜测的数字 guess ，请你返回对朋友这次猜测的提示。

提示的格式为 "xAyB" ，x 是公牛个数， y 是奶牛个数，A 表示公牛，B 表示奶牛。

请注意秘密数字和朋友猜测的数字都可能含有重复数字。

class Solution:
    def getHint(self, secret: str, guess: str) -> str:
        bulls= 0
        s, g = Counter(), Counter()
        for x, y in zip(secret, guess):
            if x == y:
                bulls += 1
            else:
                s[x] += 1   #计数
                g[y] += 1   #计数
        cows = (s & g).total()   #Counter函数的与：相同key保留且取最小值；total：把所有的值相加
        return f'{bulls}A{cows}B'

11号_2129. 将标题首字母大写

给你一个字符串 title ，它由单个空格连接一个或多个单词组成，每个单词都只包含英文字母。请你按以下规则将每个单词的首字母 大写 ：

• 如果单词的长度为 1 或者 2 ，所有字母变成小写。
• 否则，将单词首字母大写，剩余字母变成小写。

请你返回 大写后 的 title 。

class Solution:
    def capitalizeTitle(self, title: str) -> str:
        title = title.lower().split(' ')
        for i,item in enumerate(title):
            if len(item) > 2:
                title[i] = item[0].upper() + item[1:]   #要变title而不是item
        return ' '.join(title)

12号_1261. 在受污染的二叉树中查找元素

给出一个满足下述规则的二叉树：

1. root.val == 0
2. 如果 treeNode.val == x 且 treeNode.left != null，那么 treeNode.left.val == 2 * x + 1
3. 如果 treeNode.val == x 且 treeNode.right != null，那么 treeNode.right.val == 2 * x + 2

现在这个二叉树受到「污染」，所有的 treeNode.val 都变成了 -1。

请你先还原二叉树，然后实现 FindElements 类：

• FindElements(TreeNode* root) 用受污染的二叉树初始化对象，你需要先把它还原。
• bool find(int target) 判断目标值 target 是否存在于还原后的二叉树中并返回结果。

def __init__(self, root: Optional[TreeNode]):
    #实际上，如果可以直接输出find的话，不需要把受污染树完全还原
    self.root = root   #将输入值赋给类属性
    self.root.val = 0  #将根节点值改为0
    queue = deque([self.root])
    #BFS遍历
    while queue:
        node = queue.popleft()
        if node.left:
            node.left.val = node.val * 2 + 1  #更改左子树值
            queue.append(node.left)
        if node.right:
            node.right.val = node.val * 2 + 2 #更改右子树值
            queue.append(node.right)


def find(self, target: int) -> bool:
    lst = []  #用作储存树遍历顺序的栈
    while target:  #将顺序标识反向放入栈中
        if target % 2:
            lst.append(1)
            target = (target - 1) // 2
        else:
            lst.append(0)
            target = (target - 2) // 2
    cur = self.root  #用局部变量储存类属性
    while lst:
        n = lst.pop()  #从栈中拿出顺序标识，这时为正向拿出
        if n == 1:
            if cur.left: cur = cur.left
            else: return False #子树为空说明不存在
        if n == 0:
            if cur.right: cur = cur.right
            else: return False
    return True

class FindElements:
    def __init__(self, root: Optional[TreeNode]):
        s = set()
        #dfs遍历
        def dfs(node: Optional[TreeNode], val: int) -> None:
            if node is None:
                return
            s.add(val) #在遍历时就把所有节点值储存起来
            dfs(node.left, val * 2 + 1)
            dfs(node.right, val * 2 + 2)
        dfs(root, 0)
        self.s = s

    def find(self, target: int) -> bool:
        return target in self.s

#思路和方法一一致，使用位运算极大简化代码
class FindElements:
    def __init__(self, root: Optional[TreeNode]):
        self.root = root

    def find(self, target: int) -> bool:
        target += 1  #相当于将所有的节点数+1
        cur = self.root  # 从根节点出发
        # 从次高位开始枚举
        for i in range(target.bit_length() - 2, -1, -1):  #bit_length求二进制位数
            bit = (target >> i) & 1  # target 第 i 位的比特值
            cur = cur.right if bit else cur.left
            if cur is None:  # 走到空节点，说明 target 不在二叉树中
                return False
        return True  # 没有走到空节点，说明 target 在二叉树中

13号_2864. 最大二进制奇数

给你一个 二进制 字符串 s ，其中至少包含一个 '1' 。

你必须按某种方式 重新排列 字符串中的位，使得到的二进制数字是可以由该组合生成的 最大二进制奇数 。

以字符串形式，表示并返回可以由给定组合生成的最大二进制奇数。

注意 返回的结果字符串 可以 含前导零。

class Solution:
    def maximumOddBinaryNumber(self, s: str) -> str:
        cnt = s.count('1')
        return '1' * (cnt - 1) + '0' * (len(s) - cnt) + '1'

14号_2789. 合并后数组中的最大元素

给你一个下标从 0 开始、由正整数组成的数组 nums 。

你可以在数组上执行下述操作 任意 次：

• 选中一个同时满足 0 <= i < nums.length - 1 和 nums[i] <= nums[i + 1] 的整数 i 。将元素 nums[i + 1] 替换为 nums[i] + nums[i + 1] ，并从数组中删除元素 nums[i] 。

返回你可以从最终数组中获得的 最大 元素的值。

class Solution:
    def maxArrayValue(self, nums: List[int]) -> int:
        for i in range(len(nums) - 1,0,-1):  #反向遍历，不遍历0
            if i > 0 and nums[i] >= nums[i-1]: #满足条件则执行题中操作
                nums[i-1] += nums[i]            
        return nums[0]  #如果nums[0]比nums[1]小，则会累加，如果nums[0]比nums[1]大，它本身就是最大的

15号_2312. 卖木头块

给你两个整数 m 和 n ，分别表示一块矩形木块的高和宽。同时给你一个二维整数数组 prices ，其中 prices[i] = [hi, wi, pricei] 表示你可以以 pricei 元的价格卖一块高为 hi 宽为 wi 的矩形木块。

每一次操作中，你必须按下述方式之一执行切割操作，以得到两块更小的矩形木块：

• 沿垂直方向按高度 完全 切割木块，或
• 沿水平方向按宽度 完全 切割木块

在将一块木块切成若干小木块后，你可以根据 prices 卖木块。你可以卖多块同样尺寸的木块。你不需要将所有小木块都卖出去。你 不能 旋转切好后木块的高和宽。

请你返回切割一块大小为 m x n 的木块后，能得到的 最多 钱数。

注意你可以切割木块任意次。

#暴力枚举，一个高宽为ij的木板，有三种情况，横切竖切和自身
class Solution:
    def sellingWood(self, m: int, n: int, prices: List[List[int]]) -> int:
        f = [[0]* (n+1) for _ in range(m+1)]
        for w, h, p in prices:
            f[w][h] = p
        for i in range(m+1):
            for j in range(n+1):
                f[i][j] = max(f[i][j],
                              max((f[i][k]+f[i][j-k] for k in range(1, j // 2 + 1)), default = 0), #横向切割
                              max((f[k][j]+f[i-k][j] for k in range(1, i// 2 + 1)), default = 0))  #纵向切割
        return f[m][n]                      

16号_2684. 矩阵中移动的最大次数

给你一个下标从 0 开始、大小为 m x n 的矩阵 grid ，矩阵由若干 正 整数组成。

你可以从矩阵第一列中的 任一 单元格出发，按以下方式遍历 grid ：

• 从单元格 (row, col) 可以移动到 (row - 1, col + 1)、(row, col + 1) 和 (row + 1, col + 1) 三个单元格中任一满足值 严格 大于当前单元格的单元格。

返回你在矩阵中能够 移动 的 最大 次数。

#朴素dfs遍历，每个遍历返回长度，最后比较长度
class Solution:
    def maxMoves(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        f = [[0] * n for _ in range(m)]  #哈希表存储对应dfs值，避免重复遍历
        def dfs(i,j):  #dfs遍历
            res1, res2, res3 = 0, 0, 0  #用来储存返回值，避免超出索引
            if j >= n-1:
                return 0
            if i > 0 and grid[i][j] < grid[i-1][j+1]:
                if not f[i-1][j+1]:  #如果为0，则递归后续
                    f[i-1][j+1] = dfs(i-1,j+1)
                res1 = 1 + f[i-1][j+1]  #如果f[i-1][j+1]有值，直接使用
            if grid[i][j] < grid[i][j+1]:
                if not f[i][j+1]:
                    f[i][j+1] = dfs(i,j+1)
                res2 = 1 + f[i][j+1]
            if i < m-1 and grid[i][j] < grid[i+1][j+1]:
                if not f[i+1][j+1]:
                    f[i+1][j+1] = dfs(i+1,j+1)
                res3 = 1 + f[i+1][j+1]
            return max(res1, res2, res3)
        lst = []
        for i in range(m):
            lst.append(dfs(i,0))
        return max(lst)

#dfs遍历，直接输出最长长度
class Solution:
    def maxMoves(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        ans = 0
        def dfs(i: int, j: int) -> None:
            nonlocal ans
            ans = max(ans, j)  #只需要确定ans的最大值，函数不需要返回任何值
            if ans == n - 1:  # ans 已达到最大值
                return
            for k in i - 1, i, i + 1:  # 向右上/右/右下走一步
                if 0 <= k < m and grid[k][j + 1] > grid[i][j]:
                    dfs(k, j + 1)
            grid[i][j] = 0  #使得后续遍历不再走该节点
        for i in range(m):
            dfs(i, 0)  # 从第一列的任一单元格出发
        return ans

#BFS遍历 
#一开始把所有 (i,0)(i,0)(i,0) 都加入一个列表。每一轮循环，遍历列表中的坐标，把右边这一列的能到达的格子坐标加入一个新列表。注意只有之前没入队的格子才能入队，，我们可以把要入队的格子值变为其相反数，从而判断哪些格子在队列中。此外，一个数一旦变成负数就不会比当前格子值大了，这可以保证一个格子值只会被标记（改成相反数）一次。
class Solution:
    def maxMoves(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        for row in grid:
            row[0] *= -1  # 入队标记
        for j in range(n - 1):
            for i, row in enumerate(grid):
                if row[j] > 0:  # 不在队列中
                    continue
                for k in i - 1, i, i + 1:
                    if 0 <= k < m and grid[k][j + 1] > -row[j]:
                        grid[k][j + 1] *= -1  # 入队标记
            if all(row[j + 1] > 0 for row in grid):  # 无法再往右走了
                return j
        return n - 1

17号_310. 最小高度树

给你一棵包含 n 个节点的树，标记为 0 到 n - 1 。给定数字 n 和一个有 n - 1 条无向边的 edges 列表（每一个边都是一对标签），其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条无向边。

可选择树中任何一个节点作为根。当选择节点 x 作为根节点时，设结果树的高度为 h 。在所有可能的树中，具有最小高度的树（即，min(h)）被称为 最小高度树 。

请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。

树的 高度 是指根节点和叶子节点之间最长向下路径上边的数量。

'''原理：设起点为u，第一次BFS找到的终点v一定是树的直径的一个端点。

证明：

如果u 是直径上的点，则v必然是直径的终点。（因为如果v不是的话，则必定存在另一个点w使得u到w的距离更长，则于BFS找到了v矛盾）
如果u不是直径上的点，则u到v的路径必然与树的直径相交，设交点为c，那么c到v的路径与直径的后半段重合。所以v一定是直径的一个端点，因此从v进行BFS得到的一定是直径长度。'''

class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        if n == 1:
            return [0]

        d = [[] for _ in range(n)]
        for x, y in edges:
            d[x].append(y)
            d[y].append(x)
        father = [0] * n

        def bfs(start):
            vis = [False] * n
            vis[start] = True
            qe = deque([start])
            while qe:
                x = qe.popleft()
                for y in d[x]:
                    if not vis[y]: #避免重复遍历
                        vis[y] = True
                        father[y] = x #记录父节点
                        qe.append(y)
            return x
        #先找离起始点最远的点x，再找离x最远的点y，xy即为最远距离
        x = bfs(0)
        y = bfs(x)

        path = []
        father[x] = -1
        while y != -1:
            path.append(y)
            y = father[y]
        m = len(path)
        return [path[m//2]] if m % 2 else [path[m//2 - 1], path[m//2]]

18号_303. 区域和检索 - 数组不可变

给定一个整数数组 nums，处理以下类型的多个查询:

1. 计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的 和 ，其中 left <= right

实现 NumArray 类：

• NumArray(int[] nums) 使用数组 nums 初始化对象
• int sumRange(int i, int j) 返回数组 nums 中索引 left 和 right 之间的元素的 总和 ，包含 left 和 right 两点（也就是 nums[left] + nums[left + 1] + ... + nums[right] )

class NumArray:

    def __init__(self, nums: List[int]):
        n = len(nums)
        self.s = [0] * (n+1)  #为了避免nums(left)=0的情况，设s[0]=0
        for i in range(1,n+1):
            self.s[i] = self.s[i-1] + nums[i-1]

    def sumRange(self, left: int, right: int) -> int:
        return self.s[right+1] - self.s[left] #通过前缀和的差来输出累加和，使得时间复杂度为O(1)

19号_1793. 好子数组的最大分数

给你一个整数数组 nums **（下标从 0 开始）**和一个整数 k 。

一个子数组 (i, j) 的 分数 定义为 min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1) 。一个 好 子数组的两个端点下标需要满足 i <= k <= j 。

请你返回 好 子数组的最大可能 分数 。

#双指针
class Solution:
    def maximumScore(self, nums: List[int], k: int) -> int:
        i = j = k
        n = len(nums)
        s = h = nums[k]
        for _ in range(n-1):  #必须遍历所有可能，而不是加终止条件
            if j == n-1 or (i and nums[i-1] >= nums[j+1]): #and的优先级比or高，实际上可以不加括号
                h = min(h,nums[i-1])
                i -= 1
            else:
                h = min(h,nums[j+1])
                j += 1
            print(i,j,h,s)
            s = max(s, h*(j-i+1))
        return s

1969. 数组元素的最小非零乘积

给你一个正整数 p 。你有一个下标从 1 开始的数组 nums ，这个数组包含范围 [1, 2p - 1] 内所有整数的二进制形式（两端都 包含）。你可以进行以下操作 任意 次：

• 从 nums 中选择两个元素 x 和 y 。
• 选择 x 中的一位与 y 对应位置的位交换。对应位置指的是两个整数 相同位置 的二进制位。

比方说，如果 x = 11***0***1 且 y = 00***1***1 ，交换右边数起第 2 位后，我们得到 x = 11***1***1 和 y = 00***0***1 。

请你算出进行以上操作 任意次 以后，nums 能得到的 最小非零 乘积。将乘积对 109 + 7 取余 后返回。

**注意：**答案应为取余 之前 的最小值。

class Solution:
    def minNonZeroProduct(self, p: int) -> int:
        #本质是个算法问题，更像个数学问题
        mod = 10**9 + 7
        m = 2**p - 1
        #可以把除了2**p-1以外的项两辆配对，操作之后的最小配对乘积为(2**p - 2)**(2**(p-1) - 1)
        return (m * pow(m-1, m>>1, mod)) % mod

21号_2671. 频率跟踪器

请你设计并实现一个能够对其中的值进行跟踪的数据结构，并支持对频率相关查询进行应答。

实现 FrequencyTracker 类：

• FrequencyTracker()：使用一个空数组初始化 FrequencyTracker 对象。
• void add(int number)：添加一个 number 到数据结构中。
• void deleteOne(int number)：从数据结构中删除一个 number 。数据结构 可能不包含 number ，在这种情况下不删除任何内容。
• bool hasFrequency(int frequency): 如果数据结构中存在出现 frequency 次的数字，则返回 true，否则返回 false。

class FrequencyTracker:

    def __init__(self):
        self.cnt = Counter()   #统计number出现频率
        self.freq = Counter()  #统计频率的出现次数

    def add(self, number: int, delta=1) -> None: #delta默认为1，为delete嵌套做准备
        self.freq[self.cnt[number]] -= 1  #将number原频率的出现次数减一
        self.cnt[number] += delta             #将number频率加一
        self.freq[self.cnt[number]] += 1  #将number新频率的出现次数加一

    def deleteOne(self, number: int) -> None:
        if self.cnt[number]:  #如果number出现频率不为0，即number在数组中
            self.add(number, -1)  #套用add函数，加上负一等于减一，Counter减到0会自动删除    

    def hasFrequency(self, frequency: int) -> bool:
        return self.freq[frequency] > 0 #如果不存在，Counter默认返回0
# Your FrequencyTracker object will be instantiated and called as such:
# obj = FrequencyTracker()
# obj.add(number)
# obj.deleteOne(number)
# param_3 = obj.hasFrequency(frequency)

22号_2617. 网格图中最少访问的格子数

给你一个下标从 0 开始的 m x n 整数矩阵 grid 。你一开始的位置在 左上角 格子 (0, 0) 。

当你在格子 (i, j) 的时候，你可以移动到以下格子之一：

• 满足 j < k <= grid[i][j] + j 的格子 (i, k) （向右移动），或者
• 满足 i < k <= grid[i][j] + i 的格子 (k, j) （向下移动）。

请你返回到达 右下角 格子 (m - 1, n - 1) 需要经过的最少移动格子数，如果无法到达右下角格子，请你返回 -1 。

class Solution:
    def minimumVisitedCells(self, grid: List[List[int]]) -> int:
        #明白思路了，暂时放弃查看代码
        m, n = len(grid), len(grid[0])
        col_stacks = [[] for _ in range(n)]  # 每列的单调栈
        for i in range(m - 1, -1, -1):
            row_st = []  # 当前行的单调栈
            for j in range(n - 1, -1, -1):
                g = grid[i][j]
                col_st = col_stacks[j]
                mn = inf if i < m - 1 or j < n - 1 else 1
                if g:  # 可以向右/向下跳
                    # 在单调栈上二分查找最优转移来源
                    k = bisect_left(row_st, -(j + g), key=lambda p: p[1])
                    if k < len(row_st):
                        mn = row_st[k][0] + 1
                    k = bisect_left(col_st, -(i + g), key=lambda p: p[1])
                    if k < len(col_st):
                        mn = min(mn, col_st[k][0] + 1)
                if mn < inf:
                    # 插入单调栈
                    while row_st and mn <= row_st[-1][0]:
                        row_st.pop()
                    row_st.append((mn, -j))  # 保证下标单调递增，方便调用 bisect_left
                    while col_st and mn <= col_st[-1][0]:
                        col_st.pop()
                    col_st.append((mn, -i))  # 保证下标单调递增，方便调用 bisect_left
        return mn if mn < inf else -1  # 最后一个算出的 mn 就是 f[0][0]

23号_2549. 统计桌面上的不同数字

给你一个正整数 n ，开始时，它放在桌面上。在 109 天内，每天都要执行下述步骤：

• 对于出现在桌面上的每个数字 x ，找出符合 1 <= i <= n 且满足 x % i == 1 的所有数字 i 。
• 然后，将这些数字放在桌面上。

返回在 109 天之后，出现在桌面上的 不同 整数的数目。

注意：

• 一旦数字放在桌面上，则会一直保留直到结束。
• % 表示取余运算。例如，14 % 3 等于 2 。

class Solution:
    def distinctIntegers(self, n: int) -> int:
        return n-1 if n>1 else 1

24号_322. 零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

#动态规划
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float('inf')] * (amount+1)
        dp[0] = 0
        for i in range(1,amount+1): #先amount再coins是排列，先coins再amount是组合
            for coin in coins:
                if coin <= i:
                    dp[i] = min(dp[i], dp[i-coin]+1)
        return dp[amount] if dp[amount] < float('inf') else -1

#递归
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        @cache #缓存器
        def dfs(i,a):
            if i < 0: return 0 if a == 0 else inf
            if a < coins[i]: return dfs(i-1,a)
            return min(dfs(i-1,a), dfs(i,a-coins[i])+1)
        ans = dfs(len(coins)-1, amount)
        return ans if ans < inf else -1

25号_518. 零钱兑换 II

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

#动态规划
class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1
        for coin in coins: #先amount再coins是排列，先coins再amount是组合
            for i in range(1,amount+1):
                if i >= coin:
                    dp[i] += dp[i-coin]
        return dp[amount]

26号_2642. 设计可以求最短路径的图类

给你一个有 n 个节点的 有向带权 图，节点编号为 0 到 n - 1 。图中的初始边用数组 edges 表示，其中 edges[i] = [fromi, toi, edgeCosti] 表示从 fromi 到 toi 有一条代价为 edgeCosti 的边。

请你实现一个 Graph 类：

• Graph(int n, int[][] edges) 初始化图有 n 个节点，并输入初始边。
• addEdge(int[] edge) 向边集中添加一条边，其中 edge = [from, to, edgeCost] 。数据保证添加这条边之前对应的两个节点之间没有有向边。
• int shortestPath(int node1, int node2) 返回从节点 node1 到 node2 的路径 最小 代价。如果路径不存在，返回 -1 。一条路径的代价是路径中所有边代价之和

class Graph:

    def __init__(self, n: int, edges: List[List[int]]):
        self.n = n
        self.f = [[inf] * n for _ in range(n)]
        for x, y, d in edges:
            self.f[x][y] = d

    def addEdge(self, edge: List[int]) -> None:
        self.f[edge[0]][edge[1]] = edge[2]

    def shortestPath(self, node1: int, node2: int) -> int:
        done = [False] * self.n
        dist = [inf] * self.n
        dist[node1] = 0
        while True:
            x = -1 #重置x
            for i, do in enumerate(done):
                if not do and (x<0 or dist[i] < dist[x]):
                    x = i  
            if x == node2: return dist[node2] if dist[node2] < inf else -1  
            for y, d in enumerate(self.f[x]):
                new_dist = dist[x] + d
                if new_dist < dist[y]:
                    dist[y] = new_dist
            done[x] = True

27号_2580. 统计将重叠区间合并成组的方案数

给你一个二维整数数组 ranges ，其中 ranges[i] = [starti, endi] 表示 starti 到 endi 之间（包括二者）的所有整数都包含在第 i 个区间中。

你需要将 ranges 分成 两个 组（可以为空），满足：

• 每个区间只属于一个组。
• 两个有 交集 的区间必须在 同一个 组内。

如果两个区间有至少 一个 公共整数，那么这两个区间是 有交集 的。

• 比方说，区间 [1, 3] 和 [2, 5] 有交集，因为 2 和 3 在两个区间中都被包含。

请你返回将 ranges 划分成两个组的 总方案数 。由于答案可能很大，将它对 109 + 7 取余 后返回。

class Solution:
    def countWays(self, ranges: List[List[int]]) -> int:
        ranges.sort(key = lambda x: x[0]) #排序
        res, max_r = 1, -1
        for l, r in ranges:
            if l > max_r: #无法合并区间
                res = res * 2 % (10**9+7) #每有一个无法合并的区间，就多一个独立区间
            max_r = max(max_r, r) #更新区间右端点
        return res

28号_1997. 访问完所有房间的第一天

你需要访问 n 个房间，房间从 0 到 n - 1 编号。同时，每一天都有一个日期编号，从 0 开始，依天数递增。你每天都会访问一个房间。

最开始的第 0 天，你访问 0 号房间。给你一个长度为 n 且 下标从 0 开始 的数组 nextVisit 。在接下来的几天中，你访问房间的 次序 将根据下面的 规则 决定：

• 假设某一天，你访问 i 号房间。
• 如果算上本次访问，访问 i 号房间的次数为 奇数 ，那么 第二天 需要访问 nextVisit[i] 所指定的房间，其中 0 <= nextVisit[i] <= i 。
• 如果算上本次访问，访问 i 号房间的次数为 偶数 ，那么 第二天 需要访问 (i + 1) mod n 号房间。

请返回你访问完所有房间的第一天的日期编号。题目数据保证总是存在这样的一天。由于答案可能很大，返回对 109 + 7 取余后的结果。

#动态规划，没规划出来
class Solution:
    def firstDayBeenInAllRooms(self, nextVisit: List[int]) -> int:
        dp = [0] * len(nextVisit)
        for i, j in enumerate(nextVisit[:-1]):
            dp[i+1] = (dp[i] * 2 - dp[j] + 2 ) % 1_000_000_007 
        return dp[-1]

29号_2908. 元素和最小的山形三元组 I

给你一个下标从 0 开始的整数数组 nums 。

如果下标三元组 (i, j, k) 满足下述全部条件，则认为它是一个 山形三元组 ：

• i < j < k
• nums[i] < nums[j] 且 nums[k] < nums[j]

请你找出 nums 中 元素和最小 的山形三元组，并返回其 元素和 。如果不存在满足条件的三元组，返回 -1 。

#时间O(N2),空间O(1)
class Solution:
    def minimumSum(self, nums: List[int]) -> int:
        res = float('inf')
        for i in range(1,len(nums)-1):
            m, l, r =nums[i], min(nums[:i]), min(nums[i+1:])
            if l<m and r<m: res = min(res, l+r+m)
        return res if res < float('inf') else -1

#时间O(N),空间O(N)
class Solution:
    def minimumSum(self, nums: List[int]) -> int:
        n = len(nums)
        suf = [0] * n
        suf[-1] = nums[-1]  # 后缀最小值
        for i in range(n - 2, 1, -1):
            suf[i] = min(suf[i + 1], nums[i])

        ans = inf
        pre = nums[0]  # 前缀最小值
        for j in range(1, n - 1):
            if pre < nums[j] > suf[j + 1]:  # 山形
                ans = min(ans, pre + nums[j] + suf[j + 1])  # 更新答案
            pre = min(pre, nums[j])
        return ans if ans < inf else -1

30号_2952. 需要添加的硬币的最小数量

给你一个下标从 0 开始的整数数组 coins，表示可用的硬币的面值，以及一个整数 target 。

如果存在某个 coins 的子序列总和为 x，那么整数 x 就是一个 可取得的金额 。

返回需要添加到数组中的 任意面值 硬币的 最小数量 ，使范围 [1, target] 内的每个整数都属于 可取得的金额 。

数组的 子序列 是通过删除原始数组的一些（可能不删除）元素而形成的新的 非空 数组，删除过程不会改变剩余元素的相对位置。

class Solution:
    def minimumAddedCoins(self, coins: List[int], target: int) -> int:
        coins.sort()
        s, i, res = 1, 0, 0
        while s <= target: #贪心，考虑每个coin[i]所能覆盖的范围
            if i < len(coins) and coins[i] <= s: 
                s += coins[i]
                i += 1
            else:
                s *= 2
                res += 1
        return res

31号_331. 验证二叉树的前序序列化

序列化二叉树的一种方法是使用 前序遍历 。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。

例如，上面的二叉树可以被序列化为字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#"，其中 # 代表一个空节点。

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

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

你可以认为输入格式总是有效的

• 例如它永远不会包含两个连续的逗号，比如 "1,,3" 。

**注意：**不允许重建树。

#队列
class Solution:
    def isValidSerialization(self, preorder: str) -> bool:
        preorder = preorder.split(',')[::-1]
        que = deque([preorder.pop()])
        while que:
            node = que.popleft()
            if node != '#':
                if len(preorder) <= 1: return False
                que.append(preorder.pop())
                que.append(preorder.pop())
        return False if preorder else True

#栈
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('#')

4月

1号_2810. 故障键盘

你的笔记本键盘存在故障，每当你在上面输入字符 'i' 时，它会反转你所写的字符串。而输入其他字符则可以正常工作。

给你一个下标从 0 开始的字符串 s ，请你用故障键盘依次输入每个字符。

返回最终笔记本屏幕上输出的字符串。

#暴力
class Solution:
    def finalString(self, s: str) -> str:
        ans = []
        for item in s:
            if item == 'i': ans = ans[::-1]
            else: ans.append(item)               
        return ''.join(ans)

#双向队列
class Solution:
    def finalString(self, s: str) -> str:
        qe = deque()
        tail = True #判断从尾部加元素还是从头部加
        for c in s:
            if c == 'i':
                tail = not tail #修改方向
            elif tail:
                qe.append(c)
            else:
                qe.appendleft(c)
        return ''.join(qe if tail else reversed(qe))

2号_894. 所有可能的真二叉树

给你一个整数 n ，请你找出所有可能含 n 个节点的 真二叉树 ，并以列表形式返回。答案中每棵树的每个节点都必须符合 Node.val == 0 。

答案的每个元素都是一棵真二叉树的根节点。你可以按 任意顺序 返回最终的真二叉树列表**。**

真二叉树 是一类二叉树，树中每个节点恰好有 0 或 2 个子节点。

#分治，递归
class Solution:
    @cache
    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:
        res = []
        if n % 2 == 0: return res
        if n == 1: 
            res.append(TreeNode(0))
            return res   
        for k in range(1,n,2):
            left = self.allPossibleFBT(k)
            right = self.allPossibleFBT(n-1-k)
            for l in left:
                for r in right:
                    node = TreeNode(0,l,r)
                    res.append(node)
        return res

#dp
class Solution:
    def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:
        if n % 2 == 0: return []
        l = n//2 + 1
        dp = [[] for _ in range(l)]
        dp[0] = [TreeNode(0)]
        for i in range(1,l):
            for j in range(i):
                for l in dp[j]:
                    for r in dp[i-j-1]:
                        dp[i].append(TreeNode(0,l,r))
        return dp[-1]

3号_1379. 找出克隆二叉树中的相同节点

给你两棵二叉树，原始树 original 和克隆树 cloned，以及一个位于原始树 original 中的目标节点 target。

其中，克隆树 cloned 是原始树 original 的一个 副本 。

请找出在树 cloned 中，与 target 相同 的节点，并返回对该节点的引用（在 C/C++ 等有指针的语言中返回 节点指针，其他语言返回节点本身）。

**注意：**你 不能 对两棵二叉树，以及 target 节点进行更改。只能 返回对克隆树 cloned 中已有的节点的引用

class Solution:
    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
        if not original: return
        if original == target: return cloned
        #cloned是克隆树，和original不同，不能让它们相等
        return self.getTargetCopy(original.left, cloned.left, target) or \
               self.getTargetCopy(original.right, cloned.right, target)

4号_2192. 有向无环图中一个节点的所有祖先

给你一个正整数 n ，它表示一个 有向无环图 中节点的数目，节点编号为 0 到 n - 1 （包括两者）。

给你一个二维整数数组 edges ，其中 edges[i] = [fromi, toi] 表示图中一条从 fromi 到 toi 的单向边。

请你返回一个数组 answer，其中 answer[i]是第 i 个节点的所有 祖先 ，这些祖先节点 升序 排序。

如果 u 通过一系列边，能够到达 v ，那么我们称节点 u 是节点 v 的 祖先 节点。

#正向dfs，把start节点放到每个后续节点的ans中，每个节点作为start遍历
class Solution:
    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:
        g = [[] for _ in range(n)]
        for x,y in edges:
            g[x].append(y)
        ans = [[] for _ in range(n)]
        visit = [-1] * n
        
        def dfs(x):
            visit[x] = start
            for y in g[x]:
                if visit[y] != start:
                    ans[y].append(start)
                    dfs(y)
                    
        for start in range(n):
            dfs(start)
        return ans

#逆向dfs
class Solution:
    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:
        g = [[] for _ in range(n)]
        for x,y in edges:
            g[y].append(x)  #反向dfs
        ans = [[] for _ in range(n)]

        def dfs(y):
            visit[y] = True
            for x in g[y]:
                if not visit[x]:
                    dfs(x)
        
        for i in range(n):
            visit = [False] * n
            dfs(i)
            visit[i] = False #除了起始点以外的途径点都为True
            ans[i] = [j for j,b in enumerate(visit) if b] #将途经点添加
        return ans

5号_1026. 节点与其祖先之间的最大差值

给定二叉树的根节点 root，找出存在于 不同 节点 A 和 B 之间的最大值 V，其中 V = |A.val - B.val|，且 A 是 B 的祖先。

（如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）

#递+最大最小值
class Solution:
    def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
        res = 0
        def dfs(root, mn, mx):
            if not root: 
                nonlocal res
                res = max(res, mx - mn)
                return       
            mn = min(mn, root.val)
            mx = max(mx, root.val)          
            dfs(root.left, mn, mx)
            dfs(root.right, mn, mx)
        dfs(root, root.val, root.val)
        return res

#归+最大最小值
class Solution:
    def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
        res = 0
        def dfs(root):
            if not root: 
                return inf, -inf
            l_mn, l_mx = dfs(root.left)
            r_mn, r_mx = dfs(root.right)
            mn = min(root.val, l_mn, r_mn)
            mx = max(root.val, l_mx, r_mx)
            nonlocal res
            res = max(res, root.val-mn, mx-root.val)          
            return mn, mx
        dfs(root)
        return res

6号_1483. 树节点的第 K 个祖先

给你一棵树，树上有 n 个节点，按从 0 到 n-1 编号。树以父节点数组的形式给出，其中 parent[i] 是节点 i 的父节点。树的根节点是编号为 0 的节点。

树节点的第 k 个祖先节点是从该节点到根节点路径上的第 k 个节点。

实现 TreeAncestor 类：

• TreeAncestor（int n， int[] parent） 对树和父数组中的节点数初始化对象。
• getKthAncestor``(int node, int k) 返回节点 node 的第 k 个祖先节点。如果不存在这样的祖先节点，返回 -1 。

class TreeAncestor:

    def __init__(self, n: int, parent: List[int]):
        m = n.bit_length() - 1 #位数减1
        pa = [[p] + [-1] * m for p in parent] #有点dp的思想在里面
        for j in range(m):
            for i in range(n):
                if pa[i][j] != -1: #等于-1说明已经越过根节点，无需再找爷节点
                    pa[i][j+1] = pa[pa[i][j]][j]
        self.pa = pa       

    def getKthAncestor(self, node: int, k: int) -> int:
        for i in range(k.bit_length()):
            if (k >> i) & 1: 
                node = self.pa[node][i]
                if node == -1: break
        return node

7号_1600. 王位继承顺序

一个王国里住着国王、他的孩子们、他的孙子们等等。每一个时间点，这个家庭里有人出生也有人死亡。

这个王国有一个明确规定的王位继承顺序，第一继承人总是国王自己。我们定义递归函数 Successor(x, curOrder) ，给定一个人 x 和当前的继承顺序，该函数返回 x 的下一继承人。

Successor(x, curOrder):
    如果 x 没有孩子或者所有 x 的孩子都在 curOrder 中：
        如果 x 是国王，那么返回 null
        否则，返回 Successor(x 的父亲, curOrder)
    否则，返回 x 不在 curOrder 中最年长的孩子

比方说，假设王国由国王，他的孩子 Alice 和 Bob （Alice 比 Bob 年长）和 Alice 的孩子 Jack 组成。

1. 一开始， curOrder 为 ["king"].
2. 调用 Successor(king, curOrder) ，返回 Alice ，所以我们将 Alice 放入 curOrder 中，得到 ["king", "Alice"] 。
3. 调用 Successor(Alice, curOrder) ，返回 Jack ，所以我们将 Jack 放入 curOrder 中，得到 ["king", "Alice", "Jack"] 。
4. 调用 Successor(Jack, curOrder) ，返回 Bob ，所以我们将 Bob 放入 curOrder 中，得到 ["king", "Alice", "Jack", "Bob"] 。
5. 调用 Successor(Bob, curOrder) ，返回 null 。最终得到继承顺序为 ["king", "Alice", "Jack", "Bob"] 。

通过以上的函数，我们总是能得到一个唯一的继承顺序。

请你实现 ThroneInheritance 类：

• ThroneInheritance(string kingName) 初始化一个 ThroneInheritance 类的对象。国王的名字作为构造函数的参数传入。
• void birth(string parentName, string childName) 表示 parentName 新拥有了一个名为 childName 的孩子。
• void death(string name) 表示名为 name 的人死亡。一个人的死亡不会影响 Successor 函数，也不会影响当前的继承顺序。你可以只将这个人标记为死亡状态。
• string[] getInheritanceOrder() 返回 除去 死亡人员的当前继承顺序列表

class ThroneInheritance:

    def __init__(self, kingName: str):
        self.king = kingName
        self.son = {kingName:[]}
        self.dead = set() #不能和后面的death函数重名

    def birth(self, parentName: str, childName: str) -> None:
        self.son[parentName].append(childName)
        self.son[childName] = []

    def death(self, name: str) -> None:
        self.dead.add(name)

    def getInheritanceOrder(self) -> List[str]:
        def dfs(cur):
            if cur not in self.dead:
                res.append(cur)
            for son in self.son[cur]:
                dfs(son)
        res = []
        dfs(self.king)
        return res

8号_2009. 使数组连续的最少操作数

给你一个整数数组 nums 。每一次操作中，你可以将 nums 中 任意 一个元素替换成 任意 整数。

如果 nums 满足以下条件，那么它是 连续的 ：

• nums 中所有元素都是 互不相同 的。
• nums 中 最大 元素与 最小 元素的差等于 nums.length - 1 。

比方说，nums = [4, 2, 5, 3] 是 连续的 ，但是 nums = [1, 2, 3, 5, 6] 不是连续的 。

请你返回使 nums 连续 的 最少 操作次数

#先去重排序，然后找到可操作最长连续子数组
class Solution:
    def minOperations(self, nums: List[int]) -> int:
        n = len(nums) #元素总个数
        nums = list(set(nums))
        m = len(nums) #不重复元素个数
        nums.sort()
        max_len = dp = 1                
        for i in range(1,m):
            if nums[i] + 1 - nums[i-dp] <= n : #子数组不连续处空的元素可以由数组中其他元素补充
                dp += 1  
            else:
                for j in range(i-dp+1, i+1):
                    if nums[i] + 1 - nums[j] <= n:
                        dp = i-j+1
                        break
            max_len = max(max_len, dp)
        return n - max_len

#先去重排序，滑动窗口
class Solution:
    def minOperations(self, nums: List[int]) -> int:
        n = len(nums) #元素总个数
        nums = list(set(nums))
        m = len(nums) #不重复元素个数
        nums.sort()
        max_len = tmp = 1
        i = j = 0             
        while j < m:
            tmp = j - i + 1
            if nums[j] - nums[i] + 1 > n: 
                i += 1
                tmp -= 1
            else: 
                j += 1
            max_len = max(max_len, tmp)
        return n - max_len

9号_2529. 正整数和负整数的最大计数

给你一个按 非递减顺序 排列的数组 nums ，返回正整数数目和负整数数目中的最大值。

• 换句话讲，如果 nums 中正整数的数目是 pos ，而负整数的数目是 neg ，返回 pos 和 neg二者中的最大值。

注意：0 既不是正整数也不是负整数。

#遍历
class Solution:
    def maximumCount(self, nums: List[int]) -> int:
        positive = negative = 0
        for num in nums:
            if num > 0: positive += 1
            elif num < 0: negative += 1
        return max(positive, negative)

#二分
import bisect
class Solution:
    def maximumCount(self, nums: List[int]) -> int:
        neg = bisect_left(nums, 0)
        pos = len(nums) - bisect_right(nums, 0)
        return max(neg, pos)

10号_1702. 修改后的最大二进制字符串

给你一个二进制字符串 binary ，它仅有 0 或者 1 组成。你可以使用下面的操作任意次对它进行修改：

• 操作 1 ：如果二进制串包含子字符串 “00”，你可以用 "10"将其替换。
  • 比方说， "**00**010" -> "**10**010"
• 操作 2 ：如果二进制串包含子字符串 “10”，你可以用 "01"将其替换。
  • 比方说， "000**10**" -> "000**01**"

请你返回执行上述操作任意次以后能得到的 最大二进制字符串 。如果二进制字符串 x 对应的十进制数字大于二进制字符串 y 对应的十进制数字，那么我们称二进制字符串 x 大于二进制字符串 y 。

class Solution:
    def maximumBinaryString(self, binary: str) -> str:
        i = binary.find('0')
        if i < 0:  # binary 全是 '1'
            return binary
        cnt1 = binary.count('1', i)  # 统计 binary[i:] 中 '1' 的个数
        return '1' * (len(binary) - 1 - cnt1) + '0' + '1' * cnt1

11号_1766. 互质树

给你一个 n 个节点的树（也就是一个无环连通无向图），节点编号从 0 到 n - 1 ，且恰好有 n - 1 条边，每个节点有一个值。树的 根节点 为 0 号点。

给你一个整数数组 nums 和一个二维数组 edges 来表示这棵树。nums[i] 表示第 i 个点的值，edges[j] = [uj, vj] 表示节点 uj 和节点 vj 在树中有一条边。

当 gcd(x, y) == 1 ，我们称两个数 x 和 y 是 互质的 ，其中 gcd(x, y) 是 x 和 y 的 最大公约数 。

从节点 i 到 根 最短路径上的点都是节点 i 的祖先节点。一个节点 不是 它自己的祖先节点。

请你返回一个大小为 n 的数组 ans ，其中 ans[i]是离节点 i 最近的祖先节点且满足 nums[i] 和 nums[ans[i]] 是 互质的 ，如果不存在这样的祖先节点，ans[i] 为 -1

class Solution:
    def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:
        n = len(nums)
        # 初始化
        gcds = [[] for _ in range(51)] #注意题目，nums[i] <= 50
        tmp = [[] for _ in range(51)]
        ans = [-1] * n
        dep = [-1] * n 
        g = [[] for _ in range(n)]

        def dfs(x: int, depth: int):
            dep[x] = depth
            for val in gcds[nums[x]]:
                if not tmp[val]:
                    continue
                las = tmp[val][-1]
                if ans[x] == -1 or dep[las] > dep[ans[x]]:
                    ans[x] = las
            tmp[nums[x]].append(x)
            for val in g[x]:
                if dep[val] == -1: # 被访问过的点dep不为-1
                    dfs(val, depth + 1)
            tmp[nums[x]].pop()

        for i in range(1, 51):
            for j in range(1, 51):
                if math.gcd(i, j) == 1:
                    gcds[i].append(j)
        for x, y in edges:
            g[x].append(y)
            g[y].append(x)
        dfs(0, 1)
        return ans

12号__2923. 找到冠军 I

一场比赛中共有 n 支队伍，按从 0 到 n - 1 编号。

给你一个下标从 0 开始、大小为 n * n 的二维布尔矩阵 grid 。对于满足 0 <= i, j <= n - 1 且 i != j 的所有 i, j ：如果 grid[i][j] == 1，那么 i 队比 j 队 强 ；否则，j 队比 i 队 强 。

在这场比赛中，如果不存在某支强于 a 队的队伍，则认为 a 队将会是 冠军 。

返回这场比赛中将会成为冠军的队伍。

class Solution:
    def findChampion(self, grid: List[List[int]]) -> int:
        for j, col in enumerate(zip(*grid)):
            if 1 not in col:
                return j

#打擂台
class Solution:
    def findChampion(self, grid: List[List[int]]) -> int:
        ans = 0
        for i, row in enumerate(grid):
            if row[ans]:
                ans = i
        return ans

13号_2924. 找到冠军 II

一场比赛中共有 n 支队伍，按从 0 到 n - 1 编号。每支队伍也是 有向无环图（DAG） 上的一个节点。

给你一个整数 n 和一个下标从 0 开始、长度为 m 的二维整数数组 edges 表示这个有向无环图，其中 edges[i] = [ui, vi] 表示图中存在一条从 ui 队到 vi 队的有向边。

从 a 队到 b 队的有向边意味着 a 队比 b 队 强 ，也就是 b 队比 a 队 弱 。

在这场比赛中，如果不存在某支强于 a 队的队伍，则认为 a 队将会是 冠军 。

如果这场比赛存在 唯一 一个冠军，则返回将会成为冠军的队伍。否则，返回 -1 。

注意

• 环 是形如 a1, a2, ..., an, an+1 的一个序列，且满足：节点 a1 与节点 an+1 是同一个节点；节点 a1, a2, ..., an 互不相同；对于范围 [1, n] 中的每个 i ，均存在一条从节点 ai 到节点 ai+1 的有向边。
• 有向无环图 是不存在任何环的有向图。

#dfs
class Solution:
    def findChampion(self, n: int, edges: List[List[int]]) -> int:
        g = [[] for _ in range(n)]
        for x, y in edges:
            g[y].append(x)
        visit = [False] * n
        ans = inf

        def dfs(x):
            if not g[x]:
                nonlocal ans
                if ans == inf or ans == x: ans = x
                else: ans = -1
                return
            visit[x] = True
            for y in g[x]:
                if not visit[y]: dfs(y)
        
        for x in range(n): dfs(x)
        return ans

#直接遍历
class Solution:
    def findChampion(self, n: int, edges: List[List[int]]) -> int:
        degree = [0] * n
        for x, y in edges:
            degree[y] += 1
        champion = -1
        for i, d in enumerate(degree):
            if d == 0:
                if champion == -1:
                    champion = i
                else:
                    return -1
        return champion

14号_705. 设计哈希集合

不使用任何内建的哈希表库设计一个哈希集合（HashSet）。

实现 MyHashSet 类：

• void add(key) 向哈希集合中插入值 key 。
• bool contains(key) 返回哈希集合中是否存在这个值 key 。
• void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。

#集合（实际就是哈希表）
class MyHashSet:

    def __init__(self):
        self.mp = set()

    def add(self, key: int) -> None:
        self.mp.add(key)

    def remove(self, key: int) -> None:
        if self.contains(key):
            self.mp.remove(key)

    def contains(self, key: int) -> bool:
        return True if key in self.mp else False

#数组
class MyHashSet:
    def __init__(self):
        self.data = [False] * 1000001

    def add(self, key: int) -> None:
        self.data[key] = True

    def remove(self, key: int) -> None:
        self.data[key] = False

    def contains(self, key: int) -> bool:
        return self.data[key]

#数组+链表
class MyHashSet:
    def __init__(self):
        self.size = 1000
        self.data = [[] for _ in range(self.size)]

    def add(self, key: int) -> None:
        if self.contains(key):
            return
        idx = self.hash(key)
        self.data[idx].append(key)

    def remove(self, key: int) -> None:
        if not self.contains(key):
            return
        idx = self.hash(key)
        self.data[idx].remove(key)

    def contains(self, key: int) -> bool:
        idx = self.hash(key)
        return any(v == key for v in self.data[idx])

    def hash(self, key) -> int:
        return key % self.size

15号_706. 设计哈希映射

不使用任何内建的哈希表库设计一个哈希映射（HashMap）。

实现 MyHashMap 类：

• MyHashMap() 用空映射初始化对象
• void put(int key, int value) 向 HashMap 插入一个键值对 (key, value) 。如果 key 已经存在于映射中，则更新其对应的值 value 。
• int get(int key) 返回特定的 key 所映射的 value ；如果映射中不包含 key 的映射，返回 -1 。
• void remove(key) 如果映射中存在 key 的映射，则移除 key 和它所对应的 value 。

class MyHashMap:

    def __init__(self):
        self.mp = {}

    def put(self, key: int, value: int) -> None:
        self.mp[key] = value

    def get(self, key: int) -> int:
        return self.mp[key] if key in self.mp else -1

    def remove(self, key: int) -> None:
        if key in self.mp: del self.mp[key]

16号_924. 尽量减少恶意软件的传播

给出了一个由 n 个节点组成的网络，用 n × n 个邻接矩阵图 graph 表示。在节点网络中，当 graph[i][j] = 1 时，表示节点 i 能够直接连接到另一个节点 j。

一些节点 initial 最初被恶意软件感染。只要两个节点直接连接，且其中至少一个节点受到恶意软件的感染，那么两个节点都将被恶意软件感染。这种恶意软件的传播将继续，直到没有更多的节点可以被这种方式感染。

假设 M(initial) 是在恶意软件停止传播之后，整个网络中感染恶意软件的最终节点数。

如果从 initial 中移除某一节点能够最小化 M(initial)， 返回该节点。如果有多个节点满足条件，就返回索引最小的节点。

请注意，如果某个节点已从受感染节点的列表 initial 中删除，它以后仍有可能因恶意软件传播而受到感染。

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        st = set(initial)
        vis = [False] * len(graph)
        def dfs(x: int) -> None:
            vis[x] = True
            nonlocal node_id, size
            size += 1
            # 按照状态机更新 node_id
            if node_id != -2 and x in st:
                node_id = x if node_id == -1 else -2
            for y, conn in enumerate(graph[x]):
                if conn and not vis[y]:
                    dfs(y)

        ans = -1
        max_size = 0
        for x in initial:
            if vis[x]:
                continue
            node_id = -1
            size = 0
            dfs(x)
            if node_id >= 0 and (size > max_size or size == max_size and node_id < ans):
                ans = node_id
                max_size = size
        return min(initial) if ans < 0 else ans

17号__928. 尽量减少恶意软件的传播 II

给定一个由 n 个节点组成的网络，用 n x n 个邻接矩阵 graph 表示。在节点网络中，只有当 graph[i][j] = 1 时，节点 i 能够直接连接到另一个节点 j。

一些节点 initial 最初被恶意软件感染。只要两个节点直接连接，且其中至少一个节点受到恶意软件的感染，那么两个节点都将被恶意软件感染。这种恶意软件的传播将继续，直到没有更多的节点可以被这种方式感染。

假设 M(initial) 是在恶意软件停止传播之后，整个网络中感染恶意软件的最终节点数。

我们可以从 initial 中删除一个节点，并完全移除该节点以及从该节点到任何其他节点的任何连接。

请返回移除后能够使 M(initial) 最小化的节点。如果有多个节点满足条件，返回索引 最小的节点 。

class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        st = set(initial)
        vis = [False] * len(graph)
        def dfs(x: int) -> None:
            vis[x] = True
            nonlocal node_id, size
            size += 1
            for y, conn in enumerate(graph[x]):
                if conn == 0:
                    continue
                if y in st:
                    # 按照 924 题的状态机更新 node_id
                    # 注意避免重复统计，例如上图中的 0 有两条不同路径可以遇到 1
                    if node_id != -2 and node_id != y:
                        node_id = y if node_id == -1 else -2
                elif not vis[y]:
                    dfs(y)

        cnt = Counter()
        for i, seen in enumerate(vis):
            if seen or i in st:
                continue
            node_id = -1
            size = 0
            dfs(i)
            if node_id >= 0:  # 只找到一个在 initial 中的节点
                # 删除节点 node_id 可以让 size 个点不被感染
                cnt[node_id] += size

        # size 取反计算最大值，相同最大值取 node_id 最小值
        return min((-size, node_id) for node_id, size in cnt.items())[1] if cnt else min(initial)

18号_2007. 从双倍数组中还原原数组

一个整数数组 original 可以转变成一个 双倍 数组 changed ，转变方式为将 original 中每个元素 值乘以 2 加入数组中，然后将所有元素 随机打乱 。

给你一个数组 changed ，如果 change 是 双倍 数组，那么请你返回 original数组，否则请返回空数组。original 的元素可以以 任意 顺序返回。

class Solution:
    def findOriginalArray(self, changed: List[int]) -> List[int]:
        changed.sort()
        ans = []
        cnt = Counter()
        for x in changed:
            if x not in cnt:  # x 不是双倍后的元素
                cnt[x * 2] += 1  # 标记一个双倍元素
                ans.append(x)
            else:  # x 是双倍后的元素
                cnt[x] -= 1  # 清除一个标记
                if cnt[x] == 0:
                    del cnt[x]
        # 只有所有双倍标记都被清除掉，才能说明 changed 是一个双倍数组
        return [] if cnt else ans

#排序+队列
class Solution:
    def findOriginalArray(self, changed: List[int]) -> List[int]:
        changed.sort()
        ans = []
        q = deque()
        for x in changed:
            if q:
                if q[0] < x:  # 无法配对
                    return []
                if q[0] == x:  # 配对成功
                    q.popleft()  # 清除一个标记
                    continue
            ans.append(x)
            q.append(x * 2)  # 添加双倍标记
        # 只有所有双倍标记都被清除掉，才能说明 changed 是一个双倍数组
        return [] if q else ans

#排序+双指针
class Solution:
    def findOriginalArray(self, changed: List[int]) -> List[int]:
        n = len(changed)
        if n % 2: return []
        changed.sort()
        i = 0
        res = []
        while i < n:
            if changed[i] == 0: i += 1
            else: break
        if i % 2: return []
        else: res += [0] * (i//2)
        j = i + 1
        double = [False] * n
        while i < n and j < n:
            while j < n and changed[j] != 2 * changed[i]: j += 1
            if j == n: break
            double[j] = True
            res.append(changed[i])
            i += 1
            j += 1
            while i < n and double[i]: i += 1
        return res if len(res) == n // 2 else []

#消消乐
class Solution:
    def findOriginalArray(self, changed: List[int]) -> List[int]:
        cnt = Counter(changed)
        # 单独处理 0
        cnt0 = cnt.pop(0, 0)
        if cnt0 % 2:
            return []
        ans = [0] * (cnt0 // 2)

        for x in cnt:
            # 如果 x/2 在 cnt 中，则跳过
            if x % 2 == 0 and x // 2 in cnt:
                continue
            # 把 x, 2x, 4x, 8x, ... 全部配对
            while x in cnt:
                # 每次循环，把 cnt_x 个 x 和 cnt_x 个 2x 配对
                cnt_x = cnt[x]
                # 无法配对，至少要有 cnt_x 个 2x
                if cnt_x > cnt[x * 2]:
                    return []
                ans.extend([x] * cnt_x)
                if cnt_x < cnt[x * 2]:
                    # 还剩下一些 2x
                    cnt[x * 2] -= cnt_x
                    x *= 2
                else:
                    x *= 4
        return ans

19号_1883. 准时抵达会议现场的最小跳过休息次数

给你一个整数 hoursBefore ，表示你要前往会议所剩下的可用小时数。要想成功抵达会议现场，你必须途经 n 条道路。道路的长度用一个长度为 n 的整数数组 dist 表示，其中 dist[i] 表示第 i 条道路的长度（单位：千米）。另给你一个整数 speed ，表示你在道路上前进的速度（单位：千米每小时）。

当你通过第 i 条路之后，就必须休息并等待，直到 下一个整数小时 才能开始继续通过下一条道路。注意：你不需要在通过最后一条道路后休息，因为那时你已经抵达会议现场。

• 例如，如果你通过一条道路用去 1.4 小时，那你必须停下来等待，到 2 小时才可以继续通过下一条道路。如果通过一条道路恰好用去 2 小时，就无需等待，可以直接继续。

然而，为了能准时到达，你可以选择 跳过 一些路的休息时间，这意味着你不必等待下一个整数小时。注意，这意味着与不跳过任何休息时间相比，你可能在不同时刻到达接下来的道路。

• 例如，假设通过第 1 条道路用去 1.4 小时，且通过第 2 条道路用去 0.6 小时。跳过第 1 条道路的休息时间意味着你将会在恰好 2 小时完成通过第 2 条道路，且你能够立即开始通过第 3 条道路。

返回准时抵达会议现场所需要的 最小跳过次数 ，如果 无法准时参会 ，返回 -1 。

class Solution:
    def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int:
        # 可忽略误差
        EPS = 1e-7       
        n = len(dist)
        f = [[float("inf")] * (n + 1) for _ in range(n + 1)]
        f[0][0] = 0.
        for i in range(1, n + 1):
            for j in range(i + 1):
                if j != i:
                    f[i][j] = min(f[i][j], ceil(f[i - 1][j] + dist[i - 1] / speed - EPS))
                if j != 0:
                    f[i][j] = min(f[i][j], f[i - 1][j - 1] + dist[i - 1] / speed)
        
        for j in range(n + 1):
            if f[n][j] < hoursBefore + EPS:
                return j
        return -1

20号_39. 组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def backtrack(
            state: list[int], target: int, choices: list[int], start: int, res: list[list[int]]):
            """回溯算法：子集和 I"""
            # 子集和等于 target 时，记录解
            if target == 0:
                res.append(list(state))
                return
            # 遍历所有选择
            # 剪枝二：从 start 开始遍历，避免生成重复子集
            for i in range(start, len(choices)):
                # 剪枝一：若子集和超过 target ，则直接结束循环
                # 这是因为数组已排序，后边元素更大，子集和一定超过 target
                if target - choices[i] < 0:
                    break
                # 尝试：做出选择，更新 target, start
                state.append(choices[i])
                # 进行下一轮选择
                backtrack(state, target - choices[i], choices, i, res)
                # 回退：撤销选择，恢复到之前的状态
                state.pop()

        state = []  # 状态（子集）
        candidates.sort()  # 对 candidates 进行排序
        start = 0  # 遍历起始点
        res = []  # 结果列表（子集列表）
        backtrack(state, target, candidates, start, res)
        return res

21号_216. 组合总和 III

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

• 只使用数字1到9
• 每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        ans = []
        path = []
        def dfs(i: int, t: int) -> None:
            d = k - len(path)  # 还要选 d 个数
            if t < 0 or t > (i * 2 - d + 1) * d // 2:  # 剪枝
                return
            if d == 0:  # 找到一个合法组合
                ans.append(path.copy())
                return
            for j in range(i, d - 1, -1):
                path.append(j)
                dfs(j - 1, t - j)
                path.pop()
        dfs(9, n)
        return ans

22号_377. 组合总和 Ⅳ

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

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

#动态规划
class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        n = len(nums)
        nums.sort()
        dp = [0] * (target+1)
        dp[0] = 1
        for i in range(1,target+1):
            for j in range(n):
                if nums[j] <= i:
                    dp[i] += dp[i-nums[j]]
        return dp[-1]

#递归
class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        @cache  # 缓存装饰器，避免重复计算 dfs 的结果
        def dfs(i: int) -> int:
            if i == 0:  # 爬完了
                return 1
            return sum(dfs(i - x) for x in nums if x <= i)  # 枚举所有可以爬的台阶数
        return dfs(target)

23_1052. 爱生气的书店老板

有一个书店老板，他的书店开了 n 分钟。每分钟都有一些顾客进入这家商店。给定一个长度为 n 的整数数组 customers ，其中 customers[i] 是在第 i 分钟开始时进入商店的顾客数量，所有这些顾客在第 i 分钟结束后离开。

在某些时候，书店老板会生气。 如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。

当书店老板生气时，那一分钟的顾客就会不满意，若老板不生气则顾客是满意的。

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

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

class Solution:
    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:
        n = len(customers)
        res = 0
        for i in range(n):
            if grumpy[i]: grumpy[i] = customers[i]
            else: res += customers[i]
        mx = total = sum(grumpy[:minutes])
        for i in range(1,n-minutes+1):
            total = total + grumpy[i+minutes-1] - grumpy[i-1]
            mx = max(mx,total)
        return res + mx

class Solution:
    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:
        n = len(customers)
        total = sum(c for c, g in zip(customers, grumpy) if g == 0)
        maxIncrease = increase = sum(c * g for c, g in zip(customers[:minutes], grumpy[:minutes]))
        for i in range(minutes, n):
            increase += customers[i] * grumpy[i] - customers[i - minutes] * grumpy[i - minutes]
            maxIncrease = max(maxIncrease, increase)
        return total + maxIncrease

24号_2385. 感染二叉树需要的总时间

给你一棵二叉树的根节点 root ，二叉树中节点的值 互不相同 。另给你一个整数 start 。在第 0 分钟，感染 将会从值为 start 的节点开始爆发。

每分钟，如果节点满足以下全部条件，就会被感染：

• 节点此前还没有感染。
• 节点与一个已感染节点相邻。

返回感染整棵树需要的分钟数

#将树改成无向图
class Solution:
    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:
        fa = {}
        start_node = None
        def dfs(node: Optional[TreeNode], from_: Optional[TreeNode]) -> None:
            if node is None:
                return
            fa[node] = from_  # 记录每个节点的父节点
            if node.val == start:  # 找到 start
                nonlocal start_node
                start_node = node
            dfs(node.left, node)
            dfs(node.right, node)
        dfs(root, None)

        def maxDepth(node: Optional[TreeNode], from_: TreeNode) -> int:
            if node is None:
                return -1  # 注意这里是 -1，因为 start 的深度为 0
            return max(maxDepth(x, node) for x in (node.left, node.right, fa[node]) if x != from_) + 1
        return maxDepth(start_node, start_node)

#分为叶部和父部两块
class Solution:
    def amountOfTime(self, root: Optional[TreeNode], start: int) -> int:
        ans = 0
        def dfs(node: Optional[TreeNode]) -> (int, bool):
            if node is None:
                return 0, False
            l_len, l_found = dfs(node.left)
            r_len, r_found = dfs(node.right)
            nonlocal ans
            if node.val == start:
                # 计算子树 start 的最大深度
                # 注意这里和方法一的区别，max 后面没有 +1，所以算出的也是最大深度
                ans = max(l_len, r_len)
                return 1, True  # 找到了 start
            if l_found or r_found:
                # 只有在左子树或右子树包含 start 时，才能更新答案
                ans = max(ans, l_len + r_len)  # 两条链拼成直径
                # 保证 start 是直径端点
                return (l_len if l_found else r_len) + 1, True
            return max(l_len, r_len) + 1, False
        dfs(root)
        return ans

25号_2739. 总行驶距离

卡车有两个油箱。给你两个整数，mainTank 表示主油箱中的燃料（以升为单位），additionalTank 表示副油箱中的燃料（以升为单位）。

该卡车每耗费 1 升燃料都可以行驶 10 km。每当主油箱使用了 5 升燃料时，如果副油箱至少有 1 升燃料，则会将 1 升燃料从副油箱转移到主油箱。

返回卡车可以行驶的最大距离。

注意：从副油箱向主油箱注入燃料不是连续行为。这一事件会在每消耗 5 升燃料时突然且立即发生。

class Solution:
    def distanceTraveled(self, mainTank: int, additionalTank: int) -> int:
        res = 0
        while mainTank >= 5:
            mainTank -= 5
            res += 50
            if additionalTank >= 1:
                mainTank += 1
                additionalTank -= 1
        res += mainTank * 10
        return res  

26号_1146. 快照数组

实现支持下列接口的「快照数组」- SnapshotArray：

• SnapshotArray(int length) - 初始化一个与指定长度相等的 类数组 的数据结构。初始时，每个元素都等于 0。
• void set(index, val) - 会将指定索引 index 处的元素设置为 val。
• int snap() - 获取该数组的快照，并返回快照的编号 snap_id（快照号是调用 snap() 的总次数减去 1）。
• int get(index, snap_id) - 根据指定的 snap_id 选择快照，并返回该快照指定索引 index 的值。

class SnapshotArray:
    def __init__(self, _: int):
        self.cur_snap_id = 0
        self.history = defaultdict(list)  # 每个 index 的历史修改记录

    def set(self, index: int, val: int) -> None:
        self.history[index].append((self.cur_snap_id, val))

    def snap(self) -> int:
        self.cur_snap_id += 1
        return self.cur_snap_id - 1

    def get(self, index: int, snap_id: int) -> int:
        # 找快照编号 <= snap_id 的最后一次修改记录
        # 等价于找快照编号 >= snap_id+1 的第一个修改记录，它的上一个就是答案
        j = bisect_left(self.history[index], (snap_id + 1,)) - 1
        return self.history[index][j][1] if j >= 0 else 0

27号_2639. 查询网格图中每一列的宽度

给你一个下标从 0 开始的 m x n 整数矩阵 grid 。矩阵中某一列的宽度是这一列数字的最大 字符串长度 。

• 比方说，如果 grid = [[-10], [3], [12]] ，那么唯一一列的宽度是 3 ，因为 -10 的字符串长度为 3 。

请你返回一个大小为 n 的整数数组 ans ，其中 ans[i] 是第 i 列的宽度。

一个有 len 个数位的整数 x ，如果是非负数，那么 字符串****长度 为 len ，否则为 len + 1 。

class Solution:
    def findColumnWidth(self, grid: List[List[int]]) -> List[int]:
        m = len(grid)
        n = len(grid[0])
        res = []
        for j in range(n):
            max_len = 0
            for i in range(m): max_len = max(max_len,len(str(grid[i][j])))
            res.append (max_len)
        return res

28号_1017. 负二进制转换

给你一个整数 n ，以二进制字符串的形式返回该整数的 **负二进制（base -2）**表示。

**注意，**除非字符串就是 "0"，否则返回的字符串中不能含有前导零。

class Solution:
    def baseNeg2(self, n: int) -> str:
        if n == 0:
            return "0"

        bits = [0] * 32
        for i in range(32):
            if n == 0:
                break
            if n & 1:
                bits[i] += 1
                if i & 1:
                    bits[i + 1] += 1
            n >>= 1

        carry = 0
        for i in range(32):
            val = carry + bits[i]
            bits[i] = val & 1
            carry = (val - bits[i]) // -2

        pos = 31
        res = ""
        while pos >= 0 and bits[pos] == 0:
            pos -= 1
        while pos >= 0:
            res += str(bits[pos])
            pos -= 1
        return res

29号_1329. 将矩阵按对角线排序

矩阵对角线 是一条从矩阵最上面行或者最左侧列中的某个元素开始的对角线，沿右下方向一直到矩阵末尾的元素。例如，矩阵 mat 有 6 行 3 列，从 mat[2][0] 开始的 矩阵对角线 将会经过 mat[2][0]、mat[3][1] 和 mat[4][2] 。

给你一个 m * n 的整数矩阵 mat ，请你将同一条 矩阵对角线 上的元素按升序排序后，返回排好序的矩阵。

class Solution:
    def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]:
        m, n = len(mat), len(mat[0])
        for k in range(1 - n, m):  # k = i - j
            left_i, right_i = max(k, 0), min(k + n, m)
            a = sorted(mat[i][i - k] for i in range(left_i, right_i))
            for i in range(left_i, right_i):
                mat[i][i - k] = a[i - left_i]
        return mat

30号_2798. 满足目标工作时长的员工数目

公司里共有 n 名员工，按从 0 到 n - 1 编号。每个员工 i 已经在公司工作了 hours[i] 小时。

公司要求每位员工工作 至少 target 小时。

给你一个下标从 0 开始、长度为 n 的非负整数数组 hours 和一个非负整数 target 。

请你用整数表示并返回工作至少 target 小时的员工数。

class Solution:
    def numberOfEmployeesWhoMetTarget(self, hours: List[int], target: int) -> int:
        res = 0
        for hour in hours:
            if hour >= target: res += 1
        return res

5月

1号_2462. 雇佣 K 位工人的总代价

给你一个下标从 0 开始的整数数组 costs ，其中 costs[i] 是雇佣第 i 位工人的代价。

同时给你两个整数 k 和 candidates 。我们想根据以下规则恰好雇佣 k 位工人：

• 总共进行 k 轮雇佣，且每一轮恰好雇佣一位工人。
• 在每一轮雇佣中，从最前面candidates和最后面candidates人中选出代价最小的一位工人，如果有多位代价相同且最小的工人，选择下标更小的一位工人。
  • 比方说，costs = [3,2,7,7,1,2] 且 candidates = 2 ，第一轮雇佣中，我们选择第 4 位工人，因为他的代价最小 [*3,2*,7,7,***1**,2*] 。
  • 第二轮雇佣，我们选择第 1 位工人，因为他们的代价与第 4 位工人一样都是最小代价，而且下标更小，[*3,**2***,7,*7,2*] 。注意每一轮雇佣后，剩余工人的下标可能会发生变化。
• 如果剩余员工数目不足 candidates 人，那么下一轮雇佣他们中代价最小的一人，如果有多位代价相同且最小的工人，选择下标更小的一位工人。
• 一位工人只能被选择一次。

返回雇佣恰好 k 位工人的总代价。

import heapq
class Solution:
    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:
        n = len(costs)
        if n > 2 * candidates: l, r = candidates, n - candidates 
        elif n < candidates: l, r = n, n
        else: l, r = candidates, candidates
        left = costs[:l]
        right = costs[r:]
        heapq.heapify(left)
        heapq.heapify(right)
        cost = 0
        while k > 0 and l < r:
            if left[0] <= right[0]:
                cost += heapq.heappop(left)
                heapq.heappush(left,costs[l])
                l += 1
            else:
                cost += heapq.heappop(right)
                heapq.heappush(right,costs[r-1])
                r -= 1
            k -= 1
        while k > 0:
            if not right: cost += heapq.heappop(left)
            elif not left or left[0] > right[0]: cost += heapq.heappop(right)
            else: cost += heapq.heappop(left)
            k -= 1
        return cost

2号_857. 雇佣 K 名工人的最低成本

有 n 名工人。 给定两个数组 quality 和 wage ，其中，quality[i] 表示第 i 名工人的工作质量，其最低期望工资为 wage[i] 。

现在我们想雇佣 k 名工人组成一个*工资组。*在雇佣 一组 k 名工人时，我们必须按照下述规则向他们支付工资：

1. 对工资组中的每名工人，应当按其工作质量与同组其他工人的工作质量的比例来支付工资。
2. 工资组中的每名工人至少应当得到他们的最低期望工资。

给定整数 k ，返回 组成满足上述条件的付费群体所需的最小金额 。在实际答案的 10-5 以内的答案将被接受。。

class Solution:
    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:
        pairs = sorted(zip(quality, wage), key=lambda p: p[1] / p[0])  # 按照 r 值排序
        h = [-q for q, _ in pairs[:k]]  # 加负号变成最大堆
        heapify(h)
        sum_q = -sum(h)
        ans = sum_q * pairs[k - 1][1] / pairs[k - 1][0]  # 选 r 值最小的 k 名工人
        for q, w in pairs[k:]:  # 后面的工人 r 值更大
            if q < -h[0]:  # 但是 sum_q 可以变小，从而可能得到更优的答案
                sum_q += heapreplace(h, -q) + q  # 更新堆顶和 sum_q
                ans = min(ans, sum_q * w / q)
        return ans

3号_1491. 去掉最低工资和最高工资后的工资平均值

给你一个整数数组 salary ，数组里每个数都是 唯一 的，其中 salary[i] 是第 i 个员工的工资。

请你返回去掉最低工资和最高工资以后，剩下员工工资的平均值。

class Solution:
    def average(self, salary: List[int]) -> float:
        s = sum(salary)
        M = max(salary)
        m = min(salary)
        n = len(salary)
        return (s - M - m) / (n - 2)

4号_1235. 规划兼职工作

你打算利用空闲时间来做兼职工作赚些零花钱。

这里有 n 份兼职工作，每份工作预计从 startTime[i] 开始到 endTime[i] 结束，报酬为 profit[i]。

给你一份兼职工作表，包含开始时间 startTime，结束时间 endTime 和预计报酬 profit 三个数组，请你计算并返回可以获得的最大报酬。

注意，时间上出现重叠的 2 份工作不能同时进行。

如果你选择的工作在时间 X 结束，那么你可以立刻进行在时间 X 开始的下一份工作。

class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        jobs = sorted(zip(endTime, startTime, profit))  # 按照结束时间排序
        f = [0] * (len(jobs) + 1)
        for i, (_, st, p) in enumerate(jobs):
            j = bisect_left(jobs, (st + 1,), hi=i)  # hi=i 表示二分上界为 i（默认为 n）
            # 状态转移中，为什么是 j 不是 j+1：上面算的是 > st，-1 后得到 <= st，但由于还要 +1，抵消了
            f[i + 1] = max(f[i], f[j] + p)
        return f[-1]

5号_1652. 拆炸弹

你有一个炸弹需要拆除，时间紧迫！你的情报员会给你一个长度为 n 的 循环 数组 code 以及一个密钥 k 。

为了获得正确的密码，你需要替换掉每一个数字。所有数字会 同时 被替换。

• 如果 k > 0 ，将第 i 个数字用 接下来 k 个数字之和替换。
• 如果 k < 0 ，将第 i 个数字用 之前 k 个数字之和替换。
• 如果 k == 0 ，将第 i 个数字用 0 替换。

由于 code 是循环的， code[n-1] 下一个元素是 code[0] ，且 code[0] 前一个元素是 code[n-1] 。

给你 循环 数组 code 和整数密钥 k ，请你返回解密后的结果来拆除炸弹！

class Solution:
    def decrypt(self, code: List[int], k: int) -> List[int]:
        n = len(code)
        res = []
        if k > 0:
            code = code + code[:k]
            for i in range(n): res.append(sum(code[i+1:i+k+1]))
        elif k < 0:
            code = code[n+k:] + code
            for i in range(-k,n-k): res.append(sum(code[i+k:i]))
        else:
            res = [0] * n
        return res

6号_741. 摘樱桃

给你一个 n x n 的网格 grid ，代表一块樱桃地，每个格子由以下三种数字的一种来表示：

• 0 表示这个格子是空的，所以你可以穿过它。
• 1 表示这个格子里装着一个樱桃，你可以摘到樱桃然后穿过它。
• -1 表示这个格子里有荆棘，挡着你的路。

请你统计并返回：在遵守下列规则的情况下，能摘到的最多樱桃数：

• 从位置 (0, 0) 出发，最后到达 (n - 1, n - 1) ，只能向下或向右走，并且只能穿越有效的格子（即只可以穿过值为 0 或者 1 的格子）；
• 当到达 (n - 1, n - 1) 后，你要继续走，直到返回到 (0, 0) ，只能向上或向左走，并且只能穿越有效的格子；
• 当你经过一个格子且这个格子包含一个樱桃时，你将摘到樱桃并且这个格子会变成空的（值变为 0 ）；
• 如果在 (0, 0) 和 (n - 1, n - 1) 之间不存在一条可经过的路径，则无法摘到任何一个樱桃。

class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        @cache  # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）
        def dfs(t: int, j: int, k: int) -> int:
            # 不能出界，不能访问 -1 格子
            if j < 0 or k < 0 or t < j or t < k or grid[t - j][j] < 0 or grid[t - k][k] < 0:
                return -inf
            if t == 0:  # 此时 j = k = 0
                return grid[0][0]
            return max(dfs(t - 1, j, k), dfs(t - 1, j, k - 1), dfs(t - 1, j - 1, k), dfs(t - 1, j - 1, k - 1)) + \
                grid[t - j][j] + (grid[t - k][k] if k != j else 0)
        n = len(grid)
        return max(dfs(n * 2 - 2, n - 1, n - 1), 0)

7号_1463. 摘樱桃 II

给你一个 rows x cols 的矩阵 grid 来表示一块樱桃地。 grid 中每个格子的数字表示你能获得的樱桃数目。

你有两个机器人帮你收集樱桃，机器人 1 从左上角格子 (0,0) 出发，机器人 2 从右上角格子 (0, cols-1) 出发。

请你按照如下规则，返回两个机器人能收集的最多樱桃数目：

• 从格子 (i,j) 出发，机器人可以移动到格子 (i+1, j-1)，(i+1, j) 或者 (i+1, j+1) 。
• 当一个机器人经过某个格子时，它会把该格子内所有的樱桃都摘走，然后这个位置会变成空格子，即没有樱桃的格子。
• 当两个机器人同时到达同一个格子时，它们中只有一个可以摘到樱桃。
• 两个机器人在任意时刻都不能移动到 grid 外面。
• 两个机器人最后都要到达 grid 最底下一行。

class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        @cache  # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）
        def dfs(i: int, j: int, k: int) -> int:
            if i == m or j < 0 or j >= n or k < 0 or k >= n:
                return 0
            return max(dfs(i + 1, j2, k2) for j2 in (j - 1, j, j + 1) for k2 in (k - 1, k, k + 1)) + \
                   grid[i][j] + (grid[i][k] if k != j else 0)
        return dfs(0, 0, n - 1)

2025年

2月

20号 2595. 奇偶位数

给你一个 正 整数 n 。

用 even 表示在 n 的二进制形式（下标从 0 开始）中值为 1 的偶数下标的个数。

用 odd 表示在 n 的二进制形式（下标从 0 开始）中值为 1 的奇数下标的个数。

请注意，在数字的二进制表示中，位下标的顺序 从右到左。

返回整数数组 answer ，其中 answer = [even, odd] 。

class Solution:
    def evenOddBit(self, n: int) -> List[int]:
        even, odd = 0, 0
        while n:
            if n % 2: even += 1
            n = n >> 1
            if n % 2: odd += 1
            n = n >> 1
        return [even,odd]