代码如诗

2035. 将数组分成两个数组并最小化数组和的差

给你一个长度为 2 * n 的整数数组。你需要将 nums 分成 两个 长度为 n 的数组，分别求出两个数组的和，并 最小化 两个数组和之 差的绝对值 。nums 中每个元素都需要放入两个数组之一。

请你返回 最小 的数组和之差。

示例 1：

```txt

输入：nums = [3,9,7,3]

输出：2

解释：最优分组方案是分成 [3,9] 和 [7,3] 。

数组和之差的绝对值为 abs((3 + 9) - (7 + 3)) = 2 。

```

示例 2：

```txt

输入：nums = [-36,36]

输出：72

解释：最优分组方案是分成 [-36] 和 [36] 。

数组和之差的绝对值为 abs((-36) - (36)) = 72 。

```

示例 3：

```txt

输入：nums = [2,-1,0,4,-2,-9]

输出：0

解释：最优分组方案是分成 [2,4,-9] 和 [-1,0,-2] 。

数组和之差的绝对值为 abs((2 + 4 + -9) - (-1 + 0 + -2)) = 0 。

```

提示：

• 1 <= n <= 15

• nums.length == 2 * n

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

805. 数组的均值分割

给定你一个整数数组 nums

我们要将 nums 数组中的每个元素移动到 A 数组 或者 B 数组中，使得 A 数组和 B 数组不为空，并且 average(A) == average(B) 。

如果可以完成则返回true ， 否则返回 false  。

注意：对于数组 arr ,  average(arr) 是 arr 的所有元素的和除以 arr 长度。

示例 1:

```txt

输入: nums = [1,2,3,4,5,6,7,8]

输出: true

解释: 我们可以将数组分割为 [1,4,5,8] 和 [2,3,6,7], 他们的平均值都是4.5。

```

示例 2:

```txt

输入: nums = [3,1]

输出: false

```

提示:

• 1 <= nums.length <= 30

• 0 <= nums[i] <= 10^4

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 仅由小写英文字母组成。