X

LEETCODE 1275. Find Winner on a Tic Tac Toe Gam 解题思路分析

题目大意:

找出井字棋的获胜者

AB 在一个 3 x 3 的网格上玩井字棋。

井字棋游戏的规则如下:

  • 玩家轮流将棋子放在空方格 (” “) 上。
  • 第一个玩家 A 总是用 “X” 作为棋子,而第二个玩家 B 总是用 “O” 作为棋子。
  • “X” 和 “O” 只能放在空方格中,而不能放在已经被占用的方格上。
  • 只要有 3 个相同的(非空)棋子排成一条直线(行、列、对角线)时,游戏结束。
  • 如果所有方块都放满棋子(不为空),游戏也会结束。
  • 游戏结束后,棋子无法再进行任何移动。

给你一个数组 moves,其中每个元素是大小为 2 的另一个数组(元素分别对应网格的行和列),它按照 A 和 B 的行动顺序(先 A 后 B)记录了两人各自的棋子位置。

如果游戏存在获胜者(A 或 B),就返回该游戏的获胜者;如果游戏以平局结束,则返回 “Draw”;如果仍会有行动(游戏未结束),则返回 “Pending”。

你可以假设 moves 都 有效(遵循井字棋规则),网格最初是空的,A 将先行动。

示例 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 遵循井字棋的规则。

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1275

解题思路分析:

这周Leetcode连续出的两道题都让我怀念起小学生活。记得上小学时经常和同桌玩这个井字棋游戏。(另外一题:LEETCODE 1276. Number of Burgers with No Waste of Ingredients 解题思路分析

本题的棋盘是·3 * 3的矩阵,存在8条长度为3的线路,横向3条,纵向3条以及2条对角线。我们可以先循环一遍 moves 数组,将2个玩家的棋局还原。新建一个3 * 3的二维数组,玩家A走的位置记入1,玩家B走的位置记录4。循环结束后,我们可以在棋盘上清晰的看出每个玩家走过的位置。在8条线路中,如果某一条线路上的数值和为3,说明A获胜,如果和为12,B获胜。如果2人都没有获胜,说明不是平局就是还没下完,判断是否下完很简单,只要看 moves 数组的长度,即2人一共走过的步数即可。如果步数小于9,说明棋局还没有结束。反之则代表平局。

另外解释一下,上面提到的,为什么A玩家用1表示,B玩家用4表示?原因是我们最后要在一条直线上求和,如果使用数字1和2分别代表2个人的话,A获胜时,线路上的和应为3,B获胜时应为6,但是,如果一条线上的数字是1,2,0时,和也是3,我们就无法判断出是哪种情况了。

实现代码:

public String tictactoe(int[][] moves) {
    int[][] map =new int[3][3]; // 棋盘
    // 复盘棋局
    for(int i =0;i<moves.length;i++){
        int r =moves[i][0];
        int c= moves[i][1];
        map[r][c]= i%2 == 0 ? 1 : 4;
    }
    // 查看3条横线和3条纵线上是否有人获胜
    for(int i=0;i<3;i++){
        int sum1=map[i][0]+map[i][1]+map[i][2];
        if(sum1==3) return "A";
        if(sum1==12) return "B";
        int sum2=map[0][i]+map[1][i]+map[2][i];
        if(sum2==3) return "A";
        if(sum2==12) return "B";
    }
    // 查看2条对角线上是否有人获胜
    int sum3=map[0][0]+map[1][1]+map[2][2];
    if(sum3==3) return "A";
    if(sum3==12) return "B";
    int sum4=map[0][2]+map[1][1]+map[2][0];
    if(sum4==3) return "A";
    if(sum4==12) return "B";
    // 如果没人获胜,当前棋局走完的情况下是平局,反之是棋局还没下完
    return moves.length==9?"Draw":"Pending";
}

本题解法执行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Find Winner on a Tic Tac Toe Game.

Memory Usage: 34.5 MB, less than 100.00% of Java online submissions for Find Winner on a Tic Tac Toe Game.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1275-find-winner-on-a-tic-tac-toe-gam-解题思路分析/
Categories: leetcode
kwantong: