Posts tagged as “game”

花花酱 LeetCode 375. Guess Number Higher or Lower II

By zxi on March 13, 2020

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I’ll tell you whether the number I picked is higher or lower.

However, when you guess a particular number x, and you guess wrong, you pay $x. You win the game when you guess the number I picked.

Example:

n = 10, I pick 8.

First round:  You guess 5, I tell you that it's higher. You pay $5.
Second round: You guess 7, I tell you that it's higher. You pay $7.
Third round:  You guess 9, I tell you that it's lower. You pay $9.

Game over. 8 is the number I picked.

You end up paying $5 + $7 + $9 = $21.

Given a particular n ≥ 1, find out how much money you need to have to guarantee a win.

Solution: DP

Use dp[l][r] to denote the min money to win the game if the current guessing range is [l, r], to guarantee a win, we need to try all possible numbers in [l, r]. Let say we guess K, we need to pay K and the game might continue if we were wrong. cost will be K + max(dp(l, K-1), dp(K+1, r)), we need max to cover all possible cases. Among all Ks, we picked the cheapest one.

dp[l][r] = min(k + max(dp[l][k – 1], dp[k+1][r]), for l <= k <= r.

Time complexity: O(n^3)
Space complexity: O(n^2)

C++

// Author: Huahua

class Solution {

public:

int getMoneyAmount(int n) {

constexpr int kInf = 1e9;

vector<vector<int>> cache(n + 2, vector<int>(n + 2, kInf));

function<int(int, int)> dp = [&](int l, int r) {

int& ans = cache[l][r];

if (l >= r) return 0;

if (ans != kInf) return ans;

for (int x = l; x <= r; ++x)

ans = min(ans, x + max(dp(l, x - 1), dp(x + 1, r)));

return ans;

};

return dp(1, n);

}

};

Python3

# Author: Huahua

class Solution:

def getMoneyAmount(self, n: int) -> int:

@lru_cache(maxsize=None)

def dp(l, r):

return min([k + max(dp(l, k - 1), dp(k + 1, r))

for k in range(l, r + 1)]) if l < r else 0

return dp(1, n)

花花酱 LeetCode 1275. Find Winner on a Tic Tac Toe Game

By zxi on December 1, 2019

Tic-tac-toe is played by two players A and B on a 3 x 3 grid.

Here are the rules of Tic-Tac-Toe:

Players take turns placing characters into empty squares (” “).
The first player A always places “X” characters, while the second player B always places “O” characters.
“X” and “O” characters are always placed into empty squares, never on filled ones.
The game ends when there are 3 of the same (non-empty) character filling any row, column, or diagonal.
The game also ends if all squares are non-empty.
No more moves can be played if the game is over.

Given an array moves where each element is another array of size 2 corresponding to the row and column of the grid where they mark their respective character in the order in which A and B play.

Return the winner of the game if it exists (A or B), in case the game ends in a draw return “Draw”, if there are still movements to play return “Pending”.

You can assume that moves is valid (It follows the rules of Tic-Tac-Toe), the grid is initially empty and A will play first.

Example 1:

Input: moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
Output: "A"
Explanation: "A" wins, he always plays first.
"X  "    "X  "    "X  "    "X  "    "X  "
"   " -> "   " -> " X " -> " X " -> " X "
"   "    "O  "    "O  "    "OO "    "OOX"

Example 2:

Input: moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]]
Output: "B"
Explanation: "B" wins.
"X  "    "X  "    "XX "    "XXO"    "XXO"    "XXO"
"   " -> " O " -> " O " -> " O " -> "XO " -> "XO " 
"   "    "   "    "   "    "   "    "   "    "O  "

Example 3:

Input: moves = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]]
Output: "Draw"
Explanation: The game ends in a draw since there are no moves to make.
"XXO"
"OOX"
"XOX"

Example 4:

Input: moves = [[0,0],[1,1]]
Output: "Pending"
Explanation: The game has not finished yet.
"X  "
" O "
"   "

Constraints:

1 <= moves.length <= 9
moves[i].length == 2
0 <= moves[i][j] <= 2
There are no repeated elements on moves.
moves follow the rules of tic tac toe.

Solution: Simulation

Time complexity: O(1)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

string tictactoe(vector<vector<int>>& moves) {

vector<vector<string>> b(3, vector<string>(3, "#"));

bool A = true;

for (const auto& move : moves) {

b[move[0]][move[1]] = A ? "A" : "B";

A = !A;

}

for (int i = 0; i < 3; ++i) {

if (b[i][0] == b[i][1] && b[i][2] == b[i][1] && b[i][0] != "#")

return b[i][0];

if (b[0][i] == b[1][i] && b[2][i] == b[1][i] && b[0][i] != "#")

return b[0][i];

}

if (b[0][0] == b[1][1] && b[1][1] == b[2][2] && b[1][1] != "#")

return b[1][1];

if (b[2][0] == b[1][1] && b[1][1] == b[0][2] && b[1][1] != "#")

return b[1][1];

return moves.size() == 9 ? "Draw" : "Pending";

}

};

花花酱 LeetCode 1140. Stone Game II

By zxi on July 27, 2019

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

Solution: Recursion + Memoization

def solve(s, m) = max diff score between two players starting from s for the given M.

cache[s][M] = max{sum(piles[s:s+x]) – solve(s+x, max(x, M)}, 1 <= x <= 2*M, s + x <= n

Time complexity: O(n^3)
Space complexity: O(n^2)

C++

// Author: Huahua, 12 ms / 9.7 MB

class Solution {

public:

int stoneGameII(vector<int>& piles) {

const int n = piles.size();

unordered_map<int, int> cache;

// Maximum diff starting from piles[s] given M.

function<int(int, int)> solve = [&](int s, int M) {

if (s >= n) return 0;

const int key = (s << 8) | M;

if (cache.count(key)) return cache[key];

int best = INT_MIN;

int curr = 0;

for (int x = 1; x <= 2 * M; ++x) {

if (s + x > n) break;

curr += piles[s + x - 1];

best = max(best, curr - solve(s + x, max(x, M)));

}

return cache[key] = best;

};

int total = accumulate(begin(piles), end(piles), 0);

return (total + solve(0, 1)) / 2;

}

};

花花酱 LeetCode 45. Jump Game II

By zxi on April 28, 2019

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

Example:

Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
    Jump 1 step from index 0 to 1, then 3 steps to the last index.

Note:

You can assume that you can always reach the last index.

Solution: Greedy

Jump as far as possible but lazily.

[2, 3, 1, 1, 4]
i    nums[i]   steps   near   far
-      -         0       0     0
0      2         0       0     2
1      3         1       2     4
2      1         1       2     4
3      1         2       4     4
4      4         2       4     8

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua, running time: 12 ms / 10.3 MB

class Solution {

public:

int jump(vector<int>& nums) {

int steps = 0;

int near = 0;

int far = 0;

for (int i = 0; i < nums.size(); ++i) {

if (i > near) {

++steps;

near = far;

}

far = max(far, i + nums[i]);

}

return steps;

}

};

花花酱 LeetCode 877. Stone Game

By zxi on July 28, 2018

Problem

Alex and Lee play a game with piles of stones. There are an even 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. The total number of stones is odd, so there are no ties.

Alex and Lee take turns, with Alex starting first. Each turn, a player takes the entire pile of stones from either the beginning or the end of the row. This continues until there are no more piles left, at which point the person with the most stones wins.

Assuming Alex and Lee play optimally, return True if and only if Alex wins the game.

Example 1:

Input: [5,3,4,5]
Output: true
Explanation: 
Alex starts first, and can only take the first 5 or the last 5.
Say he takes the first 5, so that the row becomes [3, 4, 5].
If Lee takes 3, then the board is [4, 5], and Alex takes 5 to win with 10 points.
If Lee takes the last 5, then the board is [3, 4], and Alex takes 4 to win with 9 points.
This demonstrated that taking the first 5 was a winning move for Alex, so we return true.

Note:

2 <= piles.length <= 500
piles.length is even.
1 <= piles[i] <= 500
sum(piles) is odd.

Solution 1: min-max (TLE)

Time complexity: O(2^n)

Space complexity: O(n)

// Author: Huahua

// Running time: TLE 26/46 passed.

class Solution {

public:

bool stoneGame(vector<int>& piles) {

return score(piles, 0, piles.size() - 1) > 0;

}

private:

int score(const vector<int>& piles, int l, int r) {

if (l == r) return piles[l];

return max(piles[l] - score(piles, l + 1, r),

piles[r] - score(piles, l, r - 1));

}

};

Solution 2: min-max + memorization

Time complexity: O(n^2)

Space complexity: O(n^2)

// Author: Huahua

// Running time: 12 ms

class Solution {

public:

bool stoneGame(vector<int>& piles) {

const int n = piles.size();

m_ = vector<vector<int>>(n, vector<int>(n, INT_MIN));

return score(piles, 0, n - 1) > 0;

}

private:

vector<vector<int>> m_;

int score(const vector<int>& piles, int l, int r) {

if (l == r) return piles[l];

if (m_[l][r] == INT_MIN)

m_[l][r] = max(piles[l] - score(piles, l + 1, r),

piles[r] - score(piles, l, r - 1));

return m_[l][r];

}

};

Solution 3: min-max + DP

Time complexity: O(n^2)

Space complexity: O(n^2)

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

bool stoneGame(vector<int>& piles) {

const int n = piles.size();

// dp[i][j] := max(your_stones - op_stones) for piles[i] ~ piles[j]

vector<vector<int>> dp(n, vector<int>(n, 0));

for (int i = 0; i < n; ++i)

dp[i][i] = piles[i];

for (int l = 2; l <= n; ++l)

for (int i = 0; i < n - l + 1; ++i) {

int j = i + l - 1;

dp[i][j] = max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]);

}

return dp[0][n - 1] > 0;

}

};

O(n) Space

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

bool stoneGame(vector<int>& piles) {

const int n = piles.size();

// dp[i] := max(your_stones - op_stones) for piles[i] to piles[i + l - 1]

vector<int> dp(piles);

for (int l = 2; l <= n; ++l)

for (int i = 0; i < n - l + 1; ++i)

dp[i] = max(piles[i] - dp[i + 1], piles[i + l - 1] - dp[i]);

return dp[0] > 0;

}

};

Posts tagged as “game”

花花酱 LeetCode 375. Guess Number Higher or Lower II

Solution: DP

C++

Python3

花花酱 LeetCode 1275. Find Winner on a Tic Tac Toe Game

Solution: Simulation

C++

花花酱 LeetCode 1140. Stone Game II

Solution: Recursion + Memoization

C++

花花酱 LeetCode 45. Jump Game II

Solution: Greedy

C++

花花酱 LeetCode 877. Stone Game

Problem

Solution 1: min-max (TLE)

Solution 2: min-max + memorization

Solution 3: min-max + DP

Related Problems