狗家昂赛特

jiongjiongyoush 发表于 2016-10-26 11:48
findEmptyNeighbor 没有return true的情况＝＝感觉把棋盘改了不太好
看来很精通围棋啊！棋盘大小都知道 ...

哦，应该在Line 8 and Line 9之间加上 “if (board[i][j] == 0) return true;” （空位找到）.  感谢指出！

这个围棋的算法其实只是“静态”的检查（无法知道下棋的时间顺序）也就是对当前棋子并不做validation。例如：
XXXXXXXXX
XOOOOOX
XOXOXOX
XOOOOOX
XXXXXXXXX
按照算法会认为连成一片的"O" 都是死棋，但在围棋实际中是不可能走到这一步了，因为"O"有至少2个“内眼”，这在围棋中是永活的好棋，因为“X”不可能同时活着占领多个"O"的“内眼”。

补充内容 (2016-10-26 12:32):
应该是board [ \i ] [ j ] == 0. [\i] 被自动认为是斜体的格式化了。

画三角形：LZ贴的图很直观！我估计应该是这个意思：假设给定一个类似于“void drawLine(const Pt& p1, const Pt& p2)”的API，我也是用的recursion.

1. typedef pair<double,double> Pt;
   
2. typedef vector<Pt> Tri;
   
3. typedef vector<Tri> Tris;
   
4. 
   
5. // assumed given API
   
6. void drawLine(const Pt& p1, const Pt& p2);
   
7. 
   
8. // utility function to draw a given triangle
   
9. void drawTri(const Tri& tri) {
   
10.   for (int i = 0; i < 3; i++) drawLine(tri[i%3], tri[(i+1)%3]);
    
11. }
    
12. 
    
13. // dfs routine to draw central triangle and collect
    
14. // 4 smaller triangles for each big trianlges
    
15. Tris dfs(const Tris& tris) {
    
16.   Tris res;   
    
17.   for (const auto& t:tris) {
    
18.     drawTri(t); Tri tri;
    
19.     // construct and draw central triangle
    
20.     for (int i = 0; i < 3; i++)
    
21.       tri.push_back(Pt((t[i%3].first+t[(i+1)%3].first)/2.0,(t[i%3].second+t[(i+1)%3].second)/2.0));
    
22.     drawTri(tri);
    
23.     // collect all 4 smaller triangles into result
    
24.     res.push_back(tri);   
    
25.     for (int i = 0; i < 3; i++) {
    
26.       res.push_back({t[i], res[0][i], res[0][(i+2)%3]});
    
27.     }
    
28.   }
    
29.   return res;
    
30. }
    
31. 
    
32. // main function to draw triangles with given depth
    
33. void drawTriangles(const Tri& tri, unsigned int depth) {
    
34.   Tris tris = { tri };
    
35.   while (depth-- > 0) tris = dfs(tris);
    
36. }

复制代码

第一题当年写过一个围棋game, 就是数气

jiongjiongyoush 发表于 2016-10-26 11:09
输入三个顶点和depth
输出一堆点
问somehow，用这些点两两连线把depth的图画出来

最后一题dp吧

zzgzzm 发表于 2016-10-26 12:39
画三角形：LZ贴的图很直观！我估计应该是这个意思：假设给定一个类似于“void drawLine(const Pt& p1, cons ...

思路是对的。。具体没细看
图是照抄三哥的＝＝

请问下楼主第三轮第一题，如果要删除的节点有孩子，那么孩子怎么处理？是把左右孩子作为新的root加入要返回tree的集合吗？

海盗包子 发表于 2016-10-27 02:56
请问下楼主第三轮第一题，如果要删除的节点有孩子，那么孩子怎么处理？是把左右孩子作为新的root加入要返回 ...

对，返回一堆tree

画三角形那道题可不可以理解为level order traversal 的变种，bfs那种的。据我观察，每加深一层，就是把一个当前的三角形分成三个三角形（中间的倒三角形不算，这样画出的边也没有重合）写了一下代码，constructor没有详写

1. public class Point {
   
2.         int x, y;
   
3.         public Point() {}
   
4. }
   
5. public class Triangle {
   
6.         Point A, B, C;
   
7.         public Triangle(Point A, Point B, Point C){}
   
8. }
   
9. public Point getMid(Point A, Point B) {
   
10.         int x = (A.x + B.x) / 2, y = (A.y + B.y) / 2; //不考虑double的情况
    
11.         return new Point(x, y);
    
12. }
    
13. 
    
14. public void drawLine(Point A, Point B) {}
    
15. public void drawTri(Triangle tri) {
    
16.         drawLine(tri.A, tri.B);
    
17.         drawLine(tri.B, tri.C);
    
18.         drawLine(tri.A, tri.C);
    
19. }
    
20. public void drawGraph(Point A, Point B, Point C, int depth) {
    
21.         Triangle basic = new Triangle(A, B, C);
    
22.         Queue<Triangle> q = new LinkedList<Triangle>();
    
23.         q.offer(basic);
    
24.         for(int i = 0; i < depth; i++) {
    
25.                 int size = q.size();
    
26.                 for(int j = 0; j < size; j++) {
    
27.                         basic = q.poll();
    
28.                         Point mid_AB = getMid(basic.A, basic.B);
    
29.                         Point mid_AC = getMid(basic.A, basic.C);
    
30.                         Point mid_BC = getMid(basic.B, basic.C);
    
31.                         q.offer(new Triangle(basic.A, mid_AC, mid_AB));
    
32.                         q.offer(new Triangle(basic.B, mid_BC, mid_AB));
    
33.                         q.offer(new Triangle(basic.C, mid_BC, mid_AC));
    
34.                 }
    
35.         }
    
36.         while(!q.isEmpty()) {
    
37.                 drawTri(q.poll());
    
38.         }
    
39. }

复制代码

chestnut9919 发表于 2016-10-26 10:56
我明白啦！多谢！

你啥时候面啊？最近老在面经看到你

laiguojiuhao 发表于 2016-10-27 04:07
你啥时候面啊？最近老在面经看到你

这周五~~~