数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 实现 最后一块石头重量 II
假设我们有一堆石头，每块石头都有一个正整数重量。在每一轮中，我们选择任意两块石头并将它们一起粉碎。如果石头的重量分别为 x 和 y，其中 x <= y。粉碎的结果将是 -
如果 x = y，则两块石头都被完全摧毁；
如果 x != y，则重量为 x 的石头被完全摧毁，而重量为 y 的石头的新重量为 y-x。
最后，最多剩下 1 块石头。我们必须找到这块石头的最小可能重量（如果没有任何石头剩下，则重量为 0）。
例如，如果输入为 [2,7,4,1,8,1]，则输出将为 1。这是因为如果我们粉碎 (2,4)，则新的数组将为 [2,7,1,8,1]，然后粉碎 (7,8)，新的数组将为 [2,1,1,1]，然后粉碎 (2,1)，数组将为 [1,1,1]，之后粉碎 (1,1)，所以只剩下 1。
为了解决这个问题，我们将遵循以下步骤 -
n := stones 数组的大小，设置 total := 0
对于 i 的范围从 0 到 n – 1
total := total + stones[i]
req := total / 2
创建一个大小为 req + 1 的数组 dp，并用 false 值填充它
dp[0] := true，reach := 0
对于 i 的范围从 0 到 n – 1
对于 j := req，当 j – stones[i] >= 0 时，将 j 减 1
当 (dp[j] 和 dp[j – stones[i]]) 都为 false 时，dp[j] := false，否则为 true
如果 dp[j] 为 true，则 reach := reach 和 j 的最大值
返回 total – (2 * reach)
让我们看看下面的实现以更好地理解 -
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
int n = stones.size();
int total = 0;
for(int i = 0; i < n; i++){
total += stones[i];
}
int req = total / 2;
vector <bool> dp(req + 1, false);
dp[0] = true;
int reach = 0;
for(int i = 0; i < n; i++){
for(int j = req; j - stones[i] >= 0; j--){
dp[j] = dp[j] || dp[j - stones[i]];
if(dp[j]) reach = max(reach, j);
}
}
return total - (2 * reach);
}
};
main(){
vector<int> v = {2,7,4,1,8,1};
Solution ob;
cout << (ob.lastStoneWeightII(v));
}输入
[2,7,4,1,8,1]
输出
1
更新于: 2020-04-30
1K+ 浏览量
广告