[LeetCode] 794. Valid Tic-Tac-Toe State
Given a Tic-Tac-Toe board 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 that 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 three 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
Constraints:
board.length == 3
board[i].length == 3
board[i][j]
is either'X'
,'O'
, or' '
.
有效的井字游戏。
给你一个字符串数组 board 表示井字游戏的棋盘。当且仅当在井字游戏过程中,棋盘有可能达到 board 所显示的状态时,才返回 true 。
井字游戏的棋盘是一个 3 x 3 数组,由字符 ' ','X' 和 'O' 组成。字符 ' ' 代表一个空位。
以下是井字游戏的规则:
玩家轮流将字符放入空位(' ')中。
玩家 1 总是放字符 'X' ,而玩家 2 总是放字符 'O' 。
'X' 和 'O' 只允许放置在空位中,不允许对已放有字符的位置进行填充。
当有 3 个相同(且非空)的字符填充任何行、列或对角线时,游戏结束。
当所有位置非空时,也算为游戏结束。
如果游戏结束,玩家不允许再放置字符。来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/valid-tic-tac-toe-state
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
这道题的题意写的不明确,我这里做一点说明。给的是一个3x3的棋盘,请你判断目前棋盘上的形势是否有可能达到。所谓达到的意思是如果两个玩家之间有一个已经胜出了,则无法达到当前 input 给的这个状态;如果在正常下棋的过程中能达到这种状态,则返回 true。对于井字棋的规则,则比较简单了。两个玩家 X 和 O,只要有一个玩家能在何行、列或对角线时,游戏结束。
这是一道实现题,我们判断的规则是
- 因为 X 先走所以 O 的数量是不可能大于 X 的
- 因为每个人轮流走所以两者差距不会大于 1
- 如果 X 获胜但是 X 的数量小于 O,则不成立
- 如果 O 获胜但是 O 的数量小于 X,则不成立
- 两者不可能同时获胜
照着这几个要求,代码就比较好写了。
时间O(1) - 只需要判断九个空格即可
空间O(1)
Java实现
1 class Solution { 2 public boolean validTicTacToe(String[] board) { 3 char[][] res = new char[3][3]; 4 int x = 0; 5 int o = 0; 6 for (int i = 0; i < 3; i++) { 7 for (int j = 0; j < 3; j++) { 8 char c = board[i].charAt(j); 9 if (c == 'X') { 10 x++; 11 } else if (c == 'O') { 12 o++; 13 } 14 res[i][j] = c; 15 } 16 } 17 boolean a = check(res, 'X'); 18 boolean b = check(res, 'O'); 19 // System.out.println("x is " + x); 20 // System.out.println("o is " + o); 21 // 因为X先走所以O的数量是不可能大于X的 22 // 且因为每个人轮流走所以两者差距不会大于1 23 if (o > x || x - o > 1) { 24 return false; 25 } 26 // 如果x获胜但是X的数量小于O,则不成立 27 if (a && x <= o) { 28 return false; 29 } 30 // 如果O获胜但是O的数量小于X,则不成立 31 if (b && o != x) { 32 return false; 33 } 34 // 两者不可能同时获胜 35 if (a && b) { 36 return false; 37 } 38 return true; 39 } 40 41 private boolean check(char[][] board, char c) { 42 for (int i = 0; i < 3; i++) { 43 if (board[i][0] == c && board[i][1] == c && board[i][2] == c) { 44 return true; 45 } 46 } 47 for (int i = 0; i < 3; i++) { 48 if (board[0][i] == c && board[1][i] == c && board[2][i] == c) { 49 return true; 50 } 51 } 52 if (board[0][0] == c && board[1][1] == c && board[2][2] == c) { 53 return true; 54 } 55 if (board[2][0] == c && board[1][1] == c && board[0][2] == c) { 56 return true; 57 } 58 return false; 59 } 60 }