标签： todo

目标

给你一个大小为 n x n 的二维矩阵 grid ，一开始所有格子都是白色的。一次操作中，你可以选择任意下标为 (i, j) 的格子，并将第 j 列中从最上面到第 i 行所有格子改成黑色。

如果格子 (i, j) 为白色，且左边或者右边的格子至少一个格子为黑色，那么我们将 grid[i][j] 加到最后网格图的总分中去。

请你返回执行任意次操作以后，最终网格图的 最大 总分数。

示例 1：

输入：grid = [[0,0,0,0,0],[0,0,3,0,0],[0,1,0,0,0],[5,0,0,3,0],[0,0,0,0,2]]
输出：11
解释：
第一次操作中，我们将第 1 列中，最上面的格子到第 3 行的格子染成黑色。第二次操作中，我们将第 4 列中，最上面的格子到最后一行的格子染成黑色。最后网格图总分为 grid[3][0] + grid[1][2] + grid[3][3] 等于 11 。

示例 2：

输入：grid = [[10,9,0,0,15],[7,1,0,8,0],[5,20,0,11,0],[0,0,0,1,2],[8,12,1,10,3]]
输出：94
解释：
我们对第 1 ，2 ，3 列分别从上往下染黑色到第 1 ，4， 0 行。最后网格图总分为 grid[0][0] + grid[1][0] + grid[2][1] + grid[4][1] + grid[1][3] + grid[2][3] + grid[3][3] + grid[4][3] + grid[0][4] 等于 94 。

说明：

• 1 <= n == grid.length <= 100
• n == grid[i].length
• 0 <= grid[i][j] <= 10^9

思路

代码

性能

目标

X 轴上有一些机器人和工厂。给你一个整数数组 robot ，其中 robot[i] 是第 i 个机器人的位置。再给你一个二维整数数组 factory ，其中 factory[j] = [positionj, limitj] ，表示第 j 个工厂的位置在 positionj ，且第 j 个工厂最多可以修理 limitj 个机器人。

每个机器人所在的位置 互不相同 。每个工厂所在的位置也 互不相同 。注意一个机器人可能一开始跟一个工厂在 相同的位置 。

所有机器人一开始都是坏的，他们会沿着设定的方向一直移动。设定的方向要么是 X 轴的正方向，要么是 X 轴的负方向。当一个机器人经过一个没达到上限的工厂时，这个工厂会维修这个机器人，且机器人停止移动。

任何时刻，你都可以设置 部分 机器人的移动方向。你的目标是最小化所有机器人总的移动距离。

请你返回所有机器人移动的最小总距离。测试数据保证所有机器人都可以被维修。

注意：

• 所有机器人移动速度相同。
• 如果两个机器人移动方向相同，它们永远不会碰撞。
• 如果两个机器人迎面相遇，它们也不会碰撞，它们彼此之间会擦肩而过。
• 如果一个机器人经过了一个已经达到上限的工厂，机器人会当作工厂不存在，继续移动。
• 机器人从位置 x 到位置 y 的移动距离为 |y - x| 。

示例 1：

输入：robot = [0,4,6], factory = [[2,2],[6,2]]
输出：4
解释：如上图所示：
- 第一个机器人从位置 0 沿着正方向移动，在第一个工厂处维修。
- 第二个机器人从位置 4 沿着负方向移动，在第一个工厂处维修。
- 第三个机器人在位置 6 被第二个工厂维修，它不需要移动。
第一个工厂的维修上限是 2 ，它维修了 2 个机器人。
第二个工厂的维修上限是 2 ，它维修了 1 个机器人。
总移动距离是 |2 - 0| + |2 - 4| + |6 - 6| = 4 。没有办法得到比 4 更少的总移动距离。

示例 2：

输入：robot = [1,-1], factory = [[-2,1],[2,1]]
输出：2
解释：如上图所示：
- 第一个机器人从位置 1 沿着正方向移动，在第二个工厂处维修。
- 第二个机器人在位置 -1 沿着负方向移动，在第一个工厂处维修。
第一个工厂的维修上限是 1 ，它维修了 1 个机器人。
第二个工厂的维修上限是 1 ，它维修了 1 个机器人。
总移动距离是 |2 - 1| + |(-2) - (-1)| = 2 。没有办法得到比 2 更少的总移动距离。

说明：

• 1 <= robot.length, factory.length <= 100
• factory[j].length == 2
• -10^9 <= robot[i], positionj <= 10^9
• 0 <= limitj <= robot.length
• 测试数据保证所有机器人都可以被维修。

思路

// todo

代码

性能

目标

给你一个长度为 n 的整数数组 nums 和一个大小为 q 的二维整数数组 queries，其中 queries[i] = [li, ri, ki, vi]。

对于每个查询，需要按以下步骤依次执行操作：

• 设定 idx = li。
• 当 idx <= ri 时：
  • 更新：nums[idx] = (nums[idx] * vi) % (10^9 + 7)。
  • 将 idx += ki。

在处理完所有查询后，返回数组 nums 中所有元素的 按位异或 结果。

示例 1：

输入： nums = [1,1,1], queries = [[0,2,1,4]]
输出： 4
解释：
唯一的查询 [0, 2, 1, 4] 将下标 0 到下标 2 的每个元素乘以 4。
数组从 [1, 1, 1] 变为 [4, 4, 4]。
所有元素的异或为 4 ^ 4 ^ 4 = 4。

示例 2：

输入： nums = [2,3,1,5,4], queries = [[1,4,2,3],[0,2,1,2]]
输出： 31
解释：
第一个查询 [1, 4, 2, 3] 将下标 1 和 3 的元素乘以 3，数组变为 [2, 9, 1, 15, 4]。
第二个查询 [0, 2, 1, 2] 将下标 0、1 和 2 的元素乘以 2，数组变为 [4, 18, 2, 15, 4]。
所有元素的异或为 4 ^ 18 ^ 2 ^ 15 ^ 4 = 31。

说明：

• 1 <= n == nums.length <= 10^5
• 1 <= nums[i] <= 10^9
• 1 <= q == queries.length <= 10^5
• queries[i] = [li, ri, ki, vi]
• 0 <= li <= ri < n
• 1 <= ki <= n
• 1 <= vi <= 10^5

思路

有一个长度为 n 的数组，对该数组执行 n 次查询，每次查询从 li 开始，对相距 ki 个位置上的元素执行 nums[idx] = (nums[idx] * vi) % (10^9 + 7) 直到下标 idx > ri。求处理完所有查询后 nums 中所有元素的 按位异或 结果。

可以参考差分数组的思想，采用商分数组。为每一个 ki 创建一个商分数组，需要更新的下标为 l、l + ki、l + 2 * ki、……、l + x * ki。如何确定最后一个下标？使用 r - l 将区间平移至 [0, r - l]，距离右端点最近的距离为 (r - l) % k，因此原区间 [l, r] 的最后一个下标是 r - (r - l) % k。对于商分数组，需要在 l 处乘以 vi，在 r - (r - l) % k + k 处除以 vi。由于涉及到取模，这里需要求 vi 的逆元，根据 费马小定理 等价于计算 vi^(p - 2) % p，可以使用快速幂。

暴力解法的时间复杂度为 O(q * n / k)，其中 q 为查询数组长度，n 为 nums 长度，k 为所有查询中 ki 的均值，商分数组的时间复杂度为 O(q * logM + k * n)，logM 为快速幂求逆元的时间复杂度，M = 10^9 + 7，k * n 的复杂度用于遍历每一个 ki 的商分数组，内部是根据起点分组的 0 ~ ki - 1，步长为 ki。

可以发现暴力解法的复杂度 k 越大越好，而商分数组的解法 k 越小越好。可以设置一个阈值 S，小于 S 使用商分数组，大于等于 S 使用暴力解法，时间复杂度为 O(q * n / S + S * n)。根据基本不等式 a + b >= 2sqrt(ab)，当 a == b 时取等号，因此 q/S + S >= 2 * sqrt(q)，当 S = sqrt(q) 时取得最小值。

代码

性能

目标

给你两个字符串，str1 和 str2，其长度分别为 n 和 m 。

如果一个长度为 n + m - 1 的字符串 word 的每个下标 0 <= i <= n - 1 都满足以下条件，则称其由 str1 和 str2 生成：

• 如果 str1[i] == 'T'，则长度为 m 的 子字符串（从下标 i 开始）与 str2 相等，即 word[i..(i + m - 1)] == str2。
• 如果 str1[i] == 'F'，则长度为 m 的 子字符串（从下标 i 开始）与 str2 不相等，即 word[i..(i + m - 1)] != str2。

返回可以由 str1 和 str2 生成 的 字典序最小 的字符串。如果不存在满足条件的字符串，返回空字符串 ""。

如果字符串 a 在第一个不同字符的位置上比字符串 b 的对应字符在字母表中更靠前，则称字符串 a 的 字典序 小于 字符串 b。

如果前 min(a.length, b.length) 个字符都相同，则较短的字符串字典序更小。

子字符串 是字符串中的一个连续、非空 的字符序列。

示例 1：

输入: str1 = "TFTF", str2 = "ab"
输出: "ababa"
解释:
下表展示了字符串 "ababa" 的生成过程：
下标  T/F   长度为 m 的子字符串
0    'T'        "ab"
1    'F'        "ba"
2    'T'        "ab"
3    'F'        "ba"
字符串 "ababa" 和 "ababb" 都可以由 str1 和 str2 生成。
返回 "ababa"，因为它的字典序更小。

示例 2：

输入: str1 = "TFTF", str2 = "abc"
输出: ""
解释:
无法生成满足条件的字符串。

示例 3：

输入: str1 = "F", str2 = "d"
输出: "a"

说明:

• 1 <= n == str1.length <= 10^4
• 1 <= m == str2.length <= 500
• str1 仅由 'T' 或 'F' 组成。
• str2 仅由小写英文字母组成。

思路

有两个字符串 str1 和 str2，长度分别为 n 和 m。对于长度为 n + m - 1 的字符串 word，如果对于每一个位置 i 都满足以下条件，则称其由 str1 和 str2 生成：

• 如果 str1[i] == T，那么从 i 开始长度为 m 的子串 word[i ~ i + m - 1] 与 str2 相同。
• 如果 str1[i] == F，那么从 i 开始长度为 m 的子串 word[i ~ i + m - 1] 与 str2 不同。

返回由 str1 和 str2 生成的字典序最小的字符串，如果无法生成返回空字符。

// todo

代码

性能

目标

对任一由 n 个小写英文字母组成的字符串 word ，我们可以定义一个 n x n 的矩阵，并满足：

• lcp[i][j] 等于子字符串 word[i,...,n-1] 和 word[j,...,n-1] 之间的最长公共前缀的长度。

给你一个 n x n 的矩阵 lcp 。返回与 lcp 对应的、按字典序最小的字符串 word 。如果不存在这样的字符串，则返回空字符串。

对于长度相同的两个字符串 a 和 b ，如果在 a 和 b 不同的第一个位置，字符串 a 的字母在字母表中出现的顺序先于 b 中的对应字母，则认为字符串 a 按字典序比字符串 b 小。例如，"aabd" 在字典上小于 "aaca" ，因为二者不同的第一位置是第三个字母，而 'b' 先于 'c' 出现。

示例 1：

输入：lcp = [[4,0,2,0],[0,3,0,1],[2,0,2,0],[0,1,0,1]]
输出："abab"
解释：lcp 对应由两个交替字母组成的任意 4 字母字符串，字典序最小的是 "abab" 。

示例 2：

输入：lcp = [[4,3,2,1],[3,3,2,1],[2,2,2,1],[1,1,1,1]]
输出："aaaa"
解释：lcp 对应只有一个不同字母的任意 4 字母字符串，字典序最小的是 "aaaa" 。 

示例 3：

输入：lcp = [[4,3,2,1],[3,3,2,1],[2,2,2,1],[1,1,1,3]]
输出：""
解释：lcp[3][3] 无法等于 3 ，因为 word[3,...,3] 仅由单个字母组成；因此，不存在答案。

说明：

• 1 <= n == lcp.length == lcp[i].length <= 1000
• 0 <= lcp[i][j] <= n

思路

代码

性能

目标

请你实现三个 API append，addAll 和 multAll 来实现奇妙序列。

请实现 Fancy 类 ：

• Fancy() 初始化一个空序列对象。
• void append(val) 将整数 val 添加在序列末尾。
• void addAll(inc) 将所有序列中的现有数值都增加 inc 。
• void multAll(m) 将序列中的所有现有数值都乘以整数 m 。
• int getIndex(idx) 得到下标为 idx 处的数值（下标从 0 开始），并将结果对 109 + 7 取余。如果下标大于等于序列的长度，请返回 -1 。

示例：

输入：
["Fancy", "append", "addAll", "append", "multAll", "getIndex", "addAll", "append", "multAll", "getIndex", "getIndex", "getIndex"]
[[], [2], [3], [7], [2], [0], [3], [10], [2], [0], [1], [2]]
输出：
[null, null, null, null, null, 10, null, null, null, 26, 34, 20]

解释：
Fancy fancy = new Fancy();
fancy.append(2);   // 奇妙序列：[2]
fancy.addAll(3);   // 奇妙序列：[2+3] -> [5]
fancy.append(7);   // 奇妙序列：[5, 7]
fancy.multAll(2);  // 奇妙序列：[5*2, 7*2] -> [10, 14]
fancy.getIndex(0); // 返回 10
fancy.addAll(3);   // 奇妙序列：[10+3, 14+3] -> [13, 17]
fancy.append(10);  // 奇妙序列：[13, 17, 10]
fancy.multAll(2);  // 奇妙序列：[13*2, 17*2, 10*2] -> [26, 34, 20]
fancy.getIndex(0); // 返回 26
fancy.getIndex(1); // 返回 34
fancy.getIndex(2); // 返回 20

说明：

• 1 <= val, inc, m <= 100
• 0 <= idx <= 10^5
• 总共最多会有 10^5 次对 append，addAll，multAll 和 getIndex 的调用。

思路

代码

性能

目标

给你一个整数 n，表示编号从 0 到 n - 1 的 n 个节点，以及一个 edges 列表，其中 edges[i] = [ui, vi, si, musti]：

• ui 和 vi 表示节点 ui 和 vi 之间的一条无向边。
• si 是该边的强度。
• musti 是一个整数（0 或 1）。如果 musti == 1，则该边 必须 包含在生成树中，且 不能升级 。

你还有一个整数 k，表示你可以执行的最多 升级 次数。每次升级会使边的强度 翻倍 ，且每条可升级边（即 musti == 0）最多只能升级一次。

一个生成树的 稳定性 定义为其中所有边的 最小 强度。

返回任何有效生成树可能达到的 最大 稳定性。如果无法连接所有节点，返回 -1。

注意： 图的一个 生成树（spanning tree）是该图中边的一个子集，它满足以下条件：

• 将所有节点连接在一起（即图是 连通的 ）。
• 不 形成任何环。
• 包含 恰好 n - 1 条边，其中 n 是图中节点的数量。

示例 1：

输入： n = 3, edges = [[0,1,2,1],[1,2,3,0]], k = 1
输出： 2
解释：
边 [0,1] 强度为 2，必须包含在生成树中。
边 [1,2] 是可选的，可以使用一次升级将其强度从 3 提升到 6。
最终的生成树包含这两条边，强度分别为 2 和 6。
生成树中的最小强度是 2，即最大可能稳定性。

示例 2：

输入： n = 3, edges = [[0,1,4,0],[1,2,3,0],[0,2,1,0]], k = 2
输出： 6
解释：
所有边都是可选的，且最多可以进行 k = 2 次升级。
将边 [0,1] 从 4 升级到 8，将边 [1,2] 从 3 升级到 6。
生成树包含这两条边，强度分别为 8 和 6。
生成树中的最小强度是 6，即最大可能稳定性。

示例 3：

输入： n = 3, edges = [[0,1,1,1],[1,2,1,1],[2,0,1,1]], k = 0
输出： -1
解释：
所有边都是必选的，构成了一个环，这违反了生成树无环的性质。因此返回 -1。

说明：

• 2 <= n <= 10^5
• 1 <= edges.length <= 10^5
• edges[i] = [ui, vi, si, musti]
• 0 <= ui, vi < n
• ui != vi
• 1 <= si <= 10^5
• musti 是 0 或 1。
• 0 <= k <= n
• 没有重复的边。

思路

// todo

代码

性能

目标

给你 3 个正整数 zero ，one 和 limit 。

一个 二进制数组 arr 如果满足以下条件，那么我们称它是 稳定的 ：

• 0 在 arr 中出现次数 恰好 为 zero 。
• 1 在 arr 中出现次数 恰好 为 one 。
• arr 中每个长度超过 limit 的 子数组 都 同时 包含 0 和 1 。

请你返回 稳定 二进制数组的 总 数目。

由于答案可能很大，将它对 10^9 + 7 取余 后返回。

示例 1：

输入：zero = 1, one = 1, limit = 2
输出：2
解释：
两个稳定的二进制数组为 [1,0] 和 [0,1] ，两个数组都有一个 0 和一个 1 ，且没有子数组长度大于 2 。

示例 2：

输入：zero = 1, one = 2, limit = 1
输出：1
解释：
唯一稳定的二进制数组是 [1,0,1] 。
二进制数组 [1,1,0] 和 [0,1,1] 都有长度为 2 且元素全都相同的子数组，所以它们不稳定。

示例 3：

输入：zero = 3, one = 3, limit = 2
输出：14
解释：
所有稳定的二进制数组包括 [0,0,1,0,1,1] ，[0,0,1,1,0,1] ，[0,1,0,0,1,1] ，[0,1,0,1,0,1] ，[0,1,0,1,1,0] ，[0,1,1,0,0,1] ，[0,1,1,0,1,0] ，[1,0,0,1,0,1] ，[1,0,0,1,1,0] ，[1,0,1,0,0,1] ，[1,0,1,0,1,0] ，[1,0,1,1,0,0] ，[1,1,0,0,1,0] 和 [1,1,0,1,0,0] 。

说明：

• 1 <= zero, one, limit <= 1000

思路

代码

性能