TheRoom

在写算法的时候看到一个非常厉害的活用语言特性的例子, 暗叹今天又没白活, 赶紧记录下来.

原题

链接: https://leetcode.cn/problems/shift-2d-grid/submissions/

二维网格迁移, 思路不难, 本质上就是找两个坐标之间的映射关系.

算法

一顿操作猛如虎, 写得如下解法:

// 10ms 20.32%
public List<List<Integer>> shiftGrid(int[][] grid, int k) {
  // 行数量 m, 列数量 n
  int m = grid.length, n = grid[0].length;
  int[][] target = new int[m][n];
  int a, b;
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
      b = (j + k) % n;
      a = ((j + k) / n + i) % m;
      // System.out.printf("(%d,%d)->(%d,%d)\n",i,j,a,b);
      target[a][b] = grid[i][j];
    }
  }
  List<List<Integer>> res = new ArrayList<>((int) (m / 0.75) + 1);
  for (int[] ints : target) {
    List<Integer> re = Arrays.stream(ints).boxed().toList();
    res.add(re);
  }
  return res;
}

提交顺利通过, 然而花了 10ms, 只超过 20.32% 的提交, 看到居然还有提交是 1ms 的, 我不免疑惑: 这个白开水式的算法还能怎么优化?

巧妙的优化

一看大神的提交, 茅塞顿开, 马上对着我的代码进行了一轮 refine:

// 2ms 99.77%
public List<List<Integer>> shiftGrid2(int[][] grid, int k) {
  // 行数量 m, 列数量 n
  int m = grid.length, n = grid[0].length;
  int[][] target = new int[m][n];
  int a, b;
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
      b = (j + k) % n;
      a = ((j + k) / n + i) % m;
      // System.out.printf("(%d,%d)->(%d,%d)\n",i,j,a,b);
      target[a][b] = grid[i][j];
    }
  }
  List res = Arrays.asList(target);
  return res;
}

顺利跻身前 1%.

显而易见, 这个场景下影响效率的主要问题就是输出结果的构建.

由于 Java 泛型有类型擦除的特性, 方法的返回值哪怕显式写明了List<List<Integer>> , 真正在运行时 JVM 也只能认得 List<?>, 这就给了我们偷懒的机会: 跳过繁琐的构建返回值的过程, 直接使用 Arrays.asList() 的结果作为返回值.

实际上 Arrays.asList(target) 的返回值类型为 List<int[]> , 到此不免有些好奇, List<int[]> 能顺利代替 List<List<Integer>> 吗?

这就要看 leetcode 的 online judge 是怎么设计和实现的了, 如果判题逻辑不涉及到 List 相对于 int[] 的独有特性, 同时也没有强转操作, 那么是没有问题的. 从提交结果上看来确实如此, 猜测在判题的时候也仅仅是使用类似 for(Integer a: A) 这种方式去遍历, 恰好 Integer 与 int 之间的转换也会自动拆装箱, 所以一切看来都是那么完美砌合.

就好比你在富士康组装手机, 你大姨正好手机掉了, 需要一台新手机, 你直接利用职务之便直接从最终的流水线上拿了一台送给你大姨, 除了没有经过正式包装, 和别人买的成品没什么不同.

这个算法的例子中, 巧妙已经不局限于算法本身了, 甚至到了语言特性上, 可以说是非常大胆和发散了.

不过有必要强调一下, 这种取巧是不能用在工程项目中的, 工程项目中必然要追求严谨性和确定性, 你的代码定义了什么返回类型, 给的就必须是什么返回类型, 因为当代码不是由你一个人写时, 就要站在工程学的角度上想问题, 多为别人考虑, 避免不必要的错误.

1260_二维网格迁移

原题

算法

巧妙的优化

评论