|
| 1 | +## 题目地址(3599. 划分数组以最小化异或值) |
| 2 | + |
| 3 | +https://leetcode.cn/problems/partition-array-to-minimize-xor/ |
| 4 | + |
| 5 | +## 题目描述 |
| 6 | + |
| 7 | +给定一个整数数组 `nums` 和一个整数 `k`,你需要将数组划分为 **恰好** `k` 个非空子数组,使得所有子数组的异或值中的 **最大值** 最小化。返回这个最小的最大异或值。 |
| 8 | + |
| 9 | +### 示例 1: |
| 10 | + |
| 11 | +``` |
| 12 | +输入:nums = [0, 1, 2], k = 2 |
| 13 | +输出:2 |
| 14 | +解释:可以将数组划分为 [0, 1] 和 [2],异或值分别为 1 和 2,最大值为 2。 |
| 15 | +``` |
| 16 | + |
| 17 | +### 示例 2: |
| 18 | + |
| 19 | +``` |
| 20 | +输入:nums = [1, 2, 3, 4], k = 3 |
| 21 | +输出:4 |
| 22 | +解释:可以将数组划分为 [1, 2], [3], [4],异或值分别为 3, 3, 4,最大值为 4。 |
| 23 | +``` |
| 24 | + |
| 25 | +### 约束: |
| 26 | + |
| 27 | +- \(1 \leq k \leq nums.length \leq 1000\) |
| 28 | +- \(0 \leq nums[i] < 2^{30}\) |
| 29 | + |
| 30 | +## 思路 |
| 31 | + |
| 32 | +首先,看数据规模,不难想到解法应该是需要多重循环的那种。 |
| 33 | + |
| 34 | +其次,题目是极小化最大值,先考虑能不能用二分。(极大化最小值也是一样的)。想了一下,似乎没好的思路。 |
| 35 | + |
| 36 | +然后,接着想,对于每一个元素 nums[i] 是不是要么合并到前面的子数组,要么单独开辟一个新的子数组。这好像是典型的"选择"问题,应该用动态规划。想到这里就差不多解决了一大半困难了。 |
| 37 | + |
| 38 | +我们可以通过两种方法解决这个问题: |
| 39 | + |
| 40 | +- **方法一:记忆化递归(Top-Down DP)** |
| 41 | + |
| 42 | + - **状态定义**:定义 `dp(i, k)` 表示从第 `i` 个元素开始,将剩余部分划分为 `k` 个子数组时,能得到的最小最大异或值。 |
| 43 | + - **递推关系**:对于每个起始位置 `i`,我们可以尝试不同的结束位置 `j`,计算子数组 `[i, j]` 的异或值,然后递归处理剩余部分。最终结果是所有可能划分中,最大异或值的最小值。 |
| 44 | + - **剪枝优化**:如果当前计算的异或值已经大于当前最优解,则无需继续递归。 |
| 45 | + - **缺点**:由于递归深度和重复计算较多,在大数据规模下可能会超时。 |
| 46 | + |
| 47 | +- **方法二:动态规划(Bottom-Up DP)** |
| 48 | + - **状态定义**:定义 `dp[i][j]` 表示从第 `i` 个元素开始,划分为 `j` 个子数组时,能得到的最小最大异或值。 |
| 49 | + - **递推关系**:从后向前遍历数组,对于每个位置 `i` 和剩余划分数 `j`,枚举子数组的结束位置,计算异或值并更新最优解。 |
| 50 | + - **初始化**:`dp[n][0] = 0`(没有元素时划分为 0 个子数组,结果为 0),其他情况初始化为无穷大。 |
| 51 | + - **优点**:避免了递归的开销,时间复杂度更优。 |
| 52 | + |
| 53 | +两种方法的核心都是通过动态规划找到最优划分方案,区别在于递归和迭代的实现方式。以及如果用迭代对于剪枝的优化效果会更明显。 |
| 54 | + |
| 55 | +实际操作的过程,不熟悉的同学可以先递归,对于无法通过的题目可以尝试修改为动态规划。等熟练后建议大家数据规模不大递归即可,数据规模稍微有点大,直接动态规划。 |
| 56 | + |
| 57 | +## 解法 |
| 58 | + |
| 59 | +### 方法一:记忆化递归 |
| 60 | + |
| 61 | +我们使用带记忆化的自顶向下方法来高效计算结果。 |
| 62 | + |
| 63 | +```python |
| 64 | +from functools import cache |
| 65 | +from math import inf |
| 66 | + |
| 67 | +class Solution: |
| 68 | + def minXor(self, nums: List[int], k: int) -> int: |
| 69 | + @cache |
| 70 | + def dp(i: int, k: int) -> int: |
| 71 | + if i == len(nums): |
| 72 | + return 0 if k == 0 else inf |
| 73 | + ans = inf |
| 74 | + xor = 0 |
| 75 | + for j in range(i, len(nums)): |
| 76 | + xor ^= nums[j] |
| 77 | + if xor >= ans: continue # 剪枝 |
| 78 | + ans = min(ans, max(xor, dp(j + 1, k - 1))) |
| 79 | + return ans |
| 80 | + |
| 81 | + return dp(0, k) |
| 82 | +``` |
| 83 | + |
| 84 | +#### 复杂度: |
| 85 | + |
| 86 | +- **时间复杂度**:\(O(n^2 \cdot k)\),其中 \(n\) 是 `nums` 的长度。每个状态 `(i, k)` 需要 \(O(n)\) 时间计算,共有 \(O(n \cdot k)\) 个状态。 |
| 87 | +- **空间复杂度**:\(O(n \cdot k)\),用于记忆化缓存。 |
| 88 | + |
| 89 | +### 方法二:动态规划 |
| 90 | + |
| 91 | +自底向上的动态规划方法通过迭代构建解,避免了递归开销。 |
| 92 | + |
| 93 | +```python |
| 94 | +from math import inf |
| 95 | + |
| 96 | +class Solution: |
| 97 | + def minXor(self, nums: List[int], k: int) -> int: |
| 98 | + n = len(nums) |
| 99 | + dp = [[inf] * (k + 1) for _ in range(n + 1)] |
| 100 | + dp[n][0] = 0 |
| 101 | + |
| 102 | + for i in range(n - 1, -1, -1): |
| 103 | + for remaining_k in range(1, k + 1): |
| 104 | + xor = 0 |
| 105 | + ans = inf |
| 106 | + for j in range(i, n): |
| 107 | + xor ^= nums[j] |
| 108 | + if xor >= ans: continue # 剪枝 |
| 109 | + ans = min(ans, max(xor, dp[j + 1][remaining_k - 1])) |
| 110 | + dp[i][remaining_k] = ans |
| 111 | + |
| 112 | + return dp[0][k] |
| 113 | +``` |
| 114 | + |
| 115 | +#### 复杂度: |
| 116 | + |
| 117 | +- **时间复杂度**:\(O(n^2 \cdot k)\),由于三重循环。 |
| 118 | +- **空间复杂度**:\(O(n \cdot k)\),用于 DP 表。 |
0 commit comments