Google Onsite 11.23

请问楼主 “如果每一步可走两步／三步怎么办？
如一步可走：左左，左上，右下，。。。
我说应该画出解空间树，然后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. }
    

复制代码

bobzhang2004 发表于 2016-1-26 12:49
这个的前提应该是没有重复吧？

有重复也可以

bobzhang2004 发表于 2016-1-26 12:52
请问楼主 “如果每一步可走两步／三步怎么办？
如一步可走：左左，左上，右下，。。。
我说应该画出解空 ...

是这样的，不过说下思路就行，面试的时候不用写出代码哈～

请问第一个BFS不需要记住每一个G点是不是走过吗？

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

您好，我想问问这一个问题。他不是要求不能回头的么？ 能不能详细说一说。十分感谢。

jujujuhuakai 发表于 2016-4-25 23:00
您好，我想问问这一个问题。他不是要求不能回头的么？ 能不能详细说一说。十分感谢。

这个应该都不能回头，自己可以用一个buffer

Effiel 发表于 2016-4-26 09:47
这个应该都不能回头，自己可以用一个buffer

对的，不能回头，所以自己要用buffer存起来。

正方形的题
先选一个点P1
算P1到P2, P3, P4的距离平方，
看看这三个值是不是两个小的相等，大的那个是小的两倍。
然后假设大的那个值是P1-P4，那么再算P2-p4是否也等于P1-P2
最后还要记得判断下P2是否不等于P3

迷宫的题，follow up也用BFS就好.