3363.最多可收集的水果数目

目标

有一个游戏,游戏由 n x n 个房间网格状排布组成。

给你一个大小为 n x n 的二维整数数组 fruits ,其中 fruits[i][j] 表示房间 (i, j) 中的水果数目。有三个小朋友 一开始 分别从角落房间 (0, 0) ,(0, n - 1) 和 (n - 1, 0) 出发。

每一位小朋友都会 恰好 移动 n - 1 次,并到达房间 (n - 1, n - 1) :

  • 从 (0, 0) 出发的小朋友每次移动从房间 (i, j) 出发,可以到达 (i + 1, j + 1) ,(i + 1, j) 和 (i, j + 1) 房间之一(如果存在)。
  • 从 (0, n - 1) 出发的小朋友每次移动从房间 (i, j) 出发,可以到达房间 (i + 1, j - 1) ,(i + 1, j) 和 (i + 1, j + 1) 房间之一(如果存在)。
  • 从 (n - 1, 0) 出发的小朋友每次移动从房间 (i, j) 出发,可以到达房间 (i - 1, j + 1) ,(i, j + 1) 和 (i + 1, j + 1) 房间之一(如果存在)。

当一个小朋友到达一个房间时,会把这个房间里所有的水果都收集起来。如果有两个或者更多小朋友进入同一个房间,只有一个小朋友能收集这个房间的水果。当小朋友离开一个房间时,这个房间里不会再有水果。

请你返回三个小朋友总共 最多 可以收集多少个水果。

示例 1:

输入:fruits = [[1,2,3,4],[5,6,8,7],[9,10,11,12],[13,14,15,16]]
输出:100
解释:
这个例子中:
第 1 个小朋友(绿色)的移动路径为 (0,0) -> (1,1) -> (2,2) -> (3, 3) 。
第 2 个小朋友(红色)的移动路径为 (0,3) -> (1,2) -> (2,3) -> (3, 3) 。
第 3 个小朋友(蓝色)的移动路径为 (3,0) -> (3,1) -> (3,2) -> (3, 3) 。
他们总共能收集 1 + 6 + 11 + 1 + 4 + 8 + 12 + 13 + 14 + 15 = 100 个水果。

示例 2:

输入:fruits = [[1,1],[1,1]]
输出:4
解释:
这个例子中:
第 1 个小朋友移动路径为 (0,0) -> (1,1) 。
第 2 个小朋友移动路径为 (0,1) -> (1,1) 。
第 3 个小朋友移动路径为 (1,0) -> (1,1) 。
他们总共能收集 1 + 1 + 1 + 1 = 4 个水果。

说明:

  • 2 <= n == fruits.length == fruits[i].length <= 1000
  • 0 <= fruits[i][j] <= 1000

思路

有一个 n x n 排列的房间,房间中放有水果,fruits[i][j] 表示坐标为 (i, j) 的房间中的水果数量,有三个小朋友 A B C 同时从 (0, 0) (0, n - 1) (n - 1, 0) 出发,A 可以向 走,B 可以向 走,C 可以向 走,每一个小朋友到达一个房间会带走所有水果,求三个小朋友从起点出发,恰好走 n - 1 步 到达 (n - 1, n - 1) 总共可以收集的水果数量。

// todo

代码

性能

2106.摘水果

目标

在一个无限的 x 坐标轴上,有许多水果分布在其中某些位置。给你一个二维整数数组 fruits ,其中 fruits[i] = [positioni, amounti] 表示共有 amounti 个水果放置在 positioni 上。fruits 已经按 positioni 升序排列 ,每个 positioni 互不相同 。

另给你两个整数 startPos 和 k 。最初,你位于 startPos 。从任何位置,你可以选择 向左或者向右 走。在 x 轴上每移动 一个单位 ,就记作 一步 。你总共可以走 最多 k 步。你每达到一个位置,都会摘掉全部的水果,水果也将从该位置消失(不会再生)。

返回你可以摘到水果的 最大总数 。

示例 1:

输入:fruits = [[2,8],[6,3],[8,6]], startPos = 5, k = 4
输出:9
解释:
最佳路线为:
- 向右移动到位置 6 ,摘到 3 个水果
- 向右移动到位置 8 ,摘到 6 个水果
移动 3 步,共摘到 3 + 6 = 9 个水果

示例 2:

输入:fruits = [[0,9],[4,1],[5,7],[6,2],[7,4],[10,9]], startPos = 5, k = 4
输出:14
解释:
可以移动最多 k = 4 步,所以无法到达位置 0 和位置 10 。
最佳路线为:
- 在初始位置 5 ,摘到 7 个水果
- 向左移动到位置 4 ,摘到 1 个水果
- 向右移动到位置 6 ,摘到 2 个水果
- 向右移动到位置 7 ,摘到 4 个水果
移动 1 + 3 = 4 步,共摘到 7 + 1 + 2 + 4 = 14 个水果

示例 3:

输入:fruits = [[0,3],[6,4],[8,5]], startPos = 3, k = 2
输出:0
解释:
最多可以移动 k = 2 步,无法到达任一有水果的地方

说明:

  • 1 <= fruits.length <= 10^5
  • fruits[i].length == 2
  • 0 <= startPos, positioni <= 2 * 10^5
  • 对于任意 i > 0 ,positioni-1 < positioni 均成立(下标从 0 开始计数)
  • 1 <= amounti <= 10^4
  • 0 <= k <= 2 * 10^5

思路

代码

性能

2561.重排水果

目标

你有两个果篮,每个果篮中有 n 个水果。给你两个下标从 0 开始的整数数组 basket1 和 basket2 ,用以表示两个果篮中每个水果的交换成本。你想要让两个果篮相等。为此,可以根据需要多次执行下述操作:

  • 选中两个下标 i 和 j ,并交换 basket1 中的第 i 个水果和 basket2 中的第 j 个水果。
  • 交换的成本是 min(basket1i,basket2j) 。

根据果篮中水果的成本进行排序,如果排序后结果完全相同,则认为两个果篮相等。

返回使两个果篮相等的最小交换成本,如果无法使两个果篮相等,则返回 -1 。

示例 1:

输入:basket1 = [4,2,2,2], basket2 = [1,4,1,2]
输出:1
解释:交换 basket1 中下标为 1 的水果和 basket2 中下标为 0 的水果,交换的成本为 1 。此时,basket1 = [4,1,2,2] 且 basket2 = [2,4,1,2] 。重排两个数组,发现二者相等。

示例 2:

输入:basket1 = [2,3,4,1], basket2 = [3,2,5,1]
输出:-1
解释:可以证明无法使两个果篮相等。

说明:

  • basket1.length == bakste2.length
  • 1 <= basket1.length <= 10^5
  • 1 <= basket1i,basket2i <= 10^9

思路

代码

性能

3480.删除一个冲突对后最大子数组数目

目标

给你一个整数 n,表示一个包含从 1 到 n 按顺序排列的整数数组 nums。此外,给你一个二维数组 conflictingPairs,其中 conflictingPairs[i] = [a, b] 表示 a 和 b 形成一个冲突对。

从 conflictingPairs 中删除 恰好 一个元素。然后,计算数组 nums 中的非空子数组数量,这些子数组都不能同时包含任何剩余冲突对 [a, b] 中的 a 和 b。

返回删除 恰好 一个冲突对后可能得到的 最大 子数组数量。

子数组 是数组中一个连续的 非空 元素序列。

示例 1

输入: n = 4, conflictingPairs = [[2,3],[1,4]]
输出: 9
解释:
从 conflictingPairs 中删除 [2, 3]。现在,conflictingPairs = [[1, 4]]。
在 nums 中,存在 9 个子数组,其中 [1, 4] 不会一起出现。它们分别是 [1],[2],[3],[4],[1, 2],[2, 3],[3, 4],[1, 2, 3] 和 [2, 3, 4]。
删除 conflictingPairs 中一个元素后,能够得到的最大子数组数量是 9。

示例 2

输入: n = 5, conflictingPairs = [[1,2],[2,5],[3,5]]
输出: 12
解释:
从 conflictingPairs 中删除 [1, 2]。现在,conflictingPairs = [[2, 5], [3, 5]]。
在 nums 中,存在 12 个子数组,其中 [2, 5] 和 [3, 5] 不会同时出现。
删除 conflictingPairs 中一个元素后,能够得到的最大子数组数量是 12。

说明:

  • 2 <= n <= 10^5
  • 1 <= conflictingPairs.length <= 2 * n
  • conflictingPairs[i].length == 2
  • 1 <= conflictingPairs[i][j] <= n
  • conflictingPairs[i][0] != conflictingPairs[i][1]

思路

代码

性能

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

目标

存在一棵无向连通树,树中有编号从 0 到 n - 1 的 n 个节点, 以及 n - 1 条边。

给你一个下标从 0 开始的整数数组 nums ,长度为 n ,其中 nums[i] 表示第 i 个节点的值。另给你一个二维整数数组 edges ,长度为 n - 1 ,其中 edges[i] = [ai, bi] 表示树中存在一条位于节点 ai 和 bi 之间的边。

删除树中两条 不同 的边以形成三个连通组件。对于一种删除边方案,定义如下步骤以计算其分数:

  1. 分别获取三个组件 每个 组件中所有节点值的异或值。
  2. 最大 异或值和 最小 异或值的 差值 就是这一种删除边方案的分数。
  • 例如,三个组件的节点值分别是:[4,5,7]、[1,9] 和 [3,3,3] 。三个异或值分别是 4 ^ 5 ^ 7 = 6、1 ^ 9 = 8 和 3 ^ 3 ^ 3 = 3 。最大异或值是 8 ,最小异或值是 3 ,分数是 8 - 3 = 5 。

返回在给定树上执行任意删除边方案可能的 最小 分数。

示例 1:

输入:nums = [1,5,5,4,11], edges = [[0,1],[1,2],[1,3],[3,4]]
输出:9
解释:上图展示了一种删除边方案。
- 第 1 个组件的节点是 [1,3,4] ,值是 [5,4,11] 。异或值是 5 ^ 4 ^ 11 = 10 。
- 第 2 个组件的节点是 [0] ,值是 [1] 。异或值是 1 = 1 。
- 第 3 个组件的节点是 [2] ,值是 [5] 。异或值是 5 = 5 。
分数是最大异或值和最小异或值的差值,10 - 1 = 9 。
可以证明不存在分数比 9 小的删除边方案。

示例 2:

输入:nums = [5,5,2,4,4,2], edges = [[0,1],[1,2],[5,2],[4,3],[1,3]]
输出:0
解释:上图展示了一种删除边方案。
- 第 1 个组件的节点是 [3,4] ,值是 [4,4] 。异或值是 4 ^ 4 = 0 。
- 第 2 个组件的节点是 [1,0] ,值是 [5,5] 。异或值是 5 ^ 5 = 0 。
- 第 3 个组件的节点是 [2,5] ,值是 [2,2] 。异或值是 2 ^ 2 = 0 。
分数是最大异或值和最小异或值的差值,0 - 0 = 0 。
无法获得比 0 更小的分数 0 。

说明:

  • n == nums.length
  • 3 <= n <= 1000
  • 1 <= nums[i] <= 10^8
  • edges.length == n - 1
  • edges[i].length == 2
  • 0 <= ai, bi < n
  • ai != bi
  • edges 表示一棵有效的树

思路

树中删除两条边,得到三个连通分量,计算每个连通分量的异或值,定义最大异或值减去最小异或值为该删除方案的分数,求所有删除方案中最小的分数。

// todo

代码

性能

1948.删除系统中的重复文件夹

目标

由于一个漏洞,文件系统中存在许多重复文件夹。给你一个二维数组 paths,其中 paths[i] 是一个表示文件系统中第 i 个文件夹的绝对路径的数组。

例如,["one", "two", "three"] 表示路径 "/one/two/three" 。
如果两个文件夹(不需要在同一层级)包含 非空且相同的 子文件夹 集合 并具有相同的子文件夹结构,则认为这两个文件夹是相同文件夹。相同文件夹的根层级 不 需要相同。如果存在两个(或两个以上)相同 文件夹,则需要将这些文件夹和所有它们的子文件夹 标记 为待删除。

例如,下面文件结构中的文件夹 "/a" 和 "/b" 相同。它们(以及它们的子文件夹)应该被 全部 标记为待删除:

  • /a
  • /a/x
  • /a/x/y
  • /a/z
  • /b
  • /b/x
  • /b/x/y
  • /b/z

然而,如果文件结构中还包含路径 "/b/w" ,那么文件夹 "/a" 和 "/b" 就不相同。注意,即便添加了新的文件夹 "/b/w" ,仍然认为 "/a/x" 和 "/b/x" 相同。

一旦所有的相同文件夹和它们的子文件夹都被标记为待删除,文件系统将会 删除 所有上述文件夹。文件系统只会执行一次删除操作。执行完这一次删除操作后,不会删除新出现的相同文件夹。

返回二维数组 ans ,该数组包含删除所有标记文件夹之后剩余文件夹的路径。路径可以按 任意顺序 返回。

示例 1:

输入:paths = [["a"],["c"],["d"],["a","b"],["c","b"],["d","a"]]
输出:[["d"],["d","a"]]
解释:文件结构如上所示。
文件夹 "/a" 和 "/c"(以及它们的子文件夹)都会被标记为待删除,因为它们都包含名为 "b" 的空文件夹。

示例 2:

输入:paths = [["a"],["c"],["a","b"],["c","b"],["a","b","x"],["a","b","x","y"],["w"],["w","y"]]
输出:[["c"],["c","b"],["a"],["a","b"]]
解释:文件结构如上所示。
文件夹 "/a/b/x" 和 "/w"(以及它们的子文件夹)都会被标记为待删除,因为它们都包含名为 "y" 的空文件夹。
注意,文件夹 "/a" 和 "/c" 在删除后变为相同文件夹,但这两个文件夹不会被删除,因为删除只会进行一次,且它们没有在删除前被标记。

示例 3:

输入:paths = [["a","b"],["c","d"],["c"],["a"]]
输出:[["c"],["c","d"],["a"],["a","b"]]
解释:文件系统中所有文件夹互不相同。
注意,返回的数组可以按不同顺序返回文件夹路径,因为题目对顺序没有要求。

示例 4:

输入:paths = [["a"],["a","x"],["a","x","y"],["a","z"],["b"],["b","x"],["b","x","y"],["b","z"]]
输出:[]
解释:文件结构如上所示。
文件夹 "/a/x" 和 "/b/x"(以及它们的子文件夹)都会被标记为待删除,因为它们都包含名为 "y" 的空文件夹。
文件夹 "/a" 和 "/b"(以及它们的子文件夹)都会被标记为待删除,因为它们都包含一个名为 "z" 的空文件夹以及上面提到的文件夹 "x" 。

示例 5:

输入:paths = [["a"],["a","x"],["a","x","y"],["a","z"],["b"],["b","x"],["b","x","y"],["b","z"],["b","w"]]
输出:[["b"],["b","w"],["b","z"],["a"],["a","z"]]
解释:本例与上例的结构基本相同,除了新增 "/b/w" 文件夹。
文件夹 "/a/x" 和 "/b/x" 仍然会被标记,但 "/a" 和 "/b" 不再被标记,因为 "/b" 中有名为 "w" 的空文件夹而 "/a" 没有。
注意,"/a/z" 和 "/b/z" 不会被标记,因为相同子文件夹的集合必须是非空集合,但这两个文件夹都是空的。

说明:

  • 1 <= paths.length <= 2 * 10^4
  • 1 <= paths[i].length <= 500
  • 1 <= paths[i][j].length <= 10
  • 1 <= sum(paths[i][j].length) <= 2 * 10^5
  • path[i][j] 由小写英文字母组成
  • 不会存在两个路径都指向同一个文件夹的情况
  • 对于不在根层级的任意文件夹,其父文件夹也会包含在输入中

思路

代码

性能

1900.最佳运动员的比拼回合

目标

n 名运动员参与一场锦标赛,所有运动员站成一排,并根据 最开始的 站位从 1 到 n 编号(运动员 1 是这一排中的第一个运动员,运动员 2 是第二个运动员,依此类推)。

锦标赛由多个回合组成(从回合 1 开始)。每一回合中,这一排从前往后数的第 i 名运动员需要与从后往前数的第 i 名运动员比拼,获胜者将会进入下一回合。如果当前回合中运动员数目为奇数,那么中间那位运动员将轮空晋级下一回合。

例如,当前回合中,运动员 1, 2, 4, 6, 7 站成一排

  • 运动员 1 需要和运动员 7 比拼
  • 运动员 2 需要和运动员 6 比拼
  • 运动员 4 轮空晋级下一回合

每回合结束后,获胜者将会基于最开始分配给他们的原始顺序(升序)重新排成一排。

编号为 firstPlayer 和 secondPlayer 的运动员是本场锦标赛中的最佳运动员。在他们开始比拼之前,完全可以战胜任何其他运动员。而任意两个其他运动员进行比拼时,其中任意一个都有获胜的可能,因此你可以 裁定 谁是这一回合的获胜者。

给你三个整数 n、firstPlayer 和 secondPlayer 。返回一个由两个值组成的整数数组,分别表示两位最佳运动员在本场锦标赛中比拼的 最早 回合数和 最晚 回合数。

示例 1:

输入:n = 11, firstPlayer = 2, secondPlayer = 4
输出:[3,4]
解释:
一种能够产生最早回合数的情景是:
回合 1:1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
回合 2:2, 3, 4, 5, 6, 11
回合 3:2, 3, 4
一种能够产生最晚回合数的情景是:
回合 1:1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
回合 2:1, 2, 3, 4, 5, 6
回合 3:1, 2, 4
回合 4:2, 4

示例 2:

输入:n = 5, firstPlayer = 1, secondPlayer = 5
输出:[1,1]
解释:两名最佳运动员 1 和 5 将会在回合 1 进行比拼。
不存在使他们在其他回合进行比拼的可能。

说明:

  • 2 <= n <= 28
  • 1 <= firstPlayer < secondPlayer <= n

思路

代码

性能

2014.重复K次的最长子序列

目标

给你一个长度为 n 的字符串 s ,和一个整数 k 。请你找出字符串 s 中 重复 k 次的 最长子序列 。

子序列 是由其他字符串删除某些(或不删除)字符派生而来的一个字符串。

如果 seq * k 是 s 的一个子序列,其中 seq * k 表示一个由 seq 串联 k 次构造的字符串,那么就称 seq 是字符串 s 中一个 重复 k 次 的子序列。

  • 举个例子,"bba" 是字符串 "bababcba" 中的一个重复 2 次的子序列,因为字符串 "bbabba" 是由 "bba" 串联 2 次构造的,而 "bbabba" 是字符串 "bababcba" 的一个子序列。

返回字符串 s 中 重复 k 次的最长子序列 。如果存在多个满足的子序列,则返回 字典序最大 的那个。如果不存在这样的子序列,返回一个 空 字符串。

示例 1:

输入:s = "letsleetcode", k = 2
输出:"let"
解释:存在两个最长子序列重复 2 次:let" 和 "ete" 。
"let" 是其中字典序最大的一个。

示例 2:

输入:s = "bb", k = 2
输出:"b"
解释:重复 2 次的最长子序列是 "b" 。

示例 3:

输入:s = "ab", k = 2
输出:""
解释:不存在重复 2 次的最长子序列。返回空字符串。

说明:

  • n == s.length
  • 2 <= k <= 2000
  • 2 <= n < k * 8
  • s 由小写英文字母组成

思路

// todo

代码

性能

2040.两个有序数组的第K小乘积

目标

给你两个 从小到大排好序 且下标从 0 开始的整数数组 nums1 和 nums2 以及一个整数 k ,请你返回第 k (从 1 开始编号)小的 nums1[i] * nums2[j] 的乘积,其中 0 <= i < nums1.length 且 0 <= j < nums2.length 。

示例 1:

输入:nums1 = [2,5], nums2 = [3,4], k = 2
输出:8
解释:第 2 小的乘积计算如下:
- nums1[0] * nums2[0] = 2 * 3 = 6
- nums1[0] * nums2[1] = 2 * 4 = 8
第 2 小的乘积为 8 。

示例 2:

输入:nums1 = [-4,-2,0,3], nums2 = [2,4], k = 6
输出:0
解释:第 6 小的乘积计算如下:
- nums1[0] * nums2[1] = (-4) * 4 = -16
- nums1[0] * nums2[0] = (-4) * 2 = -8
- nums1[1] * nums2[1] = (-2) * 4 = -8
- nums1[1] * nums2[0] = (-2) * 2 = -4
- nums1[2] * nums2[0] = 0 * 2 = 0
- nums1[2] * nums2[1] = 0 * 4 = 0
第 6 小的乘积为 0 。

示例 3:

输入:nums1 = [-2,-1,0,1,2], nums2 = [-3,-1,2,4,5], k = 3
输出:-6
解释:第 3 小的乘积计算如下:
- nums1[0] * nums2[4] = (-2) * 5 = -10
- nums1[0] * nums2[3] = (-2) * 4 = -8
- nums1[4] * nums2[0] = 2 * (-3) = -6
第 3 小的乘积为 -6 。

说明:

  • 1 <= nums1.length, nums2.length <= 5 * 10^4
  • -10^5 <= nums1[i], nums2[j] <= 10^5
  • 1 <= k <= nums1.length * nums2.length
  • nums1 和 nums2 都是从小到大排好序的。

思路

有两个有序数组 nums1nums2,从两个数组中中各取一个数相乘,返回第 k 小的乘积。

代码

性能

2081.k镜像数字的和

目标

一个 k 镜像数字 指的是一个在十进制和 k 进制下从前往后读和从后往前读都一样的 没有前导 0 的 正 整数。

  • 比方说,9 是一个 2 镜像数字。9 在十进制下为 9 ,二进制下为 1001 ,两者从前往后读和从后往前读都一样。
  • 相反地,4 不是一个 2 镜像数字。4 在二进制下为 100 ,从前往后和从后往前读不相同。

给你进制 k 和一个数字 n ,请你返回 k 镜像数字中 最小 的 n 个数 之和 。

示例 1:

输入:k = 2, n = 5
输出:25
解释:
最小的 5 个 2 镜像数字和它们的二进制表示如下:
  十进制       二进制
    1          1
    3          11
    5          101
    7          111
    9          1001
它们的和为 1 + 3 + 5 + 7 + 9 = 25 。

示例 2:

输入:k = 3, n = 7
输出:499
解释:
7 个最小的 3 镜像数字和它们的三进制表示如下:
  十进制       三进制
    1          1
    2          2
    4          11
    8          22
    121        11111
    151        12121
    212        21212
它们的和为 1 + 2 + 4 + 8 + 121 + 151 + 212 = 499 。

示例 3:

输入:k = 7, n = 17
输出:20379000
解释:17 个最小的 7 镜像数字分别为:
1, 2, 3, 4, 5, 6, 8, 121, 171, 242, 292, 16561, 65656, 2137312, 4602064, 6597956, 6958596

说明:

  • 2 <= k <= 9
  • 1 <= n <= 30

思路

核心思想:

  1. 首先枚举 10 进制下的镜像数字
  2. 判断这些镜像数字是否是 k 进制下的镜像数字

代码

//todo

性能