📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 5342| 回复: 22
跳转到指定楼层
上一主题 下一主题
收起左侧

[高频题] 围棋

全局:
高频题
公司名称: google

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x

您好!
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 150 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Popular Interview Questions from Top Companies


上一篇:链表类的题应该怎么做
下一篇:计算器类
Warald 2019-3-8 06:15:33 | 只看该作者
全局:
关于双倍积分奖励算法题和系统设计题讨论的决定:

我们:
1. 希望能看到干货讨论;
2. 希望能看到好的代码(web端高级发帖模式下,@ 朋友右边的<> 可以选择多种代码)

版主 @14417335 负责审核加分,也请大家给好的回复加分 + 顶。
大家给30,我会跟进奖励30,double之;
大家给100,我也会跟进奖励100,double之。

很理解大家写代码、调试、写思路分析,很花时间。对于特别好的回复,还会有额外加分。

欢迎大家拿出好的题目讨论,选中了我会全站置顶。哪位同学起了好的题目/帖子,激发了干货讨论,也会获得一定的积分奖励。

欢迎大家踊跃参与。看到好的回复,也请大家顶一下,作为对别人积极参与讨论、热心分享的认可和鼓励。
其他可以获得双倍积分的题目:

在刷题版里选择高频题标签,版主@14417335 发的所有帖子,链接:
https://www.1point3acres.com/bbs/forum.php?mod=forumdisplay&fid=84&filter=typeid&typeid=1019

大家看到LC没有的高频题,也请贴到刷题版里,又有大米又有赞。对于学弟学妹们也是功劳一件。举手之劳。谢谢大家的参与。


回复

使用道具 举报

推荐
zlfp 2019-3-12 08:17:39 | 只看该作者
全局:
我来简单介绍一下围棋的规则。(以下以白棋举例)
1,如果一个白棋放在棋盘上且不与其它白棋相连,这个棋子上下左右紧邻的可以放子的地方被称为这个白棋的“气”。显然,如果这个棋子的上下左右紧邻的点被黑棋占领,它的气的数量会减小。如果这个白棋本身在边或者角上,气先天比在中央的(上下左右有四个相邻的“气”)白棋要小一些(边是3, 角是2)。
2,如果是一块白棋,在围棋规则中,会把这一块白棋作为一个整体。这时则要考虑的是这一整块白棋的气。这时这一块白棋的气的计算方法为:这块棋子所有的白棋的气的总和(显然,中间的白棋为0气,只有外边的会贡献)。

“气”在围棋中是一个很重要的概念。如果一块/个棋子的气为0,则代表这个棋子已经“死”了,需要从棋盘上取出来。

评分

参与人数 3大米 +11 收起 理由
starzero + 1 给你点个赞!
admin + 5
14417335 + 5 很有用的信息!

查看全部评分

回复

使用道具 举报

全局:
规则是按围棋规则来的,需要干两件事:1找气 2找敌人(需要validate敌人, 如果敌人外面一圈被包了,敌人是无效的)。跑过了几个testcases,欢迎讨论。
  1. public class Chess {
  2.     class ResultType {
  3.         boolean foundAir, foundEnemy;
  4.         public ResultType(boolean foundAir, boolean foundEnemy) {
  5.             this.foundAir = foundAir;
  6.             this.foundEnemy = foundEnemy;
  7.         }
  8.     }
  9.     int[] dx = {1, 0, 0, -1};
  10.     int[] dy = {0, 1, -1, 0};
  11.     // 1 black, 0 while, 2 air
  12.     public boolean isAlive(int[][] board, int i, int j) {
  13.         // validate given location, outOfBoard || foundAir
  14.         if (!inbound(board, i, j) || board[i][j] == 2) return false;
  15.         int val = board[i][j];
  16.         ResultType ans = findEmptyNeighbor(board, i, j, val);
  17.         return ans.foundAir || !ans.foundEnemy;
  18.     }
  19.     private ResultType findEmptyNeighbor(int[][] board, int x, int y, int val) {
  20.         boolean foundAir = false;
  21.         boolean foundEnemy = false;
  22.         // found air
  23.         if (board[x][y] == 2) return new ResultType(true, foundEnemy);
  24.         // found enemy
  25.         if (board[x][y] == 1 - val) {
  26.             // validate enemy
  27.             board[x][y] = Integer.MAX_VALUE;
  28.             boolean enemyFoundEnemy = false;
  29.             for (int k = 0; k < dx.length; k++) {
  30.                 int xx = x + dx[k];
  31.                 int yy = y + dy[k];
  32.                 if (!inbound(board, xx, yy) || board[xx][yy] == Integer.MAX_VALUE) continue;
  33.                 ResultType enemyChild = findEmptyNeighbor(board, xx, yy, 1 - val);
  34.                 foundEnemy |= enemyChild.foundAir;
  35.                 enemyFoundEnemy |= enemyChild.foundEnemy;
  36.             }
  37.             // two enemy valid conditions: 1. enemy find Air 2. enemy find no its enemy
  38.             foundEnemy |= !enemyFoundEnemy;

  39.             return new ResultType(foundAir, foundEnemy);
  40.             //return false;
  41.         }
  42.         // found its kind
  43.         board[x][y] = Integer.MAX_VALUE;
  44.         for (int k = 0; k < dx.length; k++) {
  45.             int xx = x + dx[k];
  46.             int yy = y + dy[k];
  47.             if (!inbound(board, xx, yy) || board[xx][yy] == Integer.MAX_VALUE) continue;
  48.             ResultType child = findEmptyNeighbor(board, xx, yy, val);
  49.             foundAir |= child.foundAir;
  50.             foundEnemy |= child.foundEnemy;
  51.         }
  52.         return new ResultType(foundAir, foundEnemy);
  53.     }
  54.     private boolean inbound(int[][] board, int i, int j) {
  55.         return i >= 0 && i < board.length && j >= 0 && j < board[0].length;
  56.     }
  57. }

  58. class Main{
  59.     public static void main(String[] args) {
  60.         int[][] board = {{1,1,1,1},
  61.                          {1,1,1,1},
  62.                          {1,1,0,1},
  63.                          {1,1,1,1}};
  64.         int[][] board1 = {{1,1,1,1},
  65.                           {1,1,1,1},
  66.                           {1,2,0,1},
  67.                           {1,1,1,1}};
  68.         int[][] board2 = {{0,0,0,0,0},
  69.                           {0,1,1,1,0},
  70.                           {0,1,0,1,0},
  71.                           {0,1,1,1,0},
  72.                           {0,0,0,0,0}};
  73.         int[][] board3 = {{1,1,1,1,1,1,1},
  74.                           {1,0,0,0,0,0,1},
  75.                           {1,0,1,1,1,0,1},
  76.                           {1,0,1,0,1,0,1},
  77.                           {1,0,1,1,1,0,1},
  78.                           {1,0,0,0,0,0,1},
  79.                           {1,1,1,1,1,1,1}};
  80.         Chess test = new Chess();
  81.         System.out.println(test.isAlive(board, 2,2)? "Alive": "Dead");
  82.         System.out.println(test.isAlive(board1, 2,2)? "Alive": "Dead");
  83.         System.out.println(test.isAlive(board2, 2,2)? "Alive": "Dead");
  84.         System.out.println(test.isAlive(board3, 2,2)? "Alive": "Dead");
  85.     }
  86. }
复制代码

评分

参与人数 3大米 +21 收起 理由
starzero + 1 给你点个赞!
admin + 10
14417335 + 10 给你点个赞!

查看全部评分

回复

使用道具 举报

🔗
t60651 2019-3-12 05:59:06 | 只看该作者
全局:
这个题说的非常不清楚,主要取决于“被包围”的定义是什么,尤其是对于我这种没有任何围棋知识的人。4个方向算包围?还是8个方向?
如果是必须被另一种颜色的棋完全包围,可以bfs从当前的棋扩展找相邻的自己颜色的棋或者空的位置。 如果碰不到4个边界,即为被包围了,反之没有被包围。
如果边界也算上的话,则还是刚才的扩展方法,计数能扩展多少个位置,再按“被包围”的定义做决定。
感觉这种题不难。由于题意不清楚,也没法写代码了。
提供一个向4个方向扩展的比较简洁的方法(只用1维数组):
int[] dir = {0, 1, 0, -1, 0};
for(int k=0;k<4;++i)
{
  int x = dir[0];
  int y = dir[1];
}

评分

参与人数 2大米 +20 收起 理由
admin + 10
14417335 + 10 给你点个赞!

查看全部评分

回复

使用道具 举报

🔗
t60651 2019-3-12 06:01:03 | 只看该作者
全局:
抱歉上面打错了。。。
int[] dir = {0, 1, 0, -1, 0};
for(int k=0;k<4;++i)
{
  int x = dir[k];
  int y = dir[k+1];
}
回复

使用道具 举报

🔗
 楼主| 14417335 2019-3-12 08:39:30 | 只看该作者
全局:
zlfp 发表于 2019-3-12 08:17
我来简单介绍一下围棋的规则。(以下以白棋举例)
1,如果一个白棋放在棋盘上且不与其它白棋相连,这个棋 ...

在楼顶第二个例子里,被围的1中又围住了0,那么如果要把0干掉,而0又要死缠烂打,最后可能剩不下几个气。

是只要1能活就整个1这个岛屿的大小都算到成绩里,还是算最后1中的气?
回复

使用道具 举报

🔗
zlfp 2019-3-12 08:48:18 | 只看该作者
全局:
14417335 发表于 2019-3-12 08:39
在楼顶第二个例子里,被围的1中又围住了0,那么如果要把0干掉,而0又要死缠烂打,最后可能剩不下几个气。 ...

在第二个例子里面,当前状态下1和0都没有死,因为他们当前都还有气。
最终到底是谁死谁活需要收气(也就是双方博弈,都按照最优走,最终慢了一气的棋子输)。
因此在围棋中有个概念叫做“眼”,只要有两个眼位就能保证这块棋永远不被吃掉

评分

参与人数 2大米 +10 收起 理由
admin + 5
14417335 + 5 给你点个赞!

查看全部评分

回复

使用道具 举报

🔗
zlfp 2019-3-12 08:49:11 | 只看该作者
全局:
如果是按照围棋规则中被“围死”完全没有气的那种被称作“包围”的话,用简单的BFS即可,我这里简单写了一个例子。

  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>

  4. using namespace std;

  5. class Solution {
  6. private:
  7.     vector<int> dx = {0, 0, -1, 1};
  8.     vector<int> dy = {-1, 1, 0, 0};
  9. public:
  10.     bool isSurround(vector<vector<int>>& grid, int x, int y) {
  11.         // 0: none, 1: white chess, 2: black chess
  12.         int n = grid.size(), m = grid[0].size();
  13.         int color = grid[x][y];


  14.         vector<vector<int>> visited(n, vector<int>(m, 0));
  15.         queue<pair<int, int>> q;

  16.         q.push({x, y});
  17.         visited[x][y] = 1;
  18.         
  19.         while (!q.empty()) {
  20.             auto p = q.front();
  21.             q.pop();
  22.             // current chess
  23.             int cx = p.first, cy = p.second;
  24.             
  25.             for (int i = 0; i < 4; ++i) {
  26.                 // new chess
  27.                 int nx = cx + dx[i], ny = cy + dy[i];
  28.             
  29.                 // if adjacent chess is in board and hasn't been visited before
  30.                 if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny]) {
  31.                     // if adjacent is empty, return false
  32.                     if (grid[nx][ny] == 0) {
  33.                         return false;
  34.                     }
  35.                     // otherwise push it into queue
  36.                     if (grid[nx][ny] == color) {
  37.                         visited[nx][ny] = 1;
  38.                         q.push({nx, ny});
  39.                     }
  40.                 }
  41.             }
  42.         }
  43.         return true;
  44.     }
  45. };

  46. int main() {
  47.     Solution sol = Solution();
  48.     int x, y;
  49.     // test case 1:
  50.     vector<vector<int>> grid1 = {{0,0,0,0},{1,1,1,0},{1,2,1,0},{0,1,1,0}}; // true
  51.     cout << sol.isSurround(grid1, 2, 1) << endl;
  52.     // test case 2:
  53.     vector<vector<int>> grid2 = {{0,0,0,0},{1,1,1,0},{2,2,1,0},{0,1,1,0}}; // false
  54.     cout << sol.isSurround(grid2, 2, 1) << endl;
  55.     return 0;
  56. }
复制代码

评分

参与人数 2大米 +40 收起 理由
admin + 20
14417335 + 20 给你点个赞!

查看全部评分

回复

使用道具 举报

🔗
zlfp 2019-3-12 08:51:12 | 只看该作者
全局:
zlfp 发表于 2019-3-12 08:48
在第二个例子里面,当前状态下1和0都没有死,因为他们当前都还有气。
最终到底是谁死谁活需要收气(也就 ...

互相包围双方都没有眼时还有一种有趣的状态叫做“双活”,是指就算互相均按照最优下,也可能谁也吃不了谁的状态。当然这个和之前说的两眼活棋都和本文没有什么关系。
回复

使用道具 举报

🔗
adh360 2019-3-12 09:48:39 | 只看该作者
全局:
这个题如果较真,感觉是个无底洞,估计可以几个小时不写代码,光讨论各种情况就时间用完了(什么棋的死活,一层围一层的情况),估计还是得限定情况,只能先把最简单的写出来然后慢慢扩展
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表