当前位置:网站首页>LeetCode 1981. 最小化目标值与所选元素的差 每日一题
LeetCode 1981. 最小化目标值与所选元素的差 每日一题
2022-07-07 15:32:00 【@小红花】
问题描述
给你一个大小为 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/problems/minimize-the-difference-between-target-and-chosen-elements
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
Java
class Solution {
public int minimizeTheDifference(int[][] mat, int target) {
int n = mat.length;
// 70 * 70
boolean[][] dp = new boolean[n][5000];
//处理第一行
for(int num : mat[0]) dp[0][num] = true;
for(int i = 1;i < n;i++){
//每一行的元素
for(int val : mat[i]){
for(int j = val;j < 5000;j++){
//上一行可选j-val值,当前行就可以选j
dp[i][j] = dp[i][j] || dp[i - 1][j - val];
}
}
}
int ans = Integer.MAX_VALUE;
for(int j = 0;j < 5000;j++){
if(dp[n - 1][j]){
ans = Math.min(ans,Math.abs(j - target));
}
}
return ans;
}
}
边栏推荐
猜你喜欢
最新阿里P7技术体系,妈妈再也不用担心我找工作了
谈谈 SAP 系统的权限管控和事务记录功能的实现
字节跳动Android金三银四解析,android面试题app
【DesignMode】代理模式(proxy pattern)
The team of East China Normal University proposed the systematic molecular implementation of convolutional neural network with DNA regulation circuit
HAVE FUN | “飞船计划”活动最新进展
记录Servlet学习时的一次乱码
Sort out several important Android knowledge and advanced Android development interview questions
最新2022年Android大厂面试经验,安卓View+Handler+Binder
Arduino 控制的双足机器人
随机推荐
C语言进阶——函数指针
LocalStorage和SessionStorage
删除 console 语句引发的惨案
Statistical learning method -- perceptron
The team of East China Normal University proposed the systematic molecular implementation of convolutional neural network with DNA regulation circuit
最新高频Android面试题目分享,带你一起探究Android事件分发机制
What is the difference between IP address and physical address
预测——灰色预测
全网“追杀”钟薛高
【HCSD大咖直播】亲授大厂面试秘诀-简要笔记
LeetCode-SQL第一天
47_ Contour lookup in opencv cv:: findcontours()
dapp丨defi丨nft丨lp单双币流动性挖矿系统开发详细说明及源码
laravel构造函数和中间件执行顺序问题
The latest interview experience of Android manufacturers in 2022, Android view+handler+binder
Three. JS series (2): API structure diagram-2
Three. JS series (3): porting shaders in shadertoy
Record the migration process of a project
SqlServer2014+: 创建表的同时创建索引
谎牛计数(春季每日一题 53)