leetcode
leetcode 1201 ~ 1250
找出井字棋的获胜者

找出井字棋的获胜者

难度:

标签:

题目描述

代码结果

运行时间: 15 ms, 内存: 16.0 MB


/*
 * 思路:
 * 1. 创建一个3x3的字符数组代表棋盘,并初始化为空格。
 * 2. 使用流操作遍历输入的moves数组,根据步数的奇偶性判断是玩家A('X')还是玩家B('O'),并在相应位置放置棋子。
 * 3. 在每次放置棋子后,检查当前棋手是否胜利(检查行、列、对角线)。
 * 4. 如果所有位置都被填满且没有胜利者,则返回平局'Draw'。
 * 5. 如果棋盘未填满且无胜者,则返回'Pending'。
 */

import java.util.Arrays;
import java.util.stream.IntStream;

public class TicTacToeStream {
    public String tictactoe(int[][] moves) {
        char[][] board = new char[3][3];
        for (char[] row : board) {
            Arrays.fill(row, ' ');
        }
        IntStream.range(0, moves.length).forEach(i -> {
            int row = moves[i][0];
            int col = moves[i][1];
            board[row][col] = (i % 2 == 0) ? 'X' : 'O';
        });
        for (int i = 0; i < moves.length; i++) {
            if (checkWinner(board, moves[i][0], moves[i][1])) {
                return (i % 2 == 0) ? "A" : "B";
            }
        }
        return (moves.length == 9) ? "Draw" : "Pending";
    }

    private boolean checkWinner(char[][] board, int row, int col) {
        char player = board[row][col];
        boolean winRow = IntStream.range(0, 3).allMatch(i -> board[row][i] == player);
        boolean winCol = IntStream.range(0, 3).allMatch(i -> board[i][col] == player);
        boolean winDiag1 = IntStream.range(0, 3).allMatch(i -> board[i][i] == player);
        boolean winDiag2 = IntStream.range(0, 3).allMatch(i -> board[i][2 - i] == player);
        return winRow || winCol || winDiag1 || winDiag2;
    }
}

解释

方法:

该题解的思路是分别记录玩家A和玩家B的棋子位置,然后判断行、列、对角线上是否有连续的三个相同棋子。具体步骤如下: 1. 遍历 moves 数组,根据索引的奇偶性分别记录玩家A和玩家B的棋子位置,并计算对角线上的差值和和值。 2. 判断玩家A的行、列、对角线上是否有连续的三个棋子,如果有则返回 'A'。 3. 判断玩家B的行、列、对角线上是否有连续的三个棋子,如果有则返回 'B'。 4. 如果棋盘已满(即棋子总数为9),则返回 'Draw'。 5. 否则,返回 'Pending',表示游戏尚未结束。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
为什么在判断玩家A和玩家B是否获胜时,只检查了行和列的计数是否为3,而没有检查对角线的计数?
实际上,对角线的检查也是在代码中进行的,但是它是通过变量 `a` 和 `b`(对于玩家A)、`c` 和 `d`(对于玩家B)来实现的。这些变量存储了对角线上棋子的特定属性(差值和和值),这样可以通过检查这些值的计数来判断对角线上是否有三个相同的棋子。因此,虽然看起来只检查了行和列的计数,实际上对角线的检查也被相应地处理了。
🦆
在代码中,`a` 和 `b` 列表分别用于存储什么数据,它们是如何帮助判断玩家A是否在对角线上赢得游戏的?
`a` 列表存储的是玩家A在主对角线上棋子的行索引与列索引的差值。如果在主对角线上有三个棋子,则这些差值都会是0(例如位置(0,0), (1,1), (2,2)的差值都是0)。`b` 列表存储的是玩家A在副对角线上棋子的行索引与列索引的和值。如果在副对角线上有三个棋子,则这些和值都会是2(例如位置(0,2), (1,1), (2,0)的和值都是2)。检查这些列表的相应值的计数是否为3,可以确定是否在对角线上获胜。
🦆
为什么在判断对角线胜利条件时,只检查了 `a.count(0) == 3` 和 `b.count(2) == 3`,这种方法是否能准确判断所有对角线获胜的情况?
检查 `a.count(0) == 3` 确定所有在主对角线上的棋子的位置,因为主对角线上的位置其行索引与列索引之差总是0。同样,检查 `b.count(2) == 3` 确定所有在副对角线上的棋子的位置,因为副对角线上的位置其行索引与列索引之和总是2。这种方法能准确判断两条对角线上的获胜情况,因为棋盘的大小固定,只有这两条对角线可能满足获胜条件。
🦆
在判断平局的逻辑中,为什么要使用 `(len(Amovesx) + len(Bmovesx)) == 9` 来判断棋盘是否已满,是否有更直接的方法来判断棋盘的状态?
使用 `(len(Amovesx) + len(Bmovesx)) == 9` 来判断棋盘是否已满是基于每个玩家的移动次数之和应等于棋盘的格子数(3x3=9)。这是一种有效的方法,因为每次玩家落子都会导致这两个列表的长度增加,直到所有格子都被填满。更直接的方法可能包括直接检查 `moves` 列表的长度是否为9,因为 `moves` 列表的长度直接反映了总的落子次数。

相关问题