有效的井字游戏
难度:
标签:
题目描述
给你一个字符串数组 board
表示井字游戏的棋盘。当且仅当在井字游戏过程中,棋盘有可能达到 board
所显示的状态时,才返回 true
。
井字游戏的棋盘是一个 3 x 3
数组,由字符 ' '
,'X'
和 'O'
组成。字符 ' '
代表一个空位。
以下是井字游戏的规则:
- 玩家轮流将字符放入空位(
' '
)中。 - 玩家 1 总是放字符
'X'
,而玩家 2 总是放字符'O'
。 'X'
和'O'
只允许放置在空位中,不允许对已放有字符的位置进行填充。- 当有 3 个相同(且非空)的字符填充任何行、列或对角线时,游戏结束。
- 当所有位置非空时,也算为游戏结束。
- 如果游戏结束,玩家不允许再放置字符。
示例 1:

输入:board = ["O "," "," "] 输出:false 解释:玩家 1 总是放字符 "X" 。
示例 2:

输入:board = ["XOX"," X "," "] 输出:false 解释:玩家应该轮流放字符。
示例 3:

输入:board = ["XOX","O O","XOX"] 输出:true
提示:
board.length == 3
board[i].length == 3
board[i][j]
为'X'
、'O'
或' '
代码结果
运行时间: 23 ms, 内存: 16.1 MB
/*
* 思路:
* 1. 使用流统计X和O的数量,X的数量必须等于O的数量或比O多1。
* 2. 检查X和O是否有三个相同的字符在任一行、列或对角线上。
* 3. 如果X胜利,X的数量必须比O多1;如果O胜利,X的数量必须等于O。
* 4. 确保没有同时存在X和O胜利的情况。
*/
import java.util.stream.IntStream;
public class TicTacToeValidatorStream {
public boolean validTicTacToe(String[] board) {
long xCount = IntStream.range(0, 3).flatMap(i -> board[i].chars()).filter(c -> c == 'X').count();
long oCount = IntStream.range(0, 3).flatMap(i -> board[i].chars()).filter(c -> c == 'O').count();
if (oCount != xCount && oCount != xCount - 1) return false;
if (win(board, 'X') && oCount != xCount - 1) return false;
if (win(board, 'O') && oCount != xCount) return false;
return true;
}
private boolean win(String[] board, char player) {
return IntStream.range(0, 3).anyMatch(i -> board[i].chars().allMatch(c -> c == player) ||
IntStream.range(0, 3).allMatch(j -> board[j].charAt(i) == player)) ||
IntStream.range(0, 3).allMatch(i -> board[i].charAt(i) == player) ||
IntStream.range(0, 3).allMatch(i -> board[i].charAt(2 - i) == player);
}
}
解释
方法:
这个题解的思路是先统计棋盘上 'X' 和 'O' 的个数,然后再统计 'X' 和 'O' 各自形成连线获胜的次数。最后根据题目规则判断棋盘状态是否合法。具体判断标准为:1. 'O' 的个数不能大于 'X' 的个数,且 'X' 的个数最多比 'O' 多1个;2. 'X' 和 'O' 不能同时形成连线获胜;3. 如果 'X' 形成连线获胜,则此时 'X' 的个数必须恰好比 'O' 多1个;4. 如果 'O' 形成连线获胜,则此时 'X' 和 'O' 的个数必须相等。只有同时满足以上条件,才是一个合法的棋盘状态。
时间复杂度:
O(1)
空间复杂度:
O(1)
代码细节讲解
🦆
代码中如何确保在统计'X'和'O'的胜利次数时,不会重复计算例如某行和某列同时包含的胜利情况?
▷🦆
在代码中,为什么在检查每一列的连线胜利时,使用了elif而不是if?这样会不会漏掉某些情况?
▷🦆
给定代码中,如果'X'或'O'在对角线上获胜,但同时在行或列中也形成了连线,这会如何影响胜利次数的统计?
▷🦆
为什么当'X'的胜利次数大于0时,需要'X'的数量恰好比'O'多1个,而'O'胜利时,'X'和'O'的数量必须相等?这背后的逻辑是什么?
▷