fork()==0世界线变动

1755. 最接近目标值的子序列和

给你一个整数数组 nums 和一个目标值 goal 。

你需要从 nums 中选出一个子序列，使子序列元素总和最接近 goal 。也就是说，如果子序列元素和为 sum ，你需要 最小化绝对差 abs(sum - goal) 。

返回 abs(sum - goal) 可能的 最小值 。

注意，数组的子序列是通过移除原始数组中的某些元素（可能全部或无）而形成的数组。

示例 1：

```txt

输入：nums = [5,-7,3,5], goal = 6

输出：0

解释：选择整个数组作为选出的子序列，元素和为 6 。

子序列和与目标值相等，所以绝对差为 0 。

```

示例 2：

```txt

输入：nums = [7,-9,15,-2], goal = -5

输出：1

解释：选出子序列 [7,-9,-2] ，元素和为 -4 。

绝对差为 abs(-4 - (-5)) = abs(1) = 1 ，是可能的最小值。

```

示例 3：

```txt

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

输出：7

```

提示：

• 1 <= nums.length <= 40

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

• -10^9 <= goal <= 10^9

956. 最高的广告牌

你正在安装一个广告牌，并希望它高度最大。这块广告牌将有两个钢制支架，两边各一个。每个钢支架的高度必须相等。

你有一堆可以焊接在一起的钢筋 rods。举个例子，如果钢筋的长度为 1、2 和 3，则可以将它们焊接在一起形成长度为 6 的支架。

返回 广告牌的最大可能安装高度 。如果没法安装广告牌，请返回 0 。

示例 1：

```txt

输入：[1,2,3,6]

输出：6

解释：我们有两个不相交的子集 {1,2,3} 和 {6}，它们具有相同的和 sum = 6。

```

示例 2：

```txt

输入：[1,2,3,4,5,6]

输出：10

解释：我们有两个不相交的子集 {2,3,5} 和 {4,6}，它们具有相同的和 sum = 10。

```

示例 3：

```txt

输入：[1,2]

输出：0

解释：没法安装广告牌，所以返回 0。

```

提示：

1. 0 <= rods.length <= 20

2. 1 <= rods[i] <= 1000

3. sum(rods[i]) <= 5000

494. 目标和

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

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

• 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：

```txt

输入：nums = [1,1,1,1,1], target = 3

输出：5

解释：一共有 5 种方法让最终目标和为 3 。

-1 + 1 + 1 + 1 + 1 = 3

+1 - 1 + 1 + 1 + 1 = 3

+1 + 1 - 1 + 1 + 1 = 3

+1 + 1 + 1 - 1 + 1 = 3

+1 + 1 + 1 + 1 - 1 = 3

```

示例 2：

```txt

输入：nums = [1], target = 1

输出：1

```

提示：

• 1 <= nums.length <= 20

• 0 <= nums[i] <= 1000

• 0 <= sum(nums[i]) <= 1000

• -1000 <= target <= 1000

6356. 收集树中金币

给你一个 n 个节点的无向无根树，节点编号从 0 到 n - 1 。给你整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间有一条边。再给你一个长度为 n 的数组 coins ，其中 coins[i] 可能为 0 也可能为 1 ，1 表示节点 i 处有一个金币。

一开始，你需要选择树中任意一个节点出发。你可以执行下述操作任意次：

• 收集距离当前节点距离为 2 以内的所有金币，或者

• 移动到树中一个相邻节点。

你需要收集树中所有的金币，并且回到出发节点，请你返回最少经过的边数。

如果你多次经过一条边，每一次经过都会给答案加一。

示例 1：

```txt

输入：coins = [1,0,0,0,0,1], edges = [[0,1],[1,2],[2,3],[3,4],[4,5]]

输出：2

解释：从节点 2 出发，收集节点 0 处的金币，移动到节点 3 ，收集节点 5 处的金币，然后移动回节点 2 。

```

示例 2：

```txt

输入：coins = [0,0,0,1,1,0,0,1], edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[5,6],[5,7]]

输出：2

解释：从节点 0 出发，收集节点 4 和 3 处的金币，移动到节点 2 处，收集节点 7 处的金币，移动回节点 0 。

```

提示：

• n == coins.length

• 1 <= n <= 3 * 10^4

• 0 <= coins[i] <= 1

• edges.length == n - 1

• edges[i].length == 2

• 0 <= ai, bi < n

• ai != bi

• edges 表示一棵合法的树。

2531. 使字符串总不同字符的数目相等

给你两个下标从 0 开始的字符串 word1 和 word2 。

一次 移动 由以下两个步骤组成：

• 选中两个下标 i 和 j ，分别满足 0 <= i < word1.length 和 0 <= j < word2.length ，

• 交换 word1[i] 和 word2[j] 。

如果可以通过 恰好一次 移动，使 word1 和 word2 中不同字符的数目相等，则返回 true ；否则，返回 false 。

示例 1：

```txt

输入：word1 = "ac", word2 = "b"

输出：false

解释：交换任何一组下标都会导致第一个字符串中有 2 个不同的字符，而在第二个字符串中只有 1 个不同字符。

```

示例 2：

```txt

输入：word1 = "abcc", word2 = "aab"

输出：true

解释：交换第一个字符串的下标 2 和第二个字符串的下标 0 。之后得到 word1 = "abac" 和 word2 = "cab" ，各有 3 个不同字符。

```

示例 3：

```txt

输入：word1 = "abcde", word2 = "fghij"

输出：true

解释：无论交换哪一组下标，两个字符串中都会有 5 个不同字符。

```

提示：

• 1 <= word1.length, word2.length <= 10^5

• word1 和 word2 仅由小写英文字母组成。

100097. 合法分组的最少组数

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

我们想将下标进行分组，使得 [0, n - 1] 内所有下标 i 都 恰好 被分到其中一组。

如果以下条件成立，我们说这个分组方案是合法的：

• 对于每个组 g ，同一组内所有下标在 nums 中对应的数值都相等。

• 对于任意两个组 g1 和 g2 ，两个组中 下标数量 的 差值不超过 1 。

请你返回一个整数，表示得到一个合法分组方案的 最少 组数。

示例 1：

```txt

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

输出：2

解释：一个得到 2 个分组的方案如下，中括号内的数字都是下标：

组 1 -> [0,2,4]

组 2 -> [1,3]

所有下标都只属于一个组。

组 1 中，nums[0] == nums[2] == nums[4] ，所有下标对应的数值都相等。

组 2 中，nums[1] == nums[3] ，所有下标对应的数值都相等。

组 1 中下标数目为 3 ，组 2 中下标数目为 2 。

两者之差不超过 1 。

无法得到一个小于 2 组的答案，因为如果只有 1 组，组内所有下标对应的数值都要相等。

所以答案为 2 。

```

示例 2：

```txt

输入：nums = [10,10,10,3,1,1]

输出：4

解释：一个得到 2 个分组的方案如下，中括号内的数字都是下标：

组 1 -> [0]

组 2 -> [1,2]

组 3 -> [3]

组 4 -> [4,5]

分组方案满足题目要求的两个条件。

无法得到一个小于 4 组的答案。

所以答案为 4 。

```

提示：

• 1 <= nums.length <= 10^5

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

2850. 将石头分散到网格图的最少移动次数

给你一个大小为 3 * 3 ，下标从 0 开始的二维整数矩阵 grid ，分别表示每一个格子里石头的数目。网格图中总共恰好有 9 个石头，一个格子里可能会有 多个 石头。

每一次操作中，你可以将一个石头从它当前所在格子移动到一个至少有一条公共边的相邻格子。

请你返回每个格子恰好有一个石头的 最少移动次数 。

示例 1：

```txt

输入：grid = [[1,1,0],[1,1,1],[1,2,1]]

输出：3

解释：让每个格子都有一个石头的一个操作序列为：

1 - 将一个石头从格子 (2,1) 移动到 (2,2) 。

2 - 将一个石头从格子 (2,2) 移动到 (1,2) 。

3 - 将一个石头从格子 (1,2) 移动到 (0,2) 。

总共需要 3 次操作让每个格子都有一个石头。

让每个格子都有一个石头的最少操作次数为 3 。

```

示例 2：

```txt

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

输出：4

解释：让每个格子都有一个石头的一个操作序列为：

1 - 将一个石头从格子 (0,1) 移动到 (0,2) 。

2 - 将一个石头从格子 (0,1) 移动到 (1,1) 。

3 - 将一个石头从格子 (2,2) 移动到 (1,2) 。

4 - 将一个石头从格子 (2,2) 移动到 (2,1) 。

总共需要 4 次操作让每个格子都有一个石头。

让每个格子都有一个石头的最少操作次数为 4 。

```

提示：

• grid.length == grid[i].length == 3

• 0 <= grid[i][j] <= 9

• grid 中元素之和为 9 。