LeetCode1275-找出井字棋的获胜者 Kotlin

> A 和 B 在一个 3 x 3 的网格上玩井字棋。 > > 井字棋游戏的规则如下： > > 玩家轮流将棋子放在空方格 (" ") 上。 > 第一个玩家 A 总是用 "X" 作为棋子，而第二个玩家 B 总是用 "O" 作为棋子。 > "X" 和 "O" 只能放在空方格中，而不能放在已经被占用的方格上。 > 只要有 3 个相同的（非空）棋子排成一条直线（行、列、对角线）时，游戏结束。 > 如果所有方块都放满棋子（不为空），游戏也会结束。 > 游戏结束后，棋子无法再进行任何移动。 > 给你一个数组 moves，其中每个元素是大小为 2 的另一个数组（元素分别对应网格的行和列），它按照 A 和 B 的行动顺序（先 A 后 B）记录了两人各自的棋子位置。 > > 如果游戏存在获胜者（A 或 B），就返回该游戏的获胜者；如果游戏以平局结束，则返回 "Draw"；如果仍会有行动（游戏未结束），则返回 "Pending"。 > > 你可以假设 moves 都 有效（遵循井字棋规则），网格最初是空的，A 将先行动。 > > 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
示例 1：

输入：moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
输出："A"
解释："A" 获胜，他总是先走。
"X  "    "X  "    "X  "    "X  "    "X  "
"   " -> "   " -> " X " -> " X " -> " X "
"   "    "O  "    "O  "    "OO "    "OOX"
示例 2：

输入：moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]]
输出："B"
解释："B" 获胜。
"X  "    "X  "    "XX "    "XXO"    "XXO"    "XXO"
"   " -> " O " -> " O " -> " O " -> "XO " -> "XO " 
"   "    "   "    "   "    "   "    "   "    "O  "
示例 3：

输入：moves = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]]
输出："Draw"
输出：由于没有办法再行动，游戏以平局结束。
"XXO"
"OOX"
"XOX"
示例 4：

输入：moves = [[0,0],[1,1]]
输出："Pending"
解释：游戏还没有结束。
"X  "
" O "
"   "
 

提示：

1 <= moves.length <= 9
moves[i].length == 2
0 <= moves[i][j] <= 2
moves 里没有重复的元素。
moves 遵循井字棋的规则。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-winner-on-a-tic-tac-toe-game
> >

题目有点像五子棋，看哪一方先获胜，有一点需要注意，已经明确了此棋盘是一个3*3的棋盘，我看到一个用位运算的题解，我研究了一下，模仿着写了一下，下面是我提交通过的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    fun tictactoe(moves: Array<IntArray>): String {
        var a = 0
        var b = 0
        val acList = arrayListOf(7, 56, 448, 73, 146, 292, 273, 84)
        for (i in moves.indices) {
            if (i % 2 == 0) {
                a = a xor (1 shl (3 * moves[i][0] + moves[i][1]))
            }else{
                b = b xor (1 shl (3 * moves[i][0] + moves[i][1]))
            }
        }
        for (ac in acList){
            if ((a and ac) == ac){
                return "A"
            }else if ((b and ac) == ac){
                return "B"
            }
        }
        return when {
            moves.size == 9 -> "Draw"
            else -> "Pending"
        }
    }
}

这里是题解的链接：https://leetcode-cn.com/problems/find-winner-on-a-tic-tac-toe-game/solution/java-wei-yun-suan-xiang-jie-shi-yong-wei-yun-suan-/

抛开题解人的解释，我来根据我自己研究出来的结论分析一下这个解答吧

  • 初始化

    • 首先可以固定的是这个棋盘有9个格子，所以，初始化a用户为000000000 ，b用户为000000000

    • 计算棋子在3* 3正方形棋盘中的位置，大家应该都知道就是3*x + y+1（x为横坐标，y为纵坐标）

    • 我们把坐标如果用二进制来表示一个九个坐标，则位置1可以表示为：000000001；位置2可以表示为000000010；位置3可以表示为000000100，依次类推

    • 所以棋子下落的位置我们可以用二进制来表示这里就用到了位运算，当棋子下落到哪个位置，我们就1左移多少 例如1 << 0 结果为00000001 ;1<<5 结果为000010000

    • 固定格子说明成功的次数是固定的即3种横+33种竖+22种对角这里直接借鉴原题解人的方法：

      • 计算举例：{[0,0],[0,1],[0,2]}{[0,0],[0,1],[0,2]}为横的一种赢面，对应的99位二进制数为000000111000000111，即十进制下的7

      • 事实上，由对应规则可以得知：

        • 33种横的赢面数字是公比为88的等比数列

        • 33种竖的赢面数字是公比为22的等比数列

        • 总共只需要计算出44个数字(11种横+11种竖+22种对角)，其余按倍数推导即可

          所有赢面数字分别为7, 56(即7\times 8), 448(即7\times 8^2), 73, 146(即73\times 2), 292(即73\times

          2^2), 273, 847,56(即7×8),448(即7×8^2),73,146(即73×2),292(即73×2^2),273,84

  • 开始走棋

  • 走棋：每次走一个棋子都用当前坐标去异或要走的坐标，原因是什么呢，因为我们要走的棋子坐标是唯一的，异或（^）情况是两位相同则为0，不同则为1，其实这里用或（|）也是可以的，因为只要保证此时能够记录下走过的步数就可以。

    举个栗子：a第一次走的1 即000000001 ，第二次走的3即000000100，此时两个异或得到000000101，用或也可以得到相同的结果

  • 比较：把a，b所有走过的步数记下来之后，就要和能够胜利的情况作比较了，这时候使用的是且（&），为什么用&呢？

    胜利的情况其实分两种情况：第一种是刚好走三步，第二种是走了超过三步；举个栗子000000111和100000111都是胜利了，此时aclist中存的这种情况的胜利是000000111，所以用且（&）即 a & ac ==ac的情况是胜利

    • 善后：还有两种情况两方都没有取胜，此时如果长度两方把棋盘下满则为平局（Draw）若还没有把棋盘下满则显示（Pending）

    以上就是我对此题目的分析，尽量做到通俗易懂，位运算是个很有意思的东西，并且效率出奇的高，所以可以平时多注意使用一下，如有疑问欢迎在下方留言，留言带着自己的邮箱，以便我回复后能够及时的通知到你