leetcode
leetcode 701 ~ 750
有效的井字游戏

有效的井字游戏

难度:

标签:

题目描述

给你一个字符串数组 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?这样会不会漏掉某些情况?
在代码中使用elif而不是if来检查列的胜利情况是一个错误,因为这样排除了某一行和某一列可能同时获胜的情况。如果某一行和某一列在同一轮循环中都符合获胜条件,使用elif就会导致该列的胜利情况被忽略,只计算行的胜利。这是一个潜在的bug,应该将elif改为if以确保行和列的胜利都能被正确统计。
🦆
给定代码中,如果'X'或'O'在对角线上获胜,但同时在行或列中也形成了连线,这会如何影响胜利次数的统计?
如果'X'或'O'在对角线上获胜,同时在行或列中也形成了连线,这将导致胜利次数被重复计算。例如,如果一个'X'在第一行和主对角线上同时形成了连线,这将使'X'的胜利次数增加两次。这种情况在代码中没有被特别处理,因此可能导致对游戏状态的错误判断。
🦆
为什么当'X'的胜利次数大于0时,需要'X'的数量恰好比'O'多1个,而'O'胜利时,'X'和'O'的数量必须相等?这背后的逻辑是什么?
这个规则反映了井字游戏的基本规则:玩家轮流放置'X'和'O'。游戏开始时,'X'先行,因此每当'X'获胜时,由于'X'总是先行,'X'的数量必须比'O'多1。相对地,如果'O'获胜,因为'O'是第二个行动,此时'X'和'O'的数量必须相等,说明'O'在其最后一次行动中获胜,而在此之前'X'和'O'的数量是平衡的。这些规则确保了游戏的正常轮换和公平性。

相关问题

设计井字棋

设计井字棋