Google Onsite 11.23

aiwojiujiu 发表于 2016-1-19 13:53
第二轮，可以用字典逆向构建tre，例如google，就在tre里面存入elgoog。
stream来的时候，从当前开始，向前 ...

这个思路好！赞！

pigmightfly 发表于 2016-1-19 18:28
只能走n步。
就是每个格子的步长不一样。
比如到A格子，步长是三步。在B格子，步长是两步。

原来如此 多谢楼主耐心解答 祝你在google 工作顺利！

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

aiwojiujiu 发表于 2016-1-20 09:41
楼主 按照你的描述 我的理解是：从一个格子，如果想走到其他周围四个格子的任意一个，需要走过的路程都是 ...

不不不，步长为3就是说可以走三个格子。或者你就理解为在不同的格子上单位时间内走的格子步数不一样

pigmightfly 发表于 2016-1-20 09:50
不不不，步长为3就是说可以走三个格子。或者你就理解为在不同的格子上单位时间内走的格子步数不一样

喔喔 那楼主的做法就是对每一个起始点开始，采用空间树的做法，枚举每一种下一时间的状况，看看最快到何时可以到某个G点吗？

aiwojiujiu 发表于 2016-1-20 09:57
喔喔 那楼主的做法就是对每一个起始点开始，采用空间树的做法，枚举每一种下一时间的状况，看看最快到何 ...

我觉得楼主应该依然是按照从G点开始的BFS策略吧？ 枚举下一层的所有情况，将加一层的所有能到的点的距离＋1

aiwojiujiu 发表于 2016-1-20 09:59
我觉得楼主应该依然是按照从G点开始的BFS策略吧？ 枚举下一层的所有情况，将加一层的所有能到的点的距离 ...

对对，是这样

pigmightfly 发表于 2015-12-9 12:00
map1 还是记录source string的char的位置
a: 0
b: 1

这个的前提应该是没有重复吧？

请问楼主 “如果每一步可走两步／三步怎么办？
如一步可走：左左，左上，右下，。。。
我说应该画出解空间树，然后DFS遍历解空间树”的意思是如果两步的话对于每个位置，计算（9 - 1） + 4个点吗？

根据JohnsonMS 的思想写了下代码

1. public class Square {
   
2.         static class Point {
   
3.                 int x;
   
4.                 int y;
   
5.                 public Point(int x, int y) {
   
6.                         this.x = x;
   
7.                         this.y = y;
   
8.                 }
   
9.         }
   
10.         public boolean isSquare(Point[] points) {
    
11.                 if (points == null || points.length != 4) {
    
12.                         return false;
    
13.                 }
    
14.                 List<Integer> dis = new ArrayList<Integer>();
    
15.                 for (int i = 0; i < points.length - 1; i++) {
    
16.                         for (int j = i + 1; j < points.length; j++) {
    
17.                                 dis.add(getDis(points[i], points[j]));
    
18.                         }
    
19.                 }
    
20.                 Collections.sort(dis);
    
21.                 if (dis.get(0) != dis.get(1) || dis.get(1) != dis.get(2) || dis.get(2) != dis.get(3) || dis.get(4) != dis.get(5)) {
    
22.                         return false;
    
23.                 } else {
    
24.                         return true;
    
25.                 }
    
26.         }
    
27.         private int getDis(Point point1, Point point2) {
    
28.                 return (int) Math.sqrt((point1.x - point2.x) * (point1.x - point2.x) + (point1.y - point2.y) * (point1.y - point2.y));
    
29.         }
    
30.        
    
31.         public static void main(String[] args) {
    
32.                 Square s = new Square();
    
33.                 Point[] points = {new Point(1, 1), new Point(2, 0), new Point(0, 1), new Point(1, 0)};
    
34.                 System.out.println(s.isSquare(points));
    
35.         }
    
36. }
    

复制代码