LeetCode348 Design Tic Tac Toe

Posted on In

题目描述

Design a Tic-tac-toe game that is played between two players on a n x n grid.

You may assume the following rules:

  • A move is guaranteed to be valid and is placed on an empty block.
  • Once a winning condition is reached, no more moves is allowed.
  • A player who succeeds in placing n of their marks in a horizontal, vertical, or diagonal row wins the game. Example:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    Given n = 3, assume that player 1 is "X" and player 2 is "O" in the board.

    TicTacToe toe = new TicTacToe(3);

    toe.move(0, 0, 1); -> Returns 0 (no one wins)
    |X| | |
    | | | |    // Player 1 makes a move at (0, 0).
    | | | |

    toe.move(0, 2, 2); -> Returns 0 (no one wins)
    |X| |O|
    | | | |    // Player 2 makes a move at (0, 2).
    | | | |

    toe.move(2, 2, 1); -> Returns 0 (no one wins)
    |X| |O|
    | | | |    // Player 1 makes a move at (2, 2).
    | | |X|

    toe.move(1, 1, 2); -> Returns 0 (no one wins)
    |X| |O|
    | |O| |    // Player 2 makes a move at (1, 1).
    | | |X|

    toe.move(2, 0, 1); -> Returns 0 (no one wins)
    |X| |O|
    | |O| |    // Player 1 makes a move at (2, 0).
    |X| |X|

    toe.move(1, 0, 2); -> Returns 0 (no one wins)
    |X| |O|
    |O|O| |    // Player 2 makes a move at (1, 0).
    |X| |X|

    toe.move(2, 1, 1); -> Returns 1 (player 1 wins)
    |X| |O|
    |O|O| |    // Player 1 makes a move at (2, 1).
    |X|X|X|

Follow up:
Could you do better than O(n2) per move() operation?

解析

题目要求设计个井字棋游戏，要求能够下子并且下了后能够判断输赢，一个很简单的方法就是存一个n * n的数组，用来保存棋谱，不过follow up要求用比O(n2)更好的方式解决move。

其实我们只要记录行、列、以及对角线上的子的个数就行，因为只有两种情况，所以可以分别设置为+1, -1每次检查下绝对值之和是否为n即可，时间复杂度和空间复杂度都是O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class TicTacToe {
    int[] rows;
    int[] cols;
    int dig;
    int bdig;
    int n;
    /** Initialize your data structure here. */
    public TicTacToe(int n) {
        rows = new int[n];
        cols = new int[n];
        dig = 0;
        bdig = 0;
        this.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) {
        int toAdd = player == 1 ? 1 : -1;
        rows[row] += toAdd;
        cols[col] += toAdd;
        if(row == col)
            dig += toAdd;
        if(row + col == n - 1)
            bdig += toAdd;
        
        if(Math.abs(rows[row]) == n || Math.abs(cols[col]) == n || Math.abs(dig) == n || Math.abs(bdig) == n)
            return player;
        return 0;
    }
}

总结

一道很典型的设计题，关键在于抓住问题的本质，算法的优化都是先想出比较暴力一点的办法解决问题，再精简掉不必要的部分