Question

1908. Game of Nim

中文文档

Description

Alice and Bob take turns playing a game with Alice starting first.

In this game, there are n piles of stones. On each player's turn, the player should remove any positive number of stones from a non-empty pile of his or her choice. The first player who cannot make a move loses, and the other player wins.

Given an integer array piles, where piles[i] is the number of stones in the ith pile, return true_ if Alice wins, or _false_ if Bob wins_.

Both Alice and Bob play optimally.

 

Example 1:

Input: piles = [1]
Output: true
Explanation: There is only one possible scenario:
- On the first turn, Alice removes one stone from the first pile. piles = [0].
- On the second turn, there are no stones left for Bob to remove. Alice wins.

Example 2:

Input: piles = [1,1]
Output: false
Explanation: It can be proven that Bob will always win. One possible scenario is:
- On the first turn, Alice removes one stone from the first pile. piles = [0,1].
- On the second turn, Bob removes one stone from the second pile. piles = [0,0].
- On the third turn, there are no stones left for Alice to remove. Bob wins.

Example 3:

Input: piles = [1,2,3]
Output: false
Explanation: It can be proven that Bob will always win. One possible scenario is:
- On the first turn, Alice removes three stones from the third pile. piles = [1,2,0].
- On the second turn, Bob removes one stone from the second pile. piles = [1,1,0].
- On the third turn, Alice removes one stone from the first pile. piles = [0,1,0].
- On the fourth turn, Bob removes one stone from the second pile. piles = [0,0,0].
- On the fifth turn, there are no stones left for Alice to remove. Bob wins.

 

Constraints:

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

 

Follow-up: Could you find a linear time solution? Although the linear time solution may be beyond the scope of an interview, it could be interesting to know.

Solutions

Solution 1

class Solution:
  def nimGame(self, piles: List[int]) -> bool:
    @cache
    def dfs(st):
      lst = list(st)
      for i, x in enumerate(lst):
        for j in range(1, x + 1):
          lst[i] -= j
          if not dfs(tuple(lst)):
            return True
          lst[i] += j
      return False

    return dfs(tuple(piles))

class Solution {
  private Map<Integer, Boolean> memo = new HashMap<>();
  private int[] p = new int[8];

  public Solution() {
    p[0] = 1;
    for (int i = 1; i < 8; ++i) {
      p[i] = p[i - 1] * 8;
    }
  }

  public boolean nimGame(int[] piles) {
    return dfs(piles);
  }

  private boolean dfs(int[] piles) {
    int st = f(piles);
    if (memo.containsKey(st)) {
      return memo.get(st);
    }
    for (int i = 0; i < piles.length; ++i) {
      for (int j = 1; j <= piles[i]; ++j) {
        piles[i] -= j;
        if (!dfs(piles)) {
          piles[i] += j;
          memo.put(st, true);
          return true;
        }
        piles[i] += j;
      }
    }
    memo.put(st, false);
    return false;
  }

  private int f(int[] piles) {
    int st = 0;
    for (int i = 0; i < piles.length; ++i) {
      st += piles[i] * p[i];
    }
    return st;
  }
}

class Solution {
public:
  bool nimGame(vector<int>& piles) {
    unordered_map<int, int> memo;
    int p[8] = {1};
    for (int i = 1; i < 8; ++i) {
      p[i] = p[i - 1] * 8;
    }
    auto f = [&](vector<int>& piles) {
      int st = 0;
      for (int i = 0; i < piles.size(); ++i) {
        st += piles[i] * p[i];
      }
      return st;
    };
    function<bool(vector<int>&)> dfs = [&](vector<int>& piles) {
      int st = f(piles);
      if (memo.count(st)) {
        return memo[st];
      }
      for (int i = 0; i < piles.size(); ++i) {
        for (int j = 1; j <= piles[i]; ++j) {
          piles[i] -= j;
          if (!dfs(piles)) {
            piles[i] += j;
            return memo[st] = true;
          }
          piles[i] += j;
        }
      }
      return memo[st] = false;
    };
    return dfs(piles);
  }
};

func nimGame(piles []int) bool {
  memo := map[int]bool{}
  p := make([]int, 8)
  p[0] = 1
  for i := 1; i < 8; i++ {
    p[i] = p[i-1] * 8
  }
  f := func(piles []int) int {
    st := 0
    for i, x := range piles {
      st += x * p[i]
    }
    return st
  }
  var dfs func(piles []int) bool
  dfs = func(piles []int) bool {
    st := f(piles)
    if v, ok := memo[st]; ok {
      return v
    }
    for i, x := range piles {
      for j := 1; j <= x; j++ {
        piles[i] -= j
        if !dfs(piles) {
          piles[i] += j
          memo[st] = true
          return true
        }
        piles[i] += j
      }
    }
    memo[st] = false
    return false
  }
  return dfs(piles)
}

function nimGame(piles: number[]): boolean {
  const p: number[] = Array(8).fill(1);
  for (let i = 1; i < 8; ++i) {
    p[i] = p[i - 1] * 8;
  }
  const f = (piles: number[]): number => {
    let st = 0;
    for (let i = 0; i < piles.length; ++i) {
      st += piles[i] * p[i];
    }
    return st;
  };
  const memo: Map<number, boolean> = new Map();
  const dfs = (piles: number[]): boolean => {
    const st = f(piles);
    if (memo.has(st)) {
      return memo.get(st)!;
    }
    for (let i = 0; i < piles.length; ++i) {
      for (let j = 1; j <= piles[i]; ++j) {
        piles[i] -= j;
        if (!dfs(piles)) {
          piles[i] += j;
          memo.set(st, true);
          return true;
        }
        piles[i] += j;
      }
    }
    memo.set(st, false);
    return false;
  };
  return dfs(piles);
}