列表

详情

1981. 最小化目标值与所选元素的差

给你一个大小为 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 。

 

提示：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: int minimizeTheDifference(vector<vector<int>>& mat, int target) { } };

java 解法, 执行用时: 126 ms, 内存消耗: 42.3 MB, 提交时间: 2023-10-10 23:36:22 

class Solution {
    public int minimizeTheDifference(int[][] mat, int target) {
        int m = mat.length, n = mat[0].length;
        boolean[][] f = new boolean[m + 1][target + 1];
        f[0][0] = true;
        int inf = 100000;
        int ans = inf, large = inf;
        for (int i = 1; i <= m; i++) {
            int next_large = inf;
            for (int j = 0; j < n; j++) {
                for (int k = 0; k <= target; k++) {
                    if (f[i - 1][k]) {
                        if (k + mat[i - 1][j] > target)
                            next_large = Math.min(next_large, k + mat[i - 1][j]);
                        else
                            f[i][k + mat[i - 1][j]] = true;

                        if (i == m)
                            ans = Math.min(ans, Math.abs(k + mat[i - 1][j] - target));
                    }
                }
                //这一步乃是这种方法的精髓所在
                next_large = Math.min(next_large, large + mat[i - 1][j]);
            }
            large = next_large;
        }
        return Math.min(ans, Math.abs(large - target));
    }
}

python3 解法, 执行用时: 2172 ms, 内存消耗: 16.5 MB, 提交时间: 2023-10-10 23:35:56 

class Solution:
    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:
        f  = {0}
        for row in mat:
            g = set()
            row.sort()
            for j in f:
                flag = False # False表示还没有出现已经大于等于target的数
                for x in row:
                    if x + j >= target:
                        if flag: break
                        else: flag = True
                    g.add(x + j)
            f = g
        
        return min(abs(x - target) for x in f)

java 解法, 执行用时: 950 ms, 内存消耗: 42.6 MB, 提交时间: 2023-10-10 23:35:40 

class Solution {
    public int minimizeTheDifference(int[][] mat, int target) {
        //由提示可知此数组最多可以得到的最大值为70×70,为了方便设置为5000
        int MAX = 5000;
        int row = mat.length;
        //定义动规方程;dp[i][j]表示第i行是否可以取到值为j
        //转移方程为dp[i][j] = dp[i][j] | dp[i - 1][j - val]; val为当前位置的值
        boolean[][] dp = new boolean[row][MAX];

        //初始化;第一行全部可以到达，初始化为true
        for (int j : mat[0]) {
            dp[0][j] = true;
        }

        for (int i = 1; i < row; i++) {
            for (int val : mat[i]) {
                for (int j = val; j < MAX; j++) {
                    dp[i][j] = dp[i][j] | dp[i - 1][j - val];
                }
            }
        }

        //从最后一行可以取到的值里找绝对差最小
        int res = Integer.MAX_VALUE;
        for (int j = 0; j < MAX; j++) {
            if (dp[row - 1][j]) {
                res = Math.min(res, Math.abs(j - target));
            }
        }

        return res;
    }
}

python3 解法, 执行用时: 2612 ms, 内存消耗: 16.4 MB, 提交时间: 2023-10-10 23:35:25 

class Solution:
    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:
        m, n = len(mat), len(mat[0])
        # 什么都不选时和为 0
        f = {0}
        # 最小的大于等于 target 的和
        large = float("inf")
        for i in range(m):
            g = set()
            next_large = float("inf")
            for x in mat[i]:
                for j in f:
                    if j + x >= target:
                        next_large = min(next_large, j + x)
                    else:
                        g.add(j + x)
                next_large = min(next_large, large + x)
            f = g
            large = next_large
        
        ans = abs(large - target)
        for x in f:
            ans = min(ans, abs(x - target))
        return ans

cpp 解法, 执行用时: 288 ms, 内存消耗: 19 MB, 提交时间: 2023-10-10 23:35:06 

class Solution {
public:
    int minimizeTheDifference(vector<vector<int>>& mat, int target) {
        int m = mat.size(), n = mat[0].size();
        vector<int> f(target, 0);
        // 什么都不选时和为 0
        f[0] = true;
        // 最小的大于等于 target 的和
        int large = INT_MAX;
        for (int i = 0; i < m; ++i) {
            vector<int> g(target);
            int next_large = INT_MAX;
            for (int x: mat[i]) {
                for (int j = 0; j < target; ++j) {
                    if (f[j]) {
                        if (j + x >= target) {
                            next_large = min(next_large, j + x);
                        }
                        else {
                            g[j + x] = true;
                        }
                    }
                }
                if (large != INT_MAX) {
                    next_large = min(next_large, large + x);
                }
            }
            f = move(g);
            large = next_large;
        }

        int ans = abs(large - target);
        for (int i = target - 1; i >= 0; --i) {
            if (f[i]) {
                ans = min(ans, target - i);
                break;
            }
        }
        return ans;
    }
};

python3 解法, 执行用时: 8804 ms, 内存消耗: 16.6 MB, 提交时间: 2023-10-10 23:34:40 

class Solution:
    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:
        m, n = len(mat), len(mat[0])
        # 什么都不选时和为 0
        f = {0}
        for i in range(m):
            best = max(mat[i])
            g = set()
            for x in mat[i]:
                for j in f:
                    g.add(j + x)
            f = g
        
        ans = float("inf")
        for x in f:
            ans = min(ans, abs(x - target))
        return ans

cpp 解法, 执行用时: 1244 ms, 内存消耗: 29.8 MB, 提交时间: 2023-10-10 23:34:27 

class Solution {
public:
    // f[i][j] 表示在矩阵 mat 的第 0,1,⋯ ,i 行分别选择一个整数，是否存在一种和为 j 的方案
    int minimizeTheDifference(vector<vector<int>>& mat, int target) {
        int m = mat.size(), n = mat[0].size();
        int maxsum = 0;
        // 什么都不选时和为 0
        vector<int> f = {1};
        for (int i = 0; i < m; ++i) {
            int best = *max_element(mat[i].begin(), mat[i].end());
            vector<int> g(maxsum + best + 1);
            for (int x: mat[i]) {
                for (int j = x; j <= maxsum + x; ++j) {
                    g[j] |= f[j - x];
                }
            }
            f = move(g);
            maxsum += best;
        }
        int ans = INT_MAX;
        for (int i = 0; i <= maxsum; ++i) {
            if (f[i] && abs(i - target) < ans) {
                ans = abs(i - target);
            }
        }
        return ans;
    }
};

golang 解法, 执行用时: 40 ms, 内存消耗: 6.5 MB, 提交时间: 2023-10-10 23:33:25 

/**
 * 把每一行看成一组，物品的体积就是元素值，这样就转化成了一个分组背包的模型。
 * 定义 f[i][j] 表示能否从前 i 组物品中选出恰好为 j 的重量，且每组都恰好选一个物品。
 */
func minimizeTheDifference(mat [][]int, target int) int {
	dp := make([]bool, min(len(mat)*70, target*2)+1) // 需要枚举的重量不会超过 target*2
	dp[0] = true
	minSum, maxSum := 0, 0
	for _, row := range mat {
		mi, mx := row[0], row[0]
		for _, v := range row[1:] {
			if v > mx {
				mx = v
			} else if v < mi {
				mi = v
			}
		}
		minSum += mi // 求 minSum 是为了防止 target 过小导致 dp 没有记录到
		maxSum = min(maxSum+mx, target*2) // 前 i 组的最大重量，优化枚举时 j 的初始值
		for j := maxSum; j >= 0; j-- {
			dp[j] = false
			for _, v := range row {
				if v <= j && dp[j-v] {
					dp[j] = true
					break
				}
			}
		}
	}
	ans := abs(minSum - target)
	for i, ok := range dp {
		if ok {
			ans = min(ans, abs(i-target))
		}
	}
	return ans
}

func abs(x int) int { if x < 0 { return -x }; return x }
func min(a, b int) int { if a < b { return a }; return b }

上一题

© 2024 leetcode.cn