[Swift]LeetCode1140. 石子游戏 II | Stone Game II - Swift 教程-OStack程序员社区-中国程序员成长平台

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

[Swift]LeetCode1140. 石子游戏 II | Stone Game II

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Alex and Lee continue their games with piles of stones. There are a number of piles arranged in a row, and each pile has a positive integer number of stones piles[i]. The objective of the game is to end with the most stones.

Alex and Lee take turns, with Alex starting first. Initially, M = 1.

On each player's turn, that player can take all the stones in the first X remaining piles, where 1 <= X <= 2M. Then, we set M = max(M, X).

The game continues until all the stones have been taken.

Assuming Alex and Lee play optimally, return the maximum number of stones Alex can get.

Example 1:

Input: piles = [2,7,9,4,4]
Output: 10
Explanation:  If Alex takes one pile at the beginning, Lee takes two piles, then Alex takes 2 piles again. Alex can get 2 + 4 + 4 = 10 piles in total. If Alex takes two piles at the beginning, then Lee can take all three piles left. In this case, Alex get 2 + 7 = 9 piles in total. So we return 10 since it's larger.

Constraints:

1 <= piles.length <= 100
1 <= piles[i] <= 10 ^ 4

亚历克斯和李继续他们的石子游戏。许多堆石子排成一行，每堆都有正整数颗石子 piles[i]。游戏以谁手中的石子最多来决出胜负。

亚历克斯和李轮流进行，亚历克斯先开始。最初，M = 1。

在每个玩家的回合中，该玩家可以拿走剩下的前 X 堆的所有石子，其中 1 <= X <= 2M。然后，令 M = max(M, X)。

游戏一直持续到所有石子都被拿走。

假设亚历克斯和李都发挥出最佳水平，返回亚历克斯可以得到的最大数量的石头。

示例：

输入：piles = [2,7,9,4,4]
输出：10
解释：
如果亚历克斯在开始时拿走一堆石子，李拿走两堆，接着亚历克斯也拿走两堆。在这种情况下，亚历克斯可以拿到 2 + 4 + 4 = 10 颗石子。 
如果亚历克斯在开始时拿走两堆石子，那么李就可以拿走剩下全部三堆石子。在这种情况下，亚历克斯可以拿到 2 + 7 = 9 颗石子。
所以我们返回更大的 10。

提示：

1 <= piles.length <= 100
1 <= piles[i] <= 10 ^ 4

8ms

 1 class Solution {
 2     private var sums = [Int](repeating: 0, count: 101)
 3     private var hash = [[Int]](repeating: [Int](repeating: 0, count: 101), count: 101)
 4     func stoneGameII(_ piles: [Int]) -> Int {
 5         let N = piles.count
 6         if N == 0 { return 0 }
 7         sums[N-1] = piles[N-1]
 8         for i in stride(from: N-2, to: -1, by: -1) {
 9             sums[i] = sums[i+1] + piles[i]
10         }
11        
12         return helper(piles, 0, 1)
13     }
14 
15 
16     private func helper(_ a: [Int], _ i: Int, _ M: Int) -> Int {
17         if i == a.count { return 0 }
18         if 2*M >= a.count - i { return sums[i] }
19         if hash[i][M] != 0 { return hash[i][M] }
20 
21         var minv = Int.max //the min value the next player can get
22         for x in 1..<2*M+1 {
23             minv = min(minv, helper(a, i+x, max(M,x)))
24         }
25         hash[i][M] = sums[i] - minv  //max stones = all the left stones - the min stones next player can get
26         return hash[i][M]
27     }
28 }

Runtime: 16 ms

Memory Usage: 21 MB

 1 class Solution {
 2     func stoneGameII(_ piles: [Int]) -> Int {
 3         var n:Int = piles.count
 4         var sums:[Int] = [Int](repeating:0,count:n + 1)
 5         for i in stride(from:n - 1,through:0,by:-1)
 6         {
 7             sums[i] = piles[i] + sums[i+1]
 8         }
 9         var dp:[[Int]] = [[Int]](repeating:[Int](repeating:0,count:n + 1),count:n)
10         for i in stride(from:n - 1,through:0,by:-1)
11         {
12             for j in 1...n
13             {
14                 if 2 * j >= n - i
15                 {
16                     dp[i][j]=sums[i]
17                 }
18                 else
19                 {
20                     for k in 1...(2*j)
21                     {
22                         let nextM:Int = max(k,j)
23                         dp[i][j] = max(dp[i][j],sums[i] - dp[i+k][nextM])
24                     }
25                 }
26             }
27         }
28         return dp[0][1]
29     }
30 }

20ms

 1 class Solution {
 2     func stoneGameII(_ piles: [Int]) -> Int {
 3         guard !piles.isEmpty else { return 0 }
 4         
 5         var hash = [Key:Int]()
 6         var sums = Array(repeating: 0, count: piles.count)
 7         sums[0] = piles[0]
 8         for i in 1..<piles.count {
 9             sums[i] = sums[i-1] + piles[i]
10         }
11         return _stoneGameII(sums, 0, 1, &hash)
12     }
13     
14     func _stoneGameII(_ sums: [Int], _ i: Int, _ m: Int, _ hash: inout [Key:Int]) -> Int {
15         if i >= sums.count { return 0 }
16         
17         let key = Key(i,m)
18         if let result = hash[key] { return result }
19         
20         var result = Int.max
21         for x in (i..<min(sums.count, (i + m * 2))) {
22             result = min(result, _stoneGameII(sums, x+1, max(m, x - i + 1), &hash))
23         }
24         
25         result = sums[sums.count - 1] - (i == 0 ? 0 : sums[i - 1]) - result
26         
27         hash[key] = result
28         return result
29     }
30 }
31 
32 struct Key: Hashable {
33     let i: Int
34     let m: Int
35     
36     init(_ i: Int, _ m: Int) {
37         self.i = i
38         self.m = m
39     }
40 }

40ms

 1 class Solution {
 2     var m = [[Int]]()
 3     func stoneGameII(_ piles: [Int]) -> Int {
 4         var sum = piles.reduce(0){$0 + $1}
 5         m = [[Int]](repeating:[Int](repeating: Int.min, count: 2 * piles.count), count: piles.count)
 6         let diff = dfsHelper(piles, 0, 1)
 7         return (sum - diff) / 2 + diff
 8     }
 9     
10     fileprivate func dfsHelper(_ piles:[Int], _ idx:Int, _ M:Int) -> Int {
11         
12         
13         if idx >= piles.count {
14             return 0
15         }
16         if m[idx][M] > 0 { return m[idx][M] } 
17     
18         var sum = 0
19         for i in idx...min(idx + 2 * M - 1, piles.count - 1) {
20             sum += piles[i]
21             m[idx][M] = max(m[idx][M], sum - dfsHelper(piles, i+1, max(M, (i - idx)+1)))
22         }
23         return m[idx][M]
24     }
25 }

192ms

 1 class Solution {
 2     func stoneGameII(_ piles: [Int]) -> Int {
 3         guard !piles.isEmpty else { return 0 }
 4         
 5         var hash = [Key:Int]()
 6         return _stoneGameII(piles, 0, 1, true, &hash)
 7     }
 8     
 9     func _stoneGameII(_ piles: [Int], _ i: Int, _ m: Int, _ player: Bool, _ hash: inout [Key:Int]) -> Int {
10         if i >= piles.count { return 0 }
11         
12         let key = Key(i,m,player)
13         if let result = hash[key] { return result }
14         
15         var result = player ? Int.min : Int.max
16         for x in (i..<min(piles.count, (i + m * 2))) {
17             
18             if player { // I am the player, maximize the results
19                 let sum = piles[i...x].reduce(0,+)
20                 result = max(result, sum + _stoneGameII(piles, x+1, max(m, x - i + 1), !player, &hash))    
21             } 
22             else { // I am the opponent, minimize the results
23                 // Note we don't do "sum + _stoneGame" because we are 
24                 // only interested in player's result (number of stones)
25                 result = min(result, _stoneGameII(piles, x+1, max(m, x - i + 1), !player, &hash))    
26             }
27             
28         }
29         
30         hash[key] = result
31         return result
32     }
33 }
34 
35 struct Key: Hashable {
36     let i: Int
37     let m: Int
38     let player: Bool
39     
40     init(_ i: Int, _ m: Int, _ player: Bool) {
41         self.i = i
42         self.m = m
43         self.player = player
44     }
45 }