优化 Leaper Graph 算法？

Question

在 Google 的 45 分钟技术面试中，我被问到 Leaper Graph 问题。我写了工作代码，但后来因为缺乏数据结构知识而被拒绝了工作机会。我想知道我可以做得更好。

问题如下： "Given an N sized board, and told that a piece can jump i positions horizontally (left or right) and j positions vertically (up or down) (I.e, sort of like a horse in chess), can the leaper reach every spot on the board?"

我写了下面的算法。它通过标记图表上所有被访问过的点来递归地找出板上的每个位置是否都可以到达。如果无法访问，则至少有一个字段为假，函数将 return 为假。

      static boolean reachable(int i, int j, int n) {
        boolean grid[][] = new boolean[n][n];
        reachableHelper(0, 0, grid, i, j, n - 1);
        for (int x = 0; x < n; x++) {
          for (int y = 0; y < n; y++) {
            if (!grid[x][y]) {
              return false;
            }
          }
        }
        return true;
      }

      static void reachableHelper(int x, int y, boolean[][] grid, int i, int j, int max) {
        if (x > max || y > max || x < 0 || y < 0 || grid[x][y]) {
          return;
        }
        grid[x][y] = true;
        int i2 = i;
        int j2 = j;
        for (int a = 0; a < 2; a++) {
          for (int b = 0; b < 2; b++) {
            reachableHelper(x + i2, y + j2, grid, i, j, max);
            reachableHelper(x + j2, y + i2, grid, i, j, max);
            i2 = -i2;
          }
          j2 = -j2;
        }
      }

现在，后来有人指出，最佳解决方案是实施 Donald Knuth 的互素实施： http://arxiv.org/pdf/math/9411240v1.pdf 这是一个人应该能够在 45 分钟的技术面试中弄清楚的东西吗？？

除了以上，还有什么可以做得更好的吗？

编辑：
- 我询问了起始位置。有人告诉我从 0,0 开始就可以了。

edit2 根据反馈，我用队列方法写了一个 while-loop。当 n = 85 时，递归方法会遇到堆栈溢出。但是，下面使用队列方法的 while 循环最多可以达到 ~n = 30,000。（之后它遇到内存超过 GB 的堆问题）。如果您知道如何进一步优化，请告诉我。

    static boolean isReachableLoop(int i, int j, int n) {
        boolean [][] grid = new boolean [n][n];

        LinkedList<Point> queue = new LinkedList<Point>();
        queue.add(new Point(0,0)); // starting position. 

        int nodesVisited = 0;
        while (queue.size() != 0) {
          Point pos = queue.removeFirst();

          if (pos.x >= 0 &&  pos.y >= 0 && pos.x < n && pos.y < n) {
            if (!grid[pos.x][pos.y]) {
              grid[pos.x][pos.y] = true;
              nodesVisited++;
              int i2 = i;
              int j2 = j;
              for (int a = 0; a < 2; a++) {
                for (int b = 0; b < 2; b++) {
                  queue.add(new Point(pos.x+i2, pos.y+j2));
                  queue.add(new Point(pos.x+j2, pos.y+i2));
                  i2 = -i2;
                }
                j2 = -j2;
              }
            }
          }
        }
        if (nodesVisited == (n * n)) {
          return true;
        } else {
          return false;
        }
      }

Answer 1

对不起，我觉得我错过了什么。

如果你只能向上或向下移动 i 和向左或向右移动 j，那么如果存在整数 m 和 n，则从起始情况 (a,b) 可以到达情况 (x,y)，以便

a + m*i = x

b + n*j = y

也就是说，对于 n > 1 的方板，一切都是错误的。

如果你的意思更像是国际象棋中的骑士，你可以 up/down 由 i 和 left/right 由 j 或 up/down 由 j 和 left/right 由 i ，您可以使用相同的技术。它只是变成了 2 个方程来解决：

a + m * i + n * j = x

b + o * i + p * j = y

如果没有满足这些方程的整数 m、n、o 和 p，则您无法达到该点。

Answer 2

我问了很多这样的面试问题。我不认为你会在面试中弄清楚互质方法，但我会因为你使用 O(n^2) 堆栈 space 而对你进行停靠——特别是因为你将所有这些参数传递给了每个递归调用而不是使用对象。

我会问你这个问题，并希望你提出使用堆上的堆栈或队列的 BFS 或 DFS。如果你在这方面失败了，我可能会像 "lacked data structure knowledge".

这样投诉

我还会问一些问题，以确保您在分配该二维数组时知道自己在做什么。

如果你真的很厉害，我会问你是否可以利用问题的对称性来减少你的搜索space。你真的只需要搜索一个 J*J 大小的网格（假设 J>=i）。

重要的是要记住面试官不只是看你的答案。他关注的是您解决问题的方式以及您大脑中有哪些工具可以用来解决问题。

编辑：再考虑一下，在通往互质方法的过程中有很多增量步骤，您可能还会想出这些步骤。没有人会想到，但这会令人印象深刻！

优化 Leaper Graph 算法？

Optimize Leaper Graph algorithm?

java

algorithm

recursion

knuth

dynamic-programming