leetcode
leetcode 301 ~ 350
设计井字棋

设计井字棋

难度:

标签:

题目描述

代码结果

运行时间: 56 ms, 内存: 0.0 MB


/*
 * 设计井字棋
 * 题目思路:
 * 实现一个TicTacToe类,它具备如下功能:
 * 1. TicTacToe(int n) 初始化一个大小为 n 的井字棋棋盘。
 * 2. int move(int row, int col, int player) 表示玩家 player 在棋盘 (row, col) 上落子。
 *    - player = 1 表示玩家 1,player = 2 表示玩家 2。
 *    - 如果玩家 player 获胜,返回 player。如果没有玩家获胜,返回 0。
 */
 
import java.util.stream.IntStream;
 
public class TicTacToe {
    private int[] rows;
    private int[] cols;
    private int diagonal;
    private int antiDiagonal;
    private int n;
 
    public TicTacToe(int n) {
        this.n = n;
        rows = new int[n];
        cols = new int[n];
        diagonal = 0;
        antiDiagonal = 0;
    }
 
    public int move(int row, int col, int player) {
        int toAdd = player == 1 ? 1 : -1;
 
        rows[row] += toAdd;
        cols[col] += toAdd;
 
        if (row == col) {
            diagonal += toAdd;
        }
 
        if (row + col == n - 1) {
            antiDiagonal += toAdd;
        }
 
        if (IntStream.of(rows).anyMatch(x -> Math.abs(x) == n) ||
            IntStream.of(cols).anyMatch(x -> Math.abs(x) == n) ||
            Math.abs(diagonal) == n || Math.abs(antiDiagonal) == n) {
            return player;
        }
 
        return 0;
    }
}

解释

方法:

这个题解使用了一种巧妙的方法来判断井字棋的获胜条件。它维护了三个数组:_row 表示每一行上玩家 1 和玩家 2 分别还需要多少个棋子才能获胜,_col 表示每一列上玩家 1 和玩家 2 分别还需要多少个棋子才能获胜,_diag 表示在两条对角线上玩家 1 和玩家 2 分别还需要多少个棋子才能获胜。每当一个玩家在某个位置放置棋子时,对应的 _row、_col 和 _diag 的计数就会减 1。当其中任何一个计数减为 0 时,就表示该玩家在对应的行、列或对角线上达成了获胜条件。

时间复杂度:

O(1)

空间复杂度:

O(n)

代码细节讲解

🦆
在初始化时,数组_row和_col中的每个元素为何设置为n,这与棋盘大小的关系是什么?
在井字棋游戏中,每行或每列获胜的条件是某一玩家的棋子填满整行或整列。因此,初始化时将_row和_col数组的每个元素设置为棋盘的大小n,表示每行或每列最开始时需要n个同一玩家的棋子才能获胜。这直接反映了棋盘的大小,每行或每列最大的棋子数量就是n。
🦆
如何确保move函数中对数组的访问不会越界,特别是对_diag数组的操作?
在move函数中,通过对输入的row和col的值进行检查确保它们在有效范围内(即0到n-1),从而避免_row和_col数组越界。对于_diag数组,它被设计为只有四个元素,分别对应两条对角线上的胜利条件。对这些元素的访问是基于落子的位置:如果落在主对角线(row == col)或反对角线(row + col == n-1),则分别检查并更新_diag数组中的对应元素。这种方法确保了访问不会越界,因为对数组元素的访问是条件性的,只在落子位置满足对应对角线条件时发生。
🦆
为什么在对对角线的胜利条件检查时,分别设置了四个指标来跟踪两个玩家在两条对角线上的状态,而不是更简化的方法?
设计中分别设置四个指标来跟踪两条对角线上的状态,这是为了能够独立地跟踪每个玩家在每条对角线上的胜利条件。这种设计允许系统即时检测到任一玩家在任一对角线上达到获胜条件,同时也简化了每次落子后的胜利判断逻辑。如果使用更简化的方法,可能需要更复杂的逻辑来区分不同玩家对同一对角线的影响,从而增加了实现的复杂度和出错的可能。
🦆
move函数返回的胜利状态是如何立即确定的,即检测到计数为0就直接返回胜利,这种实现有可能遗漏其他玩家的胜利情况吗?
move函数中,当任一胜利条件的计数减至0时(即某行、列或对角线上玩家的棋子数量填满),函数就会返回该玩家的胜利状态。这是因为每次只有一个玩家可以落子,所以每次落子后只需要检查落子的玩家是否满足胜利条件。这种方法不会遗漏其他玩家的胜利情况,因为在任何玩家获胜时游戏就已经结束,不会再有进一步的落子。

相关问题

有效的井字游戏

给你一个字符串数组 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'' '