1275.找出井字棋的獲勝者Java

題目描述

A 和 B 在一個 3 x 3 的網格上玩井字棋。

井字棋遊戲的規則如下：

玩家輪流将棋子放在空方格 (" ") 上。

第一個玩家 A 總是用 “X” 作為棋子，而第二個玩家 B 總是用 “O” 作為棋子。

“X” 和 “O” 隻能放在空方格中，而不能放在已經被占用的方格上。

隻要有 3 個相同的（非空）棋子排成一條直線（行、列、對角線）時，遊戲結束。

如果所有方塊都放滿棋子（不為空），遊戲也會結束。

遊戲結束後，棋子無法再進行任何移動。

給你一個數組 moves，其中每個元素是大小為 2 的另一個數組（元素分别對應網格的行和列），它按照 A 和 B 的行動順序（先 A 後 B）記錄了兩人各自的棋子位置。

如果遊戲存在獲勝者（A 或 B），就傳回該遊戲的獲勝者；如果遊戲以平局結束，則傳回 “Draw”；如果仍會有行動（遊戲未結束），則傳回 “Pending”。

你可以假設 moves 都 有效（遵循井字棋規則），網格最初是空的，A 将先行動。

輸入輸出樣式

示例1：

輸入：moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]

輸出：“A”

解釋：“A” 獲勝，他總是先走。

示例2：

輸入：moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]]

輸出：“B”

解釋：“B” 獲勝。

示例3：

輸入：moves = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]]

輸出：“Draw”

輸出：由于沒有辦法再行動，遊戲以平局結束。

“XXO”

“OOX”

“XOX”

示例4：

輸入：moves = [[0,0],[1,1]]

輸出：“Pending”

解釋：遊戲還沒有結束。

"X "

" O "

" "

本文題來自https://leetcode-cn.com/problems/find-winner-on-a-tic-tac-toe-game

思路

1.首先判斷A和B誰勝利了，如果沒有結果再判斷是Pending還是Draw。

2.判斷誰勝利了，其實隻需要判斷最後下一步棋的是否獲勝就可以了。因為如果最後一手勝利了就不會再繼續下了(假設有勝者的話)。

3.反着周遊Moves數組，預設最後一手為周遊對象，來記錄棋子的情況(行，列，主副對角線一旦有一個滿足有3個棋子即獲勝)，借此判斷勝利與否。

算法分析

時間複雜度為O(Moves.Length)，空間複雜度為O(1)

求解函數

public String tictactoe(int[][] moves) {
        int size = moves.length; 
        //數組count分别記錄行、列、正副對角線的棋子個數
        //count[0~2]為行，[3~5]為列,[6~7]為正副對角線
        int[] count = new int[8];
        //反着周遊，最後一個下棋的肯定是勝利的人
        for (int i = size - 1; i >= 0; i -= 2) {
            //記錄行的棋子數
            count[moves[i][0]]++;
            //記錄列的棋子數，列記錄在3~5是以要+3
            count[moves[i][1] + 3]++;
            //記錄主對角線的棋子數
            if (moves[i][0] == moves[i][1]) count[6]++;
            //記錄副對角線的棋子數
            if (moves[i][0] + moves[i][1] == 2) count[7]++;
            //判斷是否滿足獲勝條件
            if (count[moves[i][0]] == 3 || count[moves[i][1] + 3] == 3
                    || count[6] == 3 || count[7] == 3) {
                //總步數為偶數則B勝，反之則A勝，因為A先下B後下。
                return (size % 2 == 0) ? "B" : "A";
            }
        }
        //不滿足以上的獲勝條件，則看棋盤是否下滿了棋子
        if (size < 9) return "Pending";
        //既不滿足勝利條件，棋盤也不滿，則可以繼續下棋
        return "Draw";
    }
           

主函數調用

class Solution1275 {
    public static void main(String[] args) {
        Solution1275 sol = new Solution1275();
        int[][] moves = new int[][]{{0, 0}, {1, 1}, {0, 1}, {0, 2}, {1, 0},{2, 0}};
        System.out.println(sol.tictactoe(moves));
    }

    public String tictactoe(int[][] moves) {...}
}
           

輸出結果