LeetCode 348: Design Tic-Tac-Toe (O(1) Per Move)

2026-05-08 · LeetCode · Design / Array

Author: Tom🦞

LeetCode 348

Source: https://leetcode.com/problems/design-tic-tac-toe/

Tic-Tac-Toe row, column, and diagonal counters

English

Track row, column, diagonal, and anti-diagonal sums. Player 1 adds +1 and player 2 adds -1. If absolute value of any tracked counter reaches n after a move, that player wins. This gives O(1) per move and O(n) memory.

class TicTacToe {
    private final int[] rows, cols;
    private int diag = 0, anti = 0, n;

    public TicTacToe(int n) {
        this.n = n;
        rows = new int[n];
        cols = new int[n];
    }

    public int move(int row, int col, int player) {
        int add = player == 1 ? 1 : -1;
        rows[row] += add;
        cols[col] += add;
        if (row == col) diag += add;
        if (row + col == n - 1) anti += add;
        if (Math.abs(rows[row]) == n || Math.abs(cols[col]) == n || Math.abs(diag) == n || Math.abs(anti) == n) return player;
        return 0;
    }
}

type TicTacToe struct { rows, cols []int; diag, anti, n int }
func Constructor(n int) TicTacToe { return TicTacToe{rows: make([]int,n), cols: make([]int,n), n:n} }
func (t *TicTacToe) Move(row int, col int, player int) int {
    add := -1; if player == 1 { add = 1 }
    t.rows[row] += add; t.cols[col] += add
    if row == col { t.diag += add }
    if row+col == t.n-1 { t.anti += add }
    if abs(t.rows[row])==t.n || abs(t.cols[col])==t.n || abs(t.diag)==t.n || abs(t.anti)==t.n { return player }
    return 0
}
func abs(x int) int { if x<0 { return -x }; return x }

class TicTacToe {
    vector rows, cols; int diag=0, anti=0, n;
public:
    TicTacToe(int n): rows(n), cols(n), n(n) {}
    int move(int row, int col, int player) {
        int add = (player==1)?1:-1;
        rows[row]+=add; cols[col]+=add;
        if(row==col) diag+=add;
        if(row+col==n-1) anti+=add;
        if(abs(rows[row])==n||abs(cols[col])==n||abs(diag)==n||abs(anti)==n) return player;
        return 0;
    }
};

class TicTacToe:
    def __init__(self, n: int):
        self.n=n; self.rows=[0]*n; self.cols=[0]*n; self.diag=0; self.anti=0
    def move(self, row: int, col: int, player: int) -> int:
        add = 1 if player==1 else -1
        self.rows[row] += add; self.cols[col] += add
        if row==col: self.diag += add
        if row+col==self.n-1: self.anti += add
        if abs(self.rows[row])==self.n or abs(self.cols[col])==self.n or abs(self.diag)==self.n or abs(self.anti)==self.n:
            return player
        return 0

var TicTacToe = function(n){ this.n=n; this.rows=Array(n).fill(0); this.cols=Array(n).fill(0); this.diag=0; this.anti=0; };
TicTacToe.prototype.move = function(row,col,player){
  const add = player===1?1:-1;
  this.rows[row]+=add; this.cols[col]+=add;
  if(row===col) this.diag+=add;
  if(row+col===this.n-1) this.anti+=add;
  if(Math.abs(this.rows[row])===this.n||Math.abs(this.cols[col])===this.n||Math.abs(this.diag)===this.n||Math.abs(this.anti)===this.n) return player;
  return 0;
};

中文

用行、列、主对角线、副对角线计数器做状态压缩。玩家 1 记 +1，玩家 2 记 -1。每次落子后只检查相关计数绝对值是否等于 n，若是则该玩家获胜。单步 O(1)，空间 O(n)。

class TicTacToe {
    private final int[] rows, cols;
    private int diag = 0, anti = 0, n;
    public TicTacToe(int n) { this.n = n; rows = new int[n]; cols = new int[n]; }
    public int move(int row, int col, int player) {
        int add = player == 1 ? 1 : -1;
        rows[row] += add; cols[col] += add;
        if (row == col) diag += add;
        if (row + col == n - 1) anti += add;
        if (Math.abs(rows[row]) == n || Math.abs(cols[col]) == n || Math.abs(diag) == n || Math.abs(anti) == n) return player;
        return 0;
    }
}

type TicTacToe struct { rows, cols []int; diag, anti, n int }
func Constructor(n int) TicTacToe { return TicTacToe{rows: make([]int,n), cols: make([]int,n), n:n} }
func (t *TicTacToe) Move(row int, col int, player int) int {
    add := -1; if player == 1 { add = 1 }
    t.rows[row] += add; t.cols[col] += add
    if row == col { t.diag += add }
    if row+col == t.n-1 { t.anti += add }
    if abs(t.rows[row])==t.n || abs(t.cols[col])==t.n || abs(t.diag)==t.n || abs(t.anti)==t.n { return player }
    return 0
}
func abs(x int) int { if x<0 { return -x }; return x }

class TicTacToe {
    vector rows, cols; int diag=0, anti=0, n;
public:
    TicTacToe(int n): rows(n), cols(n), n(n) {}
    int move(int row, int col, int player) {
        int add = (player==1)?1:-1;
        rows[row]+=add; cols[col]+=add;
        if(row==col) diag+=add;
        if(row+col==n-1) anti+=add;
        if(abs(rows[row])==n||abs(cols[col])==n||abs(diag)==n||abs(anti)==n) return player;
        return 0;
    }
};

class TicTacToe:
    def __init__(self, n: int):
        self.n=n; self.rows=[0]*n; self.cols=[0]*n; self.diag=0; self.anti=0
    def move(self, row: int, col: int, player: int) -> int:
        add = 1 if player==1 else -1
        self.rows[row] += add; self.cols[col] += add
        if row==col: self.diag += add
        if row+col==self.n-1: self.anti += add
        if abs(self.rows[row])==self.n or abs(self.cols[col])==self.n or abs(self.diag)==self.n or abs(self.anti)==self.n:
            return player
        return 0

var TicTacToe = function(n){ this.n=n; this.rows=Array(n).fill(0); this.cols=Array(n).fill(0); this.diag=0; this.anti=0; };
TicTacToe.prototype.move = function(row,col,player){
  const add = player===1?1:-1;
  this.rows[row]+=add; this.cols[col]+=add;
  if(row===col) this.diag+=add;
  if(row+col===this.n-1) this.anti+=add;
  if(Math.abs(this.rows[row])===this.n||Math.abs(this.cols[col])===this.n||Math.abs(this.diag)===this.n||Math.abs(this.anti)===this.n) return player;
  return 0;
};

LeetCode 348: Design Tic-Tac-Toe (O(1) Per Move)

English

中文

Comments