Nim 游戏 II

1908. Nim 游戏 II

Alice 和 Bob 交替进行一个游戏，由 Alice 先手。

在游戏中，共有 n 堆石头。在每个玩家的回合中，玩家需要选择任一非空石头堆，从中移除任意非零数量的石头。如果不能移除任意的石头，就输掉游戏，同时另一人获胜。

给定一个整数数组 piles ，piles[i] 为第 i 堆石头的数量，如果 Alice 能获胜返回 true ，反之返回 false 。

Alice 和 Bob 都会采取 最优策略 。

示例 1：

输入：piles = [1]
输出：true
解释：只有一种可能的情况：
- 第一回合，Alice 移除了第 1 堆中 1 块石头。piles = [0]。
- 第二回合，Bob 没有任何石头可以移除。Alice 获胜。

示例 2：

输入：piles = [1,1]
输出：false
解释：可以证明，Bob一定能获胜。一种可能的情况：
- 第一回合，Alice 移除了第 1 堆中 1 块石头。 piles = [0,1]。
- 第二回合，Bob 移除了第 2 堆中 1 块石头。 piles = [0,0]。
- 第三回合，Alice 没有任何石头可以移除。Bob 获胜。

示例 3：

输入：piles = [1,2,3]
输出：false
解释：可以证明，Bob一定能获胜。一种可能的情况：
- 第一回合，Alice 移除了第 3 堆中 3 块石头。 piles = [1,2,0]。
- 第二回合，Bob 移除了第 2 堆中 1 块石头。 piles = [1,1,0]。
- 第三回合，Alice 移除了第 1 堆中 1 块石头。piles = [0,1,0]。
- 第四回合，Bob 移除了第 2 堆中 1 块石头。 piles = [0,0,0]。
- 第三回合，Alice 没有任何石头可以移除。Bob 获胜。

提示：

n == piles.length
1 <= n <= 7
1 <= piles[i] <= 7

进阶：你能想出一个 线性时间 的解决方案吗？虽然这一答案可能超出了面试所需的范围，但了解它可能会很有趣。

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: bool nimGame(vector<int>& piles) { } };

golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-10-22 10:05:57

func nimGame(piles []int) bool {
    ans := 0
    for _, pile := range piles {
        ans ^= pile
    }
    return ans != 0
}

cpp 解法, 执行用时: 4 ms, 内存消耗: 7.5 MB, 提交时间: 2023-10-22 10:05:29

class Solution {
public:
    bool nimGame(vector<int>& piles) {
        return accumulate(begin(piles), end(piles), int(), bit_xor());
    }
};

python3 解法, 执行用时: 36 ms, 内存消耗: 16 MB, 提交时间: 2023-10-22 10:05:09

class Solution:
    def nimGame(self, piles: List[int]) -> bool:
        return reduce(xor, piles) != 0

rust 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2023-10-22 10:04:36

impl Solution {
    pub fn nim_game(piles: Vec<i32>) -> bool {
        let mut ans = 0;
        for pile in piles {
            ans ^= pile;
        }
        ans != 0
    }
}

java 解法, 执行用时: 0 ms, 内存消耗: 38.6 MB, 提交时间: 2023-10-22 10:04:13

class Solution {
    public boolean nimGame(int[] piles) {
        int x = 0;
        for (int num : piles){
            x ^= num;
        }
        return x != 0;
    }
}

javascript 解法, 执行用时: 52 ms, 内存消耗: 40.8 MB, 提交时间: 2023-10-22 10:04:00

/**
 * @param {number[]} piles
 * @return {boolean}
 */
var nimGame = function(piles) {
     let x
     for(let d of piles) {
        x^=d
     }
     return x!=0
};

cpp 解法, 执行用时: 4 ms, 内存消耗: 7.5 MB, 提交时间: 2023-10-22 10:03:37

class Solution {
public:
    bool nimGame(vector<int>& piles) {
        int t = 0;
        for(int p : piles){
            t ^= p;
        }
        return t != 0;
    }
};

上一题

下一题

详情