資料結構
網路
關係型資料庫管理系統
作業系統
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+ 瀏覽量
廣告