Знайдзіце пераможцу на гульні Tic Tac Toe Leetcode Solution


Узровень складанасці Лёгка
Часта пытаюцца ў амазонка яблык facebook Zoho
масіў

Праблема "Знайсці пераможцу ў гульні" Tic Tac Toe "" Leetcode Solution "просіць нас высветліць пераможцу гульні ў" крыжыкі ". Праблема дае нам масіў альбо вектар хадоў, зробленых гульцамі. Нам трэба прайсці ходы і судзіць, хто выйграе гульню. Вынік гульні можна выйграць, згуляць унічыю альбо чакаць. У выпадках, калі хто-небудзь з іх перамагае ў гульні, мы вяртаем A альбо B. Але перш чым судзіць гульню, мы павінны ведаць правілы гэтай канкрэтнай версіі Tic Tac Toe.

  • Гульцы могуць рабіць хады толькі на тых квадратах, якія яшчэ не былі выкарыстаны.
  • Першы гулец A заўсёды змяшчае сімвалы "X", а другі гулец B заўсёды ставіць сімвалы "O".
  • Знакі "X" і "O" заўсёды размяшчаюцца ў пустых квадратах. Ні ў якім разе нельга выкарыстоўваць квадраты, якія ўжо былі выкарыстаны.
  • Гульня заканчваецца, калі ў любым радку, слупку ці дыяганалі ёсць 3 аднолькавых (ня пустых) персанажа.
  • Гульня таксама заканчваецца, калі ўсе квадраты не пустыя. У некаторых выпадках абодва яны не выйграюць і апынуцца ўнічыю.
  • Больш хадоў нельга праводзіць, калі гульня скончана. Калі засталося некалькі хадоў, прысуд "чакае чакання".
  • Гулец "А" робіць першы ход, а потым абодва гульцы выкарыстоўваюць альтэрнатыўныя павароты.

Давайце разгледзім некалькі прыкладаў.

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

Знайдзіце пераможцу на гульні Tic Tac Toe Leetcode Solution

Тлумачэнне: Як паказана вышэй на малюнку, гулец з "X" выйграе гульню. Гульня заўсёды пачынаецца, таму пераможцам таксама становіцца "А".

Падыход да пошуку пераможцы ў гульні Tic Tac Toe з рашэннем Leetcode

Праблема заключаецца ў тым, каб знайсці канчатковы вердыкт гульні ў крыжыкі пасля некалькіх хадоў. Гэта звычайная гульня, таму нам трэба проста змадэляваць працэс. Акрамя таго, нам трэба выканаць этапы ў тым жа парадку, што і пры ўводзе. Адзін са спосабаў - стварыць сетку 3 × 3, а затым імітаваць той самы працэс. Але замест гэтага мы адсочваем хады абодвух гульцоў з выкарыстаннем масіваў. Мы выкарыстоўваем 4 розныя масівы для абодвух гульцоў, 2 для хадоў, зробленых імі адносна кожнага радка і слупка. Для кожнага ходу мы павялічваем значэнні, якія захоўваюцца ў гэтых масівах. Пасля таго, як значэнні стануць роўнымі 3. Мы ведаем, што 3 хады робяцца альбо па гарызанталі, альбо па вертыкалі.

Для дыяганаляў мы проста выкарыстоўваем 4 зменныя, падобныя на масівы. Калі якое-небудзь з значэнняў становіцца роўным 3. Мы вяртаем імя адпаведна. Але калі мы не вынесем вердыкт, пакуль не будуць зроблены ўсе крокі. Затым мы вяртаем вердыкт розыгрышу, калі ўсе квадраты на сетцы занятыя, інакш чакаецца вяртанне.

Код для пошуку пераможцы ў гульні Tic Tac Toe Рашэнне 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

Аналіз складанасці

Складанасць часу

O (N), дзе N - колькасць хадоў, адпраўленых у якасці ўваходных дадзеных для функцыі.

Касмічная складанасць

O (R + C), таму што мы ствараем 4 масіва памерам, роўным радку і слупку сеткі ў гульні ў крыжыкі-нулікі.