最小化目标值与所选元素的差
难度:
标签:
题目描述
给你一个大小为 m x n 的整数矩阵 mat 和一个整数 target 。
从矩阵的 每一行 中选择一个整数，你的目标是 最小化 所有选中元素之 和 与目标值 target 的 绝对差 。
返回 最小的绝对差 。
a 和 b 两数字的 绝对差 是 a - b 的绝对值。
示例 1：
输入：mat = [[1,2,3],[4,5,6],[7,8,9]], target = 13 输出：0 解释：一种可能的最优选择方案是： - 第一行选出 1 - 第二行选出 5 - 第三行选出 7 所选元素的和是 13 ，等于目标值，所以绝对差是 0 。
示例 2：
输入：mat = [[1],[2],[3]], target = 100 输出：94 解释：唯一一种选择方案是： - 第一行选出 1 - 第二行选出 2 - 第三行选出 3 所选元素的和是 6 ，绝对差是 94 。
示例 3：
输入：mat = [[1,2,9,8,7]], target = 6 输出：1 解释：最优的选择方案是选出第一行的 7 。 绝对差是 1 。
提示：
m == mat.lengthn == mat[i].length1 <= m, n <= 701 <= mat[i][j] <= 701 <= target <= 800
代码结果
运行时间: 53 ms, 内存: 16.3 MB
/*
* 思路：
* 使用 Java Stream API 实现类似于上述的动态规划方案。
* 每一行都用 Stream 的 map 和 flatMap 方法来更新可能的和。
*/
import java.util.*;
import java.util.stream.Collectors;
public class Solution {
public int minimizeTheDifference(int[][] mat, int target) {
Set<Integer> possibleSums = new HashSet<>();
possibleSums.add(0);
for (int[] row : mat) {
possibleSums = possibleSums.stream()
.flatMap(sum -> Arrays.stream(row).mapToObj(val -> sum + val))
.collect(Collectors.toSet());
}
return possibleSums.stream()
.mapToInt(sum -> Math.abs(sum - target))
.min()
.orElse(Integer.MAX_VALUE);
}
}
解释
方法:
题解采用了动态规划的思想，结合状态压缩的技术来解决问题。核心思路是使用位运算的技巧，通过整数的每一位来表示某个和是否可达。具体步骤如下：
1. 初始状态`bits`设为1，表示只有和为0是可达的。
2. 遍历矩阵的每一行，对于每个元素，更新可达和的状态。这是通过将`bits`左移元素值位，然后与原`bits`做或运算实现的。
3. 最后，在所有可能的和中，找到最接近target的值，计算其与target的差值。
时间复杂度:
O(m * n + 4900)
空间复杂度:
O(1)
代码细节讲解
🦆
在动态规划中，为什么使用位运算来表示和的可达状态而不是使用常规的数组或哈希表？
▷🦆
如何保证在将`bits`左移元素值位后与原`bits`做或运算确实可以正确地更新和的可达状态？
▷🦆
题解中提到最大可能和为4900，这个数字是如何得出的？它是否适用于所有输入矩阵的规模？
▷🦆
为什么在寻找最小绝对差时要分别从target向上和向下寻找可达的和？直接寻找最接近target的可达和不可以吗？
▷