在Tic Tac Toe遊戲Leetcode解決方案上尋找贏家


難度級別 容易獎學金
經常問 亞馬遜 蘋果 Facebook 百會
排列

在井字遊戲中尋找獲勝者的問題Leetcode解決方案要求我們找出井字遊戲的獲勝者。 這個問題為我們提供了一個 排列 或玩家移動的向量。 我們需要仔細研究一下動作並判斷誰贏得了比賽。 遊戲的結果可以贏,平局或待決。 萬一其中任何人贏得比賽,我們都會返回A或B。但是在評判遊戲之前,我們必須了解這個Tic Tac Toe特定版本的規則。

  • 玩家只能在尚未使用的方塊上移動。
  • 第一位玩家 A 總是放置“ X”字符,而第二個玩家 B 始終放置“ O”字符。
  • “ X”和“ O”字符始終放置在空白框中。 永遠不要使用已經被利用的正方形。
  • 當有3個相同(非空)字符填充任何行,列或對角線時,遊戲結束。
  • 如果所有方塊都不為空,則遊戲也將結束。 在某些情況下,他們倆都不贏,最終以平局告終。
  • 如果遊戲結束,將無法再進行任何移動。 如果還有一些動作,則判定為“待定”。
  • 玩家“ A”先出手,然後兩個玩家交替使用回合。

讓我們看幾個例子。

moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
"A"

在Tic Tac Toe遊戲Leetcode解決方案上尋找贏家

說明:如上圖所示,帶有“ X”的玩家贏得遊戲。 A總是開始遊戲,因此獲勝者也是“ A”。

井字遊戲Leetcode解決方案上尋找獲勝者的方法

問題在於在做出一些動作後找到井字遊戲的最終裁決。 這是一個標準遊戲,因此我們只需要模擬該過程即可。 我們還需要按照輸入中指定的順序執行步驟。 一種方法是創建3×3的網格,然後模擬相同的過程。 但是我們沒有這樣做,而是跟踪兩個玩家使用數組進行的移動。 我們為兩個玩家使用4個不同的數組,對於每個行和列,他們使用2個數組進行移動。 對於每一步,我們增加存儲在這些數組中的值。 一旦值等於3。我們知道水平或垂直進行3次移動。

對於對角線,我們僅使用與數組相似的4個變量。 當任何一個值等於3時,我們將相應地返回名稱。 但是,如果我們在做出所有舉動之前沒有做出裁決的話。 然後,如果網格上的所有正方形都被佔用,我們將得出平局的結論,否則將返回未決。

井字遊戲Leetcode解決方案上尋找獲勝者的代碼

C ++代碼

#include <bits/stdc++.h>
using namespace std;

string tictactoe(vector<vector<int>>& moves) {
    int aRow[3] = {0}, bRow[3] = {0}, aCol[3] = {0}, bCol[3] = {0};
    int aDiagonal1 = 0, bDiagonal1 = 0, aDiagonal2 = 0, bDiagonal2 = 0;
    int n = moves.size();
    for (int i = 0; i < n; i++) {
        int r = moves[i][0], c = moves[i][1];
        if (i % 2 == 1) {
            if (++bRow[r] == 3 || ++bCol[c] == 3 || (r == c && ++bDiagonal1 == 3) || (r + c == 2 && ++bDiagonal2 == 3)) return "B";
        }else {
            if (++aRow[r] == 3 || ++aCol[c] == 3 || (r == c && ++aDiagonal1 == 3) || (r + c == 2 && ++aDiagonal2 == 3)) return "A";
        }
    }
    return n == 9 ? "Draw" : "Pending";
}

int main(){
    vector<vector<int>> moves = {{0,0}, {2,0}, {1,1}, {2,1}, {2,2}};
    cout<<tictactoe(moves);
}
A

Java代碼

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static String tictactoe(int[][] moves) {
        int[] aRow = new int[3];
        int[] aCol = new int[3];
        int[] bRow = new int[3];
        int[] bCol = new int[3];
        int aDiagonal1 = 0, bDiagonal1 = 0, aDiagonal2 = 0, bDiagonal2 = 0;
        int n = moves.length;
        for (int i = 0; i < n; i++) {
            int r = moves[i][0], c = moves[i][1];
            if (i % 2 == 1) {
                if (++bRow[r] == 3 || ++bCol[c] == 3 || (r == c && ++bDiagonal1 == 3) || (r + c == 2 && ++bDiagonal2 == 3)) return "B";
            }else {
                if (++aRow[r] == 3 || ++aCol[c] == 3 || (r == c && ++aDiagonal1 == 3) || (r + c == 2 && ++aDiagonal2 == 3)) return "A";
            }
        }
        return n == 9 ? "Draw" : "Pending";        
    }
    
  public static void main (String[] args) throws java.lang.Exception {
    int[][] moves = {{0,0}, {2,0}, {1,1}, {2,1}, {2,2}};
    	System.out.println(tictactoe(moves));
  }
}
A

複雜度分析

時間複雜度

上), 其中N是作為函數輸入發送的移動數。

空間複雜度

O(R + C), 因為我們在井字遊戲中創建了4個大小等於網格的行和列的數組。