348. Design Tic-Tac-Toe

betacat 發(fā)布于2019-08-14 17:27 / 1185人閱讀

摘要：題目鏈接這道題找是否有贏的方法和相似，稍微簡化了。統(tǒng)計(jì)行列和兩個(gè)對角線的情況，兩個(gè)分別用和來記。然后判斷是否有一個(gè)人贏只需要的復(fù)雜度。當(dāng)然這么做的前提是假設(shè)所有的都是的，棋盤一個(gè)地方已經(jīng)被占用了，就不能走那個(gè)地方了。

348. Design Tic-Tac-Toe

題目鏈接：https://leetcode.com/problems...

這道題找是否有player贏的方法和N-Queens相似，稍微簡化了。統(tǒng)計(jì)行列和兩個(gè)對角線player的情況，兩個(gè)player分別用+1和-1來記。然后判斷是否有一個(gè)人贏只需要O(1)的復(fù)雜度。當(dāng)然這么做的前提是假設(shè)所有的move都是valid的，棋盤一個(gè)地方已經(jīng)被占用了，就不能走那個(gè)地方了。

public class TicTacToe {
    int n;
    int[] cols;
    int[] rows;
    int diag;
    int antidiag;
    
    public TicTacToe(int n) {
        this.n = n;
        cols = new int[n];
        rows = new int[n];
        diag = 0;
        antidiag = 0;
    }
    
    public int move(int row, int col, int player) {
        // -1 for player 1, +1 for player 2
        int flag = (player == 1 ? -1 : 1);
        
        rows[row] += flag;
        cols[col] += flag;
        if(row == col) diag += flag;
        if(row + col == n - 1) antidiag += flag;
        
        if(Math.abs(rows[row]) == n || Math.abs(cols[col]) == n || Math.abs(diag) == n || Math.abs(antidiag) == n) return player;
        
        return 0;
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/66650.html

相關(guān)文章

[LeetCode] 348. Design Tic-Tac-Toe

Problem Design a Tic-tac-toe game that is played between two players on a n x n grid. You may assume the following rules: A move is guaranteed to be valid and is placed on an empty block.Once a winnin...

MobService 2019-08-16 13:51 評論0 收藏0
348. Design Tic-Tac-Toe

摘要：當(dāng)有一行完全只有這兩個(gè)中的其中一個(gè)人時(shí)，的絕對值應(yīng)該等于這個(gè)數(shù)列的長度，這樣就不需要每次再掃一遍數(shù)組。題目：Design a Tic-tac-toe game that is played between two players on a n x n grid. You may assume the following rules: A move is guaranteed to b...

zhkai 2019-08-14 14:18 評論0 收藏0
Minimax 和 Alpha-beta 剪枝算法簡介，以及以此實(shí)現(xiàn)的井字棋游戲（Tic-tac-t

摘要：我們在前文中考慮的那張圖就來自這篇文章，之后我們會用剪枝算法來改進(jìn)之前的解決方案。剪枝算法的實(shí)現(xiàn)接下來討論如何修改前面實(shí)現(xiàn)的算法，使其變?yōu)榧糁λ惴ā，F(xiàn)在我們已經(jīng)有了現(xiàn)成的和剪枝算法，只要加上一點(diǎn)兒細(xì)節(jié)就能完成這個(gè)游戲了。前段時(shí)間用 React 寫了個(gè)2048 游戲來練練手，準(zhǔn)備用來回顧下 React 相關(guān)的各種技術(shù)，以及試驗(yàn)一下新技術(shù)。在寫這個(gè)2048的過程中，我考慮是否可以在其中加...

wemall 2019-08-22 15:06 評論0 收藏0
Minimax 和 Alpha-beta 剪枝算法簡介，以及以此實(shí)現(xiàn)的井字棋游戲（Tic-tac-t

摘要：我們在前文中考慮的那張圖就來自這篇文章，之后我們會用剪枝算法來改進(jìn)之前的解決方案。剪枝算法的實(shí)現(xiàn)接下來討論如何修改前面實(shí)現(xiàn)的算法，使其變?yōu)榧糁λ惴ā，F(xiàn)在我們已經(jīng)有了現(xiàn)成的和剪枝算法，只要加上一點(diǎn)兒細(xì)節(jié)就能完成這個(gè)游戲了。前段時(shí)間用 React 寫了個(gè)2048 游戲來練練手，準(zhǔn)備用來回顧下 React 相關(guān)的各種技術(shù)，以及試驗(yàn)一下新技術(shù)。在寫這個(gè)2048的過程中，我考慮是否可以在其中加...

Eirunye 2019-06-26 18:20 評論0 收藏0
一次詭異的docker錯(cuò)誤調(diào)試

摘要：源自小伙伴的求助，雖然沒能定位到最終的原因，調(diào)試的過程也比較有意思緣起小伙伴求助我，同一個(gè)鏡像在測試機(jī)器上可以運(yùn)行，在阿里云上運(yùn)行提示用戶不存在。源自小伙伴的求助，雖然沒能定位到最終的原因，調(diào)試的過程也比較有意思緣起小伙伴求助我，同一個(gè)docker鏡像在測試機(jī)器上可以運(yùn)行，在阿里云上運(yùn)行提示用戶不存在。在阿里云上運(yùn)行提示如下： # docker run --rm -it ima...

Jeff 2019-06-28 17:12 評論0 收藏0