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+ 瀏覽量

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告