Google – Adjacent Points of K dimensional

Google – Adjacent Points of K dimensional
Given a point in k dimension vector, find all adjacent points.
For example:
(0, 0) is a point in 2-dimension, then the adjacent points are
[(0, -1), (0, 1), (1, -1), (1, 0), (1, 1), (-1, -1), (-1, 0), (-1, 1)]
[Solution]
这道题乍一看根本没有任何想法，但是知道答案之后又有种恍然大悟"其实也就这样吧"的感觉。。可是面试题往往就这样，难是不会难到哪里去的，重点就看思路能不能想到对的点上。
其实这道题就是一道普通的backtracking题，无论有多少dimension，它的邻接点无非就是每个坐标+1，-1和保持原样三种变化。直接backtracking就好了。
所以对于k dimension中的一个点，它的邻接点一共有3^k – 1个。
你说难么？不难啊！这种backtracking代码写写几分钟的事情。可是怎么从一道看似几何的题目想到传统的backtracking上呢？这种技能点还得多练练。

  public List<List<Integer>> adjacentPoints(List<Integer> point) {

    List<List<Integer>> result = new LinkedList<>();

    if (point == null || point.isEmpty()) {

      return result;

    }

 

    List<Integer> tmp = new ArrayList<>(point);

    dfs(point, tmp, 0, result);

    return result;

  }

 

  private boolean isSame(List<Integer> a, List<Integer> b) {

    if (a.size() != b.size()) {

      return false;

    }

    for (int i = 0; i < a.size(); i++) {

      if (a.get(i) != b.get(i)) {

        return false;

      }

    }

    return true;

  }

 

  private void dfs(List<Integer> point, List<Integer> tmp, int pos, List<List<Integer>> result) {

    if (pos == tmp.size()) {

      if (!isSame(point, tmp)) {

        result.add(new ArrayList<>(tmp));

      }

      return;

    }

 

    // 0

    dfs(point, tmp, pos + 1, result);

 

    int save = tmp.get(pos);

 

    // -1

    tmp.set(pos, save - 1);

    dfs(point, tmp, pos + 1, result);

 

    // +1

    tmp.set(pos, save + 1);

    dfs(point, tmp, pos + 1, result);

 

    // recover

    tmp.set(pos, save);

  }

Read full article from Google – Adjacent Points of K dimensional