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
廣告