题目大意：判断一个井字棋的棋盘是否有效。

A Tic-Tac-Toe board is given as a string array board. Return True if and only if it is possible to reach this board position during the course of a valid tic-tac-toe game.

The board is a 3 x 3 array, and consists of characters " ", "X", and "O". The ” ” character represents an empty square.

Here are the rules of Tic-Tac-Toe:

Players take turns placing characters into empty squares (” “).
The first player always places “X” characters, while the second player always places “O” characters.
“X” and “O” characters are always placed into empty squares, never 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.

Example 1:

Input: board = ["O ", " ", " "]

Output: false

Explanation: The first player always plays "X".

Example 2:

Input: board = ["XOX", " X ", " "]

Output: false

Explanation: Players take turns making moves.

Example 3:

Input: board = ["XXX", " ", "OOO"]

Output: false

Example 4:

Input: board = ["XOX", "O O", "XOX"]

Output: true

Note:

board is a length-3 array of strings, where each string board[i] has length 3.
Each board[i][j] is a character in the set {" ", "X", "O"}.

Idea: Verify all rules

C++

class Solution {

public:

bool validTicTacToe(vector<string>& board) {

int x = 0;

int o = 0;

int wins_x = getWins(board, 'X', x);

int wins_o = getWins(board, 'O', o);

return wins_x + wins_o <= 1 && x >= o + wins_x && x <= o + 1 - wins_o;

}

private:

int getWins(const vector<string>& board, char p, int& count) {

vector<string> rows(3);

string diag1, diag2;

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

diag1 += board[i][i];

diag2 += board[i][2 - i];

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

char c = board[i][j];

rows[j] += c;

count += c == p;

}

string win(3, p);

int wins = (diag1 == win) + (diag2 == win);

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

wins += rows[i] == win;

wins += board[i] == win;

}

return wins;

}

};

Problem

Given an array of scores that are non-negative integers. Player 1 picks one of the numbers from either end of the array followed by the player 2 and then player 1 and so on. Each time a player picks a number, that number will not be available for the next player. This continues until all the scores have been chosen. The player with the maximum score wins.

Given an array of scores, predict whether player 1 is the winner. You can assume each player plays to maximize his score.

Example 1:
Input: [1, 5, 2]
Output: False
Explanation: Initially, player 1 can choose between 1 and 2.
If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2).
So, final score of player 1 is 1 + 2 = 3, and player 2 is 5.
Hence, player 1 will never be the winner and you need to return False.

Example 2:
Input: [1, 5, 233, 7]
Output: True
Explanation: Player 1 first chooses 1. Then player 2 have to choose between 5 and 7. No matter which number player 2 choose, player 1 can choose 233.
Finally, player 1 has more score (234) than player 2 (12), so you need to return True representing player1 can win.
Note:
1 <= length of the array <= 20.
Any scores in the given array are non-negative integers and will not exceed 10,000,000.
If the scores of both players are equal, then player 1 is still the winner.

Solution 1: Recursion

Time complexity: O(2^n)

Space complexity: O(n)

// Author: Huahua

// Running time: 67 ms

class Solution {

public:

bool PredictTheWinner(vector<int>& nums) {

return getScore(nums, 0, nums.size() - 1) >= 0;

}

private:

// Max diff (my_score - op_score) of subarray nums[l] ~ nums[r].

int getScore(vector<int>& nums, int l, int r) {

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

return max(nums[l] - getScore(nums, l + 1, r),

nums[r] - getScore(nums, l, r - 1));

}

};

Solution 2: Recursion + Memoization

Time complexity: O(n^2)

Space complexity: O(n)

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

bool PredictTheWinner(vector<int>& nums) {

m_ = vector<vector<int>>(nums.size(), vector<int>(nums.size(), INT_MIN));

return getScore(nums, 0, nums.size() - 1) >= 0;

}

private:

vector<vector<int>> m_;

// Max diff (my_score - op_score) of subarray nums[l] ~ nums[r].

int getScore(vector<int>& nums, int l, int r) {

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

if (m_[l][r] != INT_MIN) return m_[l][r];

m_[l][r] = max(nums[l] - getScore(nums, l + 1, r),

nums[r] - getScore(nums, l, r - 1));

return m_[l][r];

}

};

DP version

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

bool PredictTheWinner(vector<int>& nums) {

const int n = nums.size();

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

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

dp[i][i] = nums[i];

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

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

int j = i + l - 1;

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

}

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

}

};

Posts tagged as “game”

花花酱 LeetCode 794. Valid Tic-Tac-Toe State

花花酱 LeetCode 486. Predict the Winner

Problem

Solution 1: Recursion

Solution 2: Recursion + Memoization

Related Problem