当前位置:网站首页>LeetCode 1049. 最后一块石头的重量 II 每日一题
LeetCode 1049. 最后一块石头的重量 II 每日一题
2022-07-07 15:32:00 【@小红花】
问题描述
有一堆石头,用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x <= y。那么粉碎的可能结果如下:
如果 x == y,那么两块石头都会被完全粉碎;
如果 x != y,那么重量为 x 的石头将会完全粉碎,而重量为 y 的石头新重量为 y-x。
最后,最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下,就返回 0。示例 1:
输入:stones = [2,7,4,1,8,1]
输出:1
解释:
组合 2 和 4,得到 2,所以数组转化为 [2,7,1,8,1],
组合 7 和 8,得到 1,所以数组转化为 [2,1,1,1],
组合 2 和 1,得到 1,所以数组转化为 [1,1,1],
组合 1 和 1,得到 0,所以数组转化为 [1],这就是最优值。
示例 2:输入:stones = [31,26,33,21,40]
输出:5
提示:
1 <= stones.length <= 30
1 <= stones[i] <= 100来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/last-stone-weight-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
Java
class Solution {
public int lastStoneWeightII(int[] stones) {
int n = stones.length;
int sum = 0;
for(int i : stones){
sum += i;
}
int[] dp = new int[sum / 2 + 1];
for(int i = 0;i < n;i++){
for(int j = sum / 2;j >= stones[i];j--){
dp[j] = Math.max(dp[j],dp[j - stones[i]] + stones[i]);
}
}
return sum - dp[sum / 2] * 2;
}
}
边栏推荐
- 运算符
- 网关Gateway的介绍与使用
- 面向接口编程
- The latest interview experience of Android manufacturers in 2022, Android view+handler+binder
- 掌握这套精编Android高级面试题解析,oppoAndroid面试题
- 在哪个期货公司开期货户最安全?
- A tour of gRPC:03 - proto序列化/反序列化
- Personal notes of graphics (3)
- Leetcode-136- number that appears only once (solve with XOR)
- 记录Servlet学习时的一次乱码
猜你喜欢
Talk about the realization of authority control and transaction record function of SAP system
"The" "PIP" "entry cannot be recognized as the name of a cmdlet, function, script file, or runnable program."
Master this set of refined Android advanced interview questions analysis, oppoandroid interview questions
掌握这套精编Android高级面试题解析,oppoAndroid面试题
数据中台落地实施之法
预售17.9万,恒驰5能不能火?产品力在线,就看怎么卖
值得一看,面试考点与面试技巧
Tragedy caused by deleting the console statement
1亿单身男女“在线相亲”,撑起130亿IPO
平衡二叉树(AVL)
随机推荐
字节跳动Android金三银四解析,android面试题app
C语言进阶——函数指针
平衡二叉树(AVL)
Pycharm terminal enables virtual environment
Tragedy caused by deleting the console statement
Common training data set formats for target tracking
Asyncio concept and usage
php 自带过滤和转义函数
Master this set of refined Android advanced interview questions analysis, oppoandroid interview questions
ORACLE进阶(六)ORACLE expdp/impdp详解
爬虫(17) - 面试(2) | 爬虫面试题库
Direct dry goods, 100% praise
水平垂直居中 方法 和兼容
DNS 系列(一):为什么更新了 DNS 记录不生效?
【MySql进阶】索引详解(一):索引数据页结构
As an Android Developer programmer, Android advanced interview
Three. JS series (1): API structure diagram-1
Binary search tree (features)
The difference and working principle between compiler and interpreter
01tire+ chain forward star +dfs+ greedy exercise one