348. Design Tic-Tac-Toe

betacat 发布于2019-08-14 17:27 / 1025人阅读

摘要：题目链接这道题找是否有赢的方法和相似，稍微简化了。统计行列和两个对角线的情况，两个分别用和来记。然后判断是否有一个人赢只需要的复杂度。当然这么做的前提是假设所有的都是的，棋盘一个地方已经被占用了，就不能走那个地方了。

348. Design Tic-Tac-Toe

题目链接：https://leetcode.com/problems...

这道题找是否有player赢的方法和N-Queens相似，稍微简化了。统计行列和两个对角线player的情况，两个player分别用+1和-1来记。然后判断是否有一个人赢只需要O(1)的复杂度。当然这么做的前提是假设所有的move都是valid的，棋盘一个地方已经被占用了，就不能走那个地方了。

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;
    }
}

idc机房托管服务器托管 348元的云服务器 Design Ant Design Fusion Design

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66650.html

[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

摘要：当有一行完全只有这两个中的其中一个人时，的绝对值应该等于这个数列的长度，这样就不需要每次再扫一遍数组。题目：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 剪枝算法简介，以及以此实现的井字棋游戏（Tic-tac-t

摘要：我们在前文中考虑的那张图就来自这篇文章，之后我们会用剪枝算法来改进之前的解决方案。剪枝算法的实现接下来讨论如何修改前面实现的算法，使其变为剪枝算法。现在我们已经有了现成的和剪枝算法，只要加上一点儿细节就能完成这个游戏了。前段时间用 React 写了个2048 游戏来练练手，准备用来回顾下 React 相关的各种技术，以及试验一下新技术。在写这个2048的过程中，我考虑是否可以在其中加...

wemall 2019-08-22 15:06 评论0 收藏0
Minimax 和 Alpha-beta 剪枝算法简介，以及以此实现的井字棋游戏（Tic-tac-t

摘要：我们在前文中考虑的那张图就来自这篇文章，之后我们会用剪枝算法来改进之前的解决方案。剪枝算法的实现接下来讨论如何修改前面实现的算法，使其变为剪枝算法。现在我们已经有了现成的和剪枝算法，只要加上一点儿细节就能完成这个游戏了。前段时间用 React 写了个2048 游戏来练练手，准备用来回顾下 React 相关的各种技术，以及试验一下新技术。在写这个2048的过程中，我考虑是否可以在其中加...

Eirunye 2019-06-26 18:20 评论0 收藏0
一次诡异的docker错误调试

摘要：源自小伙伴的求助，虽然没能定位到最终的原因，调试的过程也比较有意思缘起小伙伴求助我，同一个镜像在测试机器上可以运行，在阿里云上运行提示用户不存在。源自小伙伴的求助，虽然没能定位到最终的原因，调试的过程也比较有意思缘起小伙伴求助我，同一个docker镜像在测试机器上可以运行，在阿里云上运行提示用户不存在。在阿里云上运行提示如下： # docker run --rm -it ima...

Jeff 2019-06-28 17:12 评论0 收藏0