1275. 找出井字棋的获胜者
题目描述
A 和 B 在 3 x 3 的空棋盘上下井字棋。A 先手，用 X；B 后手，用 O。两人轮流在空格上落子，不能落在已占用的格子上。
任何一方的三枚棋子连成一行、一列或一条对角线时，游戏立即结束，该方获胜。棋盘下满也会结束。结束后不再落子。
输入数组 moves，moves[i] = [rowi, coli] 是第 i 步的落点，行列下标从 0 开始。保证所有落子都合法。
如果有人获胜，返回 "A" 或 "B"；如果棋盘下满且无人获胜，返回 "Draw"；如果游戏还没结束，返回 "Pending"。
示例 1
输入：moves = [[0,0],[2,0],[1,1],[2,1],[2,2]] 输出："A"
解释：A 占据 (0,0)、(1,1)、(2,2)，连成主对角线。
示例 2
输入：moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]] 输出："B"
解释：B 占据 (1,1)、(0,2)、(2,0)，连成副对角线。
示例 3
输入：moves = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]] 输出："Draw"
解释：九步下满，双方都没有连成一线。
数据范围
1 <= moves.length <= 9moves[i].length == 20 <= moves[i][j] <= 2moves中没有重复的落点。moves符合井字棋规则。
解题思路
不必每步检查整个棋盘。给 8 条线（3 行、3 列、2 条对角线）各开一个计数器，A 落子记 +1，B 落子记 -1。每步只更新经过该格子的线：所在行、所在列，以及（若在上面）主对角线 r == c 和副对角线 r + c == 2。某条线的计数绝对值达到 3，说明它的 3 格都是同一个人的，当前落子者获胜。
为什么正确
rows[i]、cols[j]、diag、anti 等于这条线上 A 的棋子数减 B 的棋子数；绝对值为 3 当且仅当三格同属一人。
复杂度分析
时间 O(m)，m 为步数（最多 9）；空间 O(1)。推广到 n×n 棋盘时每步仍是 O(1)。
易错点
中心格 (1,1) 同时属于两条对角线，两个 if 不能写成 if/elif。判断结束时，只有恰好下满 9 步才是平局，步数不足时是 Pending。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def tictactoe(self, moves: List[List[int]]) -> str:
rows, cols = [0] * 3, [0] * 3
diag = anti = 0
for k, (r, c) in enumerate(moves):
v = 1 if k % 2 == 0 else -1
rows[r] += v
cols[c] += v
if r == c:
diag += v
if r + c == 2:
anti += v
if 3 in (abs(rows[r]), abs(cols[c]), abs(diag), abs(anti)):
return "A" if v == 1 else "B"
return "Draw" if len(moves) == 9 else "Pending"class Solution {
public String tictactoe(int[][] moves) {
int[] rows = new int[3], cols = new int[3];
int diag = 0, anti = 0;
for (int k = 0; k < moves.length; k++) {
int r = moves[k][0], c = moves[k][1];
int v = k % 2 == 0 ? 1 : -1;
rows[r] += v;
cols[c] += v;
if (r == c) {
diag += v;
}
if (r + c == 2) {
anti += v;
}
if (Math.abs(rows[r]) == 3 || Math.abs(cols[c]) == 3 || Math.abs(diag) == 3 || Math.abs(anti) == 3) {
return v == 1 ? "A" : "B";
}
}
return moves.length == 9 ? "Draw" : "Pending";
}
}class Solution {
public:
string tictactoe(vector<vector<int>>& moves) {
int rows[3] = {0}, cols[3] = {0};
int diag = 0, anti = 0;
for (int k = 0; k < (int)moves.size(); k++) {
int r = moves[k][0], c = moves[k][1];
int v = k % 2 == 0 ? 1 : -1;
rows[r] += v;
cols[c] += v;
if (r == c) {
diag += v;
}
if (r + c == 2) {
anti += v;
}
if (abs(rows[r]) == 3 || abs(cols[c]) == 3 || abs(diag) == 3 || abs(anti) == 3) {
return v == 1 ? "A" : "B";
}
}
return moves.size() == 9 ? "Draw" : "Pending";
}
};func tictactoe(moves [][]int) string {
rows, cols := make([]int, 3), make([]int, 3)
diag, anti := 0, 0
abs := func(x int) int { return int(math.Abs(float64(x))) }
for k, m := range moves {
r, c := m[0], m[1]
v := 1
if k%2 == 1 {
v = -1
}
rows[r] += v
cols[c] += v
if r == c {
diag += v
}
if r+c == 2 {
anti += v
}
if abs(rows[r]) == 3 || abs(cols[c]) == 3 || abs(diag) == 3 || abs(anti) == 3 {
if v == 1 {
return "A"
}
return "B"
}
}
if len(moves) == 9 {
return "Draw"
}
return "Pending"
}var tictactoe = function(moves) {
const rows = [0, 0, 0], cols = [0, 0, 0];
let diag = 0, anti = 0;
for (let k = 0; k < moves.length; k++) {
const [r, c] = moves[k];
const v = k % 2 === 0 ? 1 : -1;
rows[r] += v;
cols[c] += v;
if (r === c) {
diag += v;
}
if (r + c === 2) {
anti += v;
}
if ([rows[r], cols[c], diag, anti].some(x => Math.abs(x) === 3)) {
return v === 1 ? "A" : "B";
}
}
return moves.length === 9 ? "Draw" : "Pending";
};function tictactoe(moves: number[][]): string {
const rows = [0, 0, 0], cols = [0, 0, 0];
let diag = 0, anti = 0;
for (let k = 0; k < moves.length; k++) {
const [r, c] = moves[k];
const v = k % 2 === 0 ? 1 : -1;
rows[r] += v;
cols[c] += v;
if (r === c) {
diag += v;
}
if (r + c === 2) {
anti += v;
}
if ([rows[r], cols[c], diag, anti].some(x => Math.abs(x) === 3)) {
return v === 1 ? "A" : "B";
}
}
return moves.length === 9 ? "Draw" : "Pending";
}