太平洋网站建设,网站建设的想法,百度咨询电话人工台,汉中最新通知今天文章目录1. 题目2. 解题1. 题目
给你一个大小为 m x n 的整数矩阵 mat 和一个整数 target 。
从矩阵的 每一行 中选择一个整数#xff0c;你的目标是 最小化 所有选中元素之 和 与目标值 target 的 绝对差 。
返回 最小的绝对差 。
a 和 b 两数字的 绝对差 是 a - b 的绝对…
文章目录1. 题目2. 解题1. 题目
给你一个大小为 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.length
n mat[i].length
1 m, n 70
1 mat[i][j] 70
1 target 800来源力扣LeetCode 链接https://leetcode-cn.com/problems/minimize-the-difference-between-target-and-chosen-elements 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
class Solution {
public:int minimizeTheDifference(vectorvectorint mat, int target) {int m mat.size(), n mat[0].size(), diff INT_MAX, limit 4901;vectorint dp(limit, 0);for(int i 0; i n; i)dp[mat[0][i]] 1; // 可以拿 标记为1for(int i 1; i m; i){vectorint temp(limit, 0);for(int v limit-1; v 0; --v){if(dp[v] 0) // 前面状态不存在continue;for(int j 0; j n; j){if(vmat[i][j] limit)temp[vmat[i][j]] 1;}}swap(temp, dp);}for(int i 0; i limit; i){if(dp[i]){diff min(diff, abs(i-target));}}return diff;}
};1732 ms 68.5 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
