[LeetCode] 348. Design Tic-Tac-Toe

MobService 发布于2019-08-16 13:51 / 3029人阅读

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 winning condition is reached, no more moves is allowed.
A player who succeeds in placing n of their marks in a horizontal, vertical, or diagonal row wins the game.
Example:

Given n = 3, assume that player 1 is "X" and player 2 is "O" in the board.

TicTacToe toe = new TicTacToe(3);

toe.move(0, 0, 1); -> Returns 0 (no one wins)
|X| | |
| | | |    // Player 1 makes a move at (0, 0).
| | | |

toe.move(0, 2, 2); -> Returns 0 (no one wins)
|X| |O|
| | | |    // Player 2 makes a move at (0, 2).
| | | |

toe.move(2, 2, 1); -> Returns 0 (no one wins)
|X| |O|
| | | |    // Player 1 makes a move at (2, 2).
| | |X|

toe.move(1, 1, 2); -> Returns 0 (no one wins)
|X| |O|
| |O| |    // Player 2 makes a move at (1, 1).
| | |X|

toe.move(2, 0, 1); -> Returns 0 (no one wins)
|X| |O|
| |O| |    // Player 1 makes a move at (2, 0).
|X| |X|

toe.move(1, 0, 2); -> Returns 0 (no one wins)
|X| |O|
|O|O| |    // Player 2 makes a move at (1, 0).
|X| |X|

toe.move(2, 1, 1); -> Returns 1 (player 1 wins)
|X| |O|
|O|O| |    // Player 1 makes a move at (2, 1).
|X|X|X|

Follow up:
Could you do better than O(n2) per move() operation?

Solution

class TicTacToe {

    private int[] rows;
    private int[] cols;
    private int diagonal;
    private int antiDiagonal;
    private int size;
    /** Initialize your data structure here. */
    public TicTacToe(int n) {
        rows = new int[n];
        cols = new int[n];
        diagonal = 0;
        antiDiagonal = 0;
        size = n;
    }
    
    /** Player {player} makes a move at ({row}, {col}).
        @param row The row of the board.
        @param col The column of the board.
        @param player The player, can be either 1 or 2.
        @return The current winning condition, can be either:
                0: No one wins.
                1: Player 1 wins.
                2: Player 2 wins. */
    public int move(int row, int col, int player) {
        int num = player == 1 ? 1 : -1;
        rows[row] += num;
        cols[col] += num;
        if (row == col) diagonal += num;
        if (row == size-1-col) antiDiagonal += num;
        if (Math.abs(rows[row]) == size ||
           Math.abs(cols[col]) == size ||
           Math.abs(diagonal) == size ||
           Math.abs(antiDiagonal) == size) return player;
        return 0;
    }
}

GPU云服务器云服务器 348元的云服务器 LeetCode LeetCode_String leetcode_35_SearchIn

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

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

348. Design Tic-Tac-Toe

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

betacat 2019-08-14 17:27 评论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
Leetcode PHP题解--D87 705. Design HashSet

摘要：题目链接题目分析设计一个哈希类。需要有添加元素函数，判断元素存在的函数，移除元素函数。思路这真的没什么好说的了我把要存的值作为数组的键存储。最终代码若觉得本文章对你有用，欢迎用爱发电资助。 D87 705. Design HashSet 题目链接 705. Design HashSet 题目分析设计一个哈希类。需要有add添加元素函数，contains判断元素存在的函数，remov...

why_rookie 2019-07-01 14:00 评论0 收藏0