井字游戏
难度:
标签:
题目描述
Design an algorithm to figure out if someone has won a game of tic-tac-toe. Input is a string array of size N x N, including characters " ", "X" and "O", where " " represents a empty grid.
The rules of tic-tac-toe are as follows:
- Players place characters into an empty grid(" ") in turn.
- The first player always place character "O", and the second one place "X".
- Players are only allowed to place characters in empty grid. Replacing a character is not allowed.
- If there is any row, column or diagonal filled with N same characters, the game ends. The player who place the last charater wins.
- When there is no empty grid, the game ends.
- If the game ends, players cannot place any character further.
If there is any winner, return the character that the winner used. If there's a draw, return "Draw". If the game doesn't end and there is no winner, return "Pending".
Example 1:
Input: board = ["O X"," XO","X O"] Output: "X"
Example 2:
Input: board = ["OOX","XXO","OXO"] Output: "Draw" Explanation: no player wins and no empty grid left
Example 3:
Input: board = ["OOX","XXO","OX "] Output: "Pending" Explanation: no player wins but there is still a empty grid
Note:
1 <= board.length == board[i].length <= 100- Input follows the rules.
代码结果
运行时间: 26 ms, 内存: 16.0 MB
/*
* 思路：
* 1. 使用Java Stream API来检查每一行、每一列和对角线是否有相同的非空字符
* 2. 检查是否存在空位
* 3. 根据以上检查结果返回获胜者字符、平局或待定
*/
import java.util.stream.*;
public class TicTacToeStream {
public String checkWinner(String[] board) {
int n = board.length;
boolean hasEmpty = Arrays.stream(board).anyMatch(row -> row.contains(" "));
// 检查行和列
for (int i = 0; i < n; i++) {
String row = board[i];
String column = IntStream.range(0, n).mapToObj(j -> String.valueOf(board[j].charAt(i))).collect(Collectors.joining());
if (row.chars().distinct().count() == 1 && row.charAt(0) != ' ') {
return String.valueOf(row.charAt(0));
}
if (column.chars().distinct().count() == 1 && column.charAt(0) != ' ') {
return String.valueOf(column.charAt(0));
}
}
// 检查对角线
String diag1 = IntStream.range(0, n).mapToObj(i -> String.valueOf(board[i].charAt(i))).collect(Collectors.joining());
String diag2 = IntStream.range(0, n).mapToObj(i -> String.valueOf(board[i].charAt(n - 1 - i))).collect(Collectors.joining());
if (diag1.chars().distinct().count() == 1 && diag1.charAt(0) != ' ') {
return String.valueOf(diag1.charAt(0));
}
if (diag2.chars().distinct().count() == 1 && diag2.charAt(0) != ' ') {
return String.valueOf(diag2.charAt(0));
}
// 检查是否有空位
return hasEmpty ? "Pending" : "Draw";
}
}解释
方法:
题解通过定义一个辅助函数 check(c) 来检查字符 c ('X' 或 'O') 是否在任何行、列或对角线上连续出现 N 次。首先，检查每一行和每一列是否存在连续的相同字符。其次，检查两个对角线是否有连续的相同字符。如果字符 'X' 或 'O' 符合上述任一条件，则返回相应的字符表示该玩家获胜。如果棋盘上还有空位（' '），则返回 'Pending' 表示游戏尚未结束。如果棋盘已满且无人获胜，返回 'Draw' 表示平局。
时间复杂度:
O(N^2)
空间复杂度:
O(1)
代码细节讲解
🦆
在井字游戏的算法中，如何确保在多轮检查中效率最优化，特别是在较大的棋盘上？
▷🦆
题解中提到，如果棋盘仍有空位则返回 'Pending'，但如何在代码中快速地判断棋盘是否还有未填充的空位？
▷🦆
函数 `check(c)` 在检查对角线时使用的逻辑是什么？此逻辑是否能够准确地处理棋盘边角的特殊情况？
▷