fork()==0世界线变动

100216. K 个不相交子数组的最大能量值

给你一个长度为 n 下标从 0 开始的整数数组 nums 和一个 正奇数 整数 k 。

x 个子数组的能量值定义为 strength = sum[1] * x - sum[2] * (x - 1) + sum[3] * (x - 2) - sum[4] * (x - 3) + ... + sum[x] * 1 ，其中 sum[i] 是第 i 个子数组的和。更正式的，能量值是满足 1 <= i <= x 的所有 i 对应的 (-1)^i+1 * sum[i] * (x - i + 1) 之和。

你需要在 nums 中选择 k 个 不相交子数组 ，使得 能量值最大 。

请你返回可以得到的 最大能量值 。

注意，选出来的所有子数组 不 需要覆盖整个数组。

示例 1：

```txt

输入：nums = [1,2,3,-1,2], k = 3

输出：22

解释：选择 3 个子数组的最好方式是选择：nums[0..2] ，nums[3..3] 和 nums[4..4] 。能量值为 (1 + 2 + 3) * 3 - (-1) * 2 + 2 * 1 = 22 。

```

示例 2：

```txt

输入：nums = [12,-2,-2,-2,-2], k = 5

输出：64

解释：唯一一种选 5 个不相交子数组的方案是：nums[0..0] ，nums[1..1] ，nums[2..2] ，nums[3..3] 和 nums[4..4] 。能量值为 12 * 5 - (-2) * 4 + (-2) * 3 - (-2) * 2 + (-2) * 1 = 64 。

```

示例 3：

```txt

输入：nums = [-1,-2,-3], k = 1

输出：-1

解释：选择 1 个子数组的最优方案是：nums[0..0] 。能量值为 -1 。

```

提示：

• 1 <= n <= 10^4

• -10^9 <= nums[i] <= 10^9

• 1 <= k <= n

• 1 <= n * k <= 10^6

• k 是奇数。

1187. 使数组严格递增

给你两个整数数组 arr1 和 arr2，返回使 arr1 严格递增所需要的最小「操作」数（可能为 0）。

每一步「操作」中，你可以分别从 arr1 和 arr2 中各选出一个索引，分别为 i 和 j，0 <= i < arr1.length 和 0 <= j < arr2.length，然后进行赋值运算 arr1[i] = arr2[j]。

如果无法让 arr1 严格递增，请返回 -1。

示例 1：

```txt

输入：arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]

输出：1

解释：用 2 来替换 5，之后 arr1 = [1, 2, 3, 6, 7]。

```

示例 2：

```txt

输入：arr1 = [1,5,3,6,7], arr2 = [4,3,1]

输出：2

解释：用 3 来替换 5，然后用 4 来替换 3，得到 arr1 = [1, 3, 4, 6, 7]。

```

示例 3：

```txt

输入：arr1 = [1,5,3,6,7], arr2 = [1,6,3,3]

输出：-1

解释：无法使 arr1 严格递增。

```

提示：

• 1 <= arr1.length, arr2.length <= 2000

• 0 <= arr1[i], arr2[i] <= 10^9

1611. 使整数变为 0 的最少操作次数

给你一个整数 n，你需要重复执行多次下述操作将其转换为 0 ：

• 翻转 n 的二进制表示中最右侧位（第 0 位）。

• 如果第 (i-1) 位为 1 且从第 (i-2) 位到第 0 位都为 0，则翻转 n 的二进制表示中的第 i 位。

返回将 n 转换为 0 的最小操作次数。

示例 1：

```txt

输入：n = 3

输出：2

解释：3 的二进制表示为 "11"

"11" -> "01" ，执行的是第 2 种操作，因为第 0 位为 1 。

"01" -> "00" ，执行的是第 1 种操作。

```

示例 2：

```txt

输入：n = 6

输出：4

解释：6 的二进制表示为 "110".

"110" -> "010" ，执行的是第 2 种操作，因为第 1 位为 1 ，第 0 到 0 位为 0 。

"010" -> "011" ，执行的是第 1 种操作。

"011" -> "001" ，执行的是第 2 种操作，因为第 0 位为 1 。

"001" -> "000" ，执行的是第 1 种操作。

```

提示：

• 0 <= n <= 10^9

1713. 得到子序列的最少操作次数

给你一个数组 target ，包含若干 互不相同 的整数，以及另一个整数数组 arr ，arr 可能 包含重复元素。

每一次操作中，你可以在 arr 的任意位置插入任一整数。比方说，如果 arr = [1,4,1,2] ，那么你可以在中间添加 3 得到 [1,4,**3**,1,2] 。你可以在数组最开始或最后面添加整数。

请你返回 最少 操作次数，使得 target 成为 arr 的一个子序列。

一个数组的 子序列 指的是删除原数组的某些元素（可能一个元素都不删除），同时不改变其余元素的相对顺序得到的数组。比方说，[2,7,4] 是 [4,**2**,3,**7**,2,1,**4**] 的子序列（加粗元素），但 [2,4,2] 不是子序列。

示例 1：

```txt

输入：target = [5,1,3], arr = [9,4,2,3,4]

输出：2

解释：你可以添加 5 和 1 ，使得 arr 变为 [5,9,4,1,2,3,4] ，target 为 arr 的子序列。

```

示例 2：

```txt

输入：target = [6,4,8,1,3,2], arr = [4,7,6,2,3,8,6,1]

输出：3

```

提示：

• 1 <= target.length, arr.length <= 10^5

• 1 <= target[i], arr[i] <= 10^9

• target 不包含任何重复元素。

10038. 执行操作后的最大分割数量

给你一个下标从 0 开始的字符串 s 和一个整数 k。

你需要执行以下分割操作，直到字符串 s 变为 空：

• 选择 s 的最长前缀，该前缀最多包含 k 个 不同 字符。

• 删除 这个前缀，并将分割数量加一。如果有剩余字符，它们在 s 中保持原来的顺序。

执行操作之 前 ，你可以将 s 中 至多一处 下标的对应字符更改为另一个小写英文字母。

在最优选择情形下改变至多一处下标对应字符后，用整数表示并返回操作结束时得到的最大分割数量。

示例 1：

```txt

输入：s = "accca", k = 2

输出：3

解释：在此示例中，为了最大化得到的分割数量，可以将 s[2] 改为 'b'。

s 变为 "acbca"。

按照以下方式执行操作，直到 s 变为空：

• 选择最长且至多包含 2 个不同字符的前缀，"acbca"。

• 删除该前缀，s 变为 "bca"。现在分割数量为 1。

• 选择最长且至多包含 2 个不同字符的前缀，"bca"。

• 删除该前缀，s 变为 "a"。现在分割数量为 2。

• 选择最长且至多包含 2 个不同字符的前缀，"a"。

• 删除该前缀，s 变为空。现在分割数量为 3。

因此，答案是 3。

可以证明，分割数量不可能超过 3。

```

示例 2：

```txt

输入：s = "aabaab", k = 3

输出：1

解释：在此示例中，为了最大化得到的分割数量，可以保持 s 不变。

按照以下方式执行操作，直到 s 变为空：

• 选择最长且至多包含 3 个不同字符的前缀，"aabaab"。

• 删除该前缀，s 变为空。现在分割数量为 1。

因此，答案是 1。

可以证明，分割数量不可能超过 1。

```

示例 3：

```txt

输入：s = "xxyz", k = 1

输出：4

解释：在此示例中，为了最大化得到的分割数量，可以将 s[1] 改为 'a'。

s 变为 "xayz"。

按照以下方式执行操作，直到 s 变为空：

• 选择最长且至多包含 1 个不同字符的前缀，"xayz"。

• 删除该前缀，s 变为 "ayz"。现在分割数量为 1。

• 选择最长且至多包含 1 个不同字符的前缀，"ayz"。

• 删除该前缀，s 变为 "yz"，现在分割数量为 2。

• 选择最长且至多包含 1 个不同字符的前缀，"yz"。

• 删除该前缀，s 变为 "z"。现在分割数量为 3。

• 选择最且至多包含 1 个不同字符的前缀，"z"。

• 删除该前缀，s 变为空。现在分割数量为 4。

因此，答案是 4。

可以证明，分割数量不可能超过 4。

```

提示：

• 1 <= s.length <= 10^4

• s 只包含小写英文字母。

• 1 <= k <= 26

2547. 拆分数组的最小代价

给你一个整数数组 nums 和一个整数 k 。

将数组拆分成一些非空子数组。拆分的 代价 是每个子数组中的 重要性 之和。

令 trimmed(subarray) 作为子数组的一个特征，其中所有仅出现一次的数字将会被移除。

• 例如，trimmed([3,1,2,4,3,4]) = [3,4,3,4] 。

子数组的 重要性 定义为 k + trimmed(subarray).length 。

• 例如，如果一个子数组是 [1,2,3,3,3,4,4] ，trimmed([1,2,3,3,3,4,4]) = [3,3,3,4,4] 。这个子数组的重要性就是 k + 5 。

找出并返回拆分 nums 的所有可行方案中的最小代价。

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

示例 1：

```txt

输入：nums = [1,2,1,2,1,3,3], k = 2

输出：8

解释：将 nums 拆分成两个子数组：[1,2], [1,2,1,3,3]

[1,2] 的重要性是 2 + (0) = 2 。

[1,2,1,3,3] 的重要性是 2 + (2 + 2) = 6 。

拆分的代价是 2 + 6 = 8 ，可以证明这是所有可行的拆分方案中的最小代价。

```

示例 2：

```txt

输入：nums = [1,2,1,2,1], k = 2

输出：6

解释：将 nums 拆分成两个子数组：[1,2], [1,2,1] 。

[1,2] 的重要性是 2 + (0) = 2 。

[1,2,1] 的重要性是 2 + (2) = 4 。

拆分的代价是 2 + 4 = 6 ，可以证明这是所有可行的拆分方案中的最小代价。

```

示例 3：

```txt

输入：nums = [1,2,1,2,1], k = 5

输出：10

解释：将 nums 拆分成一个子数组：[1,2,1,2,1].

[1,2,1,2,1] 的重要性是 5 + (3 + 2) = 10 。

拆分的代价是 10 ，可以证明这是所有可行的拆分方案中的最小代价。

```

提示：

• 1 <= nums.length <= 1000

• 0 <= nums[i] < nums.length

• 1 <= k <= 10^9

1824. 最少侧跳次数

给你一个长度为 n 的 3 跑道道路 ，它总共包含 n + 1 个 点 ，编号为 0 到 n 。一只青蛙从 0 号点第二条跑道 出发 ，它想要跳到点 n 处。然而道路上可能有一些障碍。

给你一个长度为 n + 1 的数组 obstacles ，其中 obstacles[i] （取值范围从 0 到 3）表示在点 i 处的 obstacles[i] 跑道上有一个障碍。如果 obstacles[i] == 0 ，那么点 i 处没有障碍。任何一个点的三条跑道中 最多有一个 障碍。

• 比方说，如果 obstacles[2] == 1 ，那么说明在点 2 处跑道 1 有障碍。

这只青蛙从点 i 跳到点 i + 1 且跑道不变的前提是点 i + 1 的同一跑道上没有障碍。为了躲避障碍，这只青蛙也可以在 同一个 点处 侧跳 到 另外一条 跑道（这两条跑道可以不相邻），但前提是跳过去的跑道该点处没有障碍。

• 比方说，这只青蛙可以从点 3 处的跑道 3 跳到点 3 处的跑道 1 。

这只青蛙从点 0 处跑道 2 出发，并想到达点 n 处的 任一跑道 ，请你返回 最少侧跳次数 。

注意：点 0 处和点 n 处的任一跑道都不会有障碍。

示例 1：

```txt

输入：obstacles = [0,1,2,3,0]

输出：2

解释：最优方案如上图箭头所示。总共有 2 次侧跳（红色箭头）。

注意，这只青蛙只有当侧跳时才可以跳过障碍（如上图点 2 处所示）。

```

示例 2：

```txt

输入：obstacles = [0,1,1,3,3,0]

输出：0

解释：跑道 2 没有任何障碍，所以不需要任何侧跳。

```

示例 3：

```txt

输入：obstacles = [0,2,1,0,3,0]

输出：2

解释：最优方案如上图所示。总共有 2 次侧跳。

```

提示：

• obstacles.length == n + 1

• 1 <= n <= 5 * 10^5

• 0 <= obstacles[i] <= 3

• obstacles[0] == obstacles[n] == 0