当前位置:网站首页>LeetCode 1981. Minimize the difference between the target value and the selected element one question per day
LeetCode 1981. Minimize the difference between the target value and the selected element one question per day
2022-07-07 16:59:00 【@Little safflower】
Problem description
Give you a size of m x n The integer matrix of mat And an integer target .
From matrix's Every line Select an integer from the , Your goal is To minimize the Of all selected elements and And target value target Of Absolute difference .
return The smallest absolute difference .
a and b Two digit Absolute difference yes a - b The absolute value of .
Example 1:
Input :mat = [[1,2,3],[4,5,6],[7,8,9]], target = 13
Output :0
explain : One possible optimal option is :
- On the first line, choose 1
- On the second line, choose 5
- On the third line, choose 7
The sum of the selected elements is 13 , Equal to the target value , So the absolute difference is 0 .
Example 2:Input :mat = [[1],[2],[3]], target = 100
Output :94
explain : The only option is :
- On the first line, choose 1
- On the second line, choose 2
- On the third line, choose 3
The sum of the selected elements is 6 , The absolute difference is 94 .
Example 3:Input :mat = [[1,2,9,8,7]], target = 6
Output :1
explain : The best choice is to choose the first line 7 .
The absolute difference is 1 .
Tips :
m == mat.length
n == mat[i].length
1 <= m, n <= 70
1 <= mat[i][j] <= 70
1 <= target <= 800source : Power button (LeetCode)
link :https://leetcode.cn/problems/minimize-the-difference-between-target-and-chosen-elements
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
Java
class Solution {
public int minimizeTheDifference(int[][] mat, int target) {
int n = mat.length;
// 70 * 70
boolean[][] dp = new boolean[n][5000];
// Deal with the first line
for(int num : mat[0]) dp[0][num] = true;
for(int i = 1;i < n;i++){
// The elements of each line
for(int val : mat[i]){
for(int j = val;j < 5000;j++){
// The previous line is optional j-val value , The current line can be selected 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;
}
}
边栏推荐
- QT中自定义控件的创建到封装到工具栏过程(二):自定义控件封装到工具栏
- skimage学习(1)
- Prediction - Grey Prediction
- Three. JS series (1): API structure diagram-1
- LeetCode 1155. 掷骰子的N种方法 每日一题
- 【Seaborn】组合图表:FacetGrid、JointGrid、PairGrid
- Cesium (4): the reason why gltf model is very dark after loading
- QT视频传输
- Seaborn数据可视化
- Pycharm terminal enables virtual environment
猜你喜欢
"The" "PIP" "entry cannot be recognized as the name of a cmdlet, function, script file, or runnable program."
skimage学习(3)——使灰度滤镜适应 RGB 图像、免疫组化染色分离颜色、过滤区域最大值
二叉搜索树(特性篇)
【Seaborn】组合图表:FacetGrid、JointGrid、PairGrid
Horizontal and vertical centering method and compatibility
【DesignMode】外观模式 (facade patterns)
QT中自定义控件的创建到封装到工具栏过程(二):自定义控件封装到工具栏
正在准备面试,分享面经
Personal notes of graphics (3)
Interface oriented programming
随机推荐
掌握这个提升路径,面试资料分享
Spark Tuning (III): persistence reduces secondary queries
Master this set of refined Android advanced interview questions analysis, oppoandroid interview questions
Pycharm IDE下载
DAPP defi NFT LP single and dual currency liquidity mining system development details and source code
如何选择合适的自动化测试工具?
字节跳动高工面试,轻松入门flutter
Pychart ide Download
QT video transmission
Skimage learning (3) -- gamma and log contrast adjustment, histogram equalization, coloring gray images
LeetCode 152. Product maximum subarray daily question
LeetCode 120. 三角形最小路径和 每日一题
1亿单身男女“在线相亲”,撑起130亿IPO
3000 words speak through HTTP cache
QT picture background color pixel processing method
二叉搜索树(基操篇)
AutoLISP series (3): function function 3
[medical segmentation] attention Unet
作为Android开发程序员,android高级面试
C语言进阶——函数指针