leetcode348. 判定井字棋胜负 好麻烦的代码

请在 n × n 的棋盘上，实现一个判定井字棋（Tic-Tac-Toe）胜负的神器，判断每一次玩家落子后，是否有胜出的玩家。

在这个井字棋游戏中，会有 2 名玩家，他们将轮流在棋盘上放置自己的棋子。

在实现这个判定器的过程中，你可以假设以下这些规则一定成立：

      1. 每一步棋都是在棋盘内的，并且只能被放置在一个空的格子里；

      2. 一旦游戏中有一名玩家胜出的话，游戏将不能再继续；

      3. 一个玩家如果在同一行、同一列或者同一斜对角线上都放置了自己的棋子，那么他便获得胜利。

示例:

给定棋盘边长 n = 3, 玩家 1 的棋子符号是 "X"，玩家 2 的棋子符号是 "O"。

TicTacToe toe = new TicTacToe(3);

toe.move(0, 0, 1); -> 函数返回 0 (此时，暂时没有玩家赢得这场对决)
|X| | |
| | | |    // 玩家 1 在 (0, 0) 落子。
| | | |

toe.move(0, 2, 2); -> 函数返回 0 (暂时没有玩家赢得本场比赛)
|X| |O|
| | | |    // 玩家 2 在 (0, 2) 落子。
| | | |

toe.move(2, 2, 1); -> 函数返回 0 (暂时没有玩家赢得比赛)
|X| |O|
| | | |    // 玩家 1 在 (2, 2) 落子。
| | |X|

toe.move(1, 1, 2); -> 函数返回 0 (暂没有玩家赢得比赛)
|X| |O|
| |O| |    // 玩家 2 在 (1, 1) 落子。
| | |X|

toe.move(2, 0, 1); -> 函数返回 0 (暂无玩家赢得比赛)
|X| |O|
| |O| |    // 玩家 1 在 (2, 0) 落子。
|X| |X|

toe.move(1, 0, 2); -> 函数返回 0 (没有玩家赢得比赛)
|X| |O|
|O|O| |    // 玩家 2 在 (1, 0) 落子.
|X| |X|

toe.move(2, 1, 1); -> 函数返回 1 (此时，玩家 1 赢得了该场比赛)
|X| |O|
|O|O| |    // 玩家 1 在 (2, 1) 落子。
|X|X|X|
 

进阶:
您有没有可能将每一步的 move() 操作优化到比 O(n2) 更快吗?

题意因该是想每一次move都把棋盘全部检查一遍，但是没必要。

进阶的意思：只把新move位置的所在行、列、和两个对角线检查一下即可，时间o(n),空间o(n*n)代码如下。

      class TicTacToe {
      int arr[][];
      /** Initialize your data structure here. */
      public TicTacToe(int n) {
       arr=new int[n][n];
       }
      /** Player {player} makes a move at ({row}, {col}).
       @param row The row of the board.
       @param col The column of the board.
       @param player The player, can be either 1 or 2.
       @return The current winning condition, can be either:
       0: No one wins.
       1: Player 1 wins.
       2: Player 2 wins. */
      public int move(int row, int col, int player) {
       arr[row][col]=player;
      if(checkCol(col,player) || checkRow(row,player) || line1(player) || line2(player)){
      return player;
       }
      return 0;
       }
      public boolean checkRow(int row,int player) {
      int len=arr.length;
      for(int i=0;i<len;i++){
      if(arr[row][i]!=player){
      return false;
       }
       }
      return true;
       }
      public boolean checkCol(int col,int player) {
      int len=arr.length;
      for(int i=0;i<len;i++){
      if(arr[i][col]!=player){
      return false;
       }
       }
      return true;
       }
      public boolean line1(int player){
      int len=arr.length;
      int ans=0;
      for(int i=0;i<len;i++){
      if(arr[i][i]!=player){
      return false;
       }
       }
      return true;
       }
      public boolean line2(int player){
      int len=arr.length;
      int ans=0;
      for(int i=0;i<len;i++){
      if(arr[i][len-i-1]!=player){
      return false;
       }
       }
      return true;
       }
      }
      /**
       * Your TicTacToe object will be instantiated and called as such:
       * TicTacToe obj = new TicTacToe(n);
       * int param_1 = obj.move(row,col,player);
       */
  
 

更好的思路，把每一行每一列，和两个对角线的情况记录下来，玩家1使所在行列对角线-1，玩家1使所在行列对角线+1.

只有某个数等于n或-n时，某个玩家会获胜。

      class TicTacToe {
      int rowArr[];
      int colArr[];
      int line1=0;
      int line2=0;
      /** Initialize your data structure here. */
      public TicTacToe(int n) {
       rowArr=new int[n];
       colArr=new int[n];
       }
      /** Player {player} makes a move at ({row}, {col}).
       @param row The row of the board.
       @param col The column of the board.
       @param player The player, can be either 1 or 2.
       @return The current winning condition, can be either:
       0: No one wins.
       1: Player 1 wins.
       2: Player 2 wins. */
      public int move(int row, int col, int player) {
      int n=rowArr.length;
      int temp=player==1?-1:1;
       rowArr[row]+=temp;
       colArr[col]+=temp;
      if(row==col){
       line1+=temp;
       }
      if(col==n-row-1){
       line2+=temp;
       }
      if(rowArr[row]==n || colArr[col]==n ||
       rowArr[row]==-n || colArr[col]==-n ||
       line1==n || line2==n || line1==-n || line2==-n){
      return player;
       }
      return 0;
       }
      }
      /**
       * Your TicTacToe object will be instantiated and called as such:
       * TicTacToe obj = new TicTacToe(n);
       * int param_1 = obj.move(row,col,player);
       */
  
 

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/104103177