大家好，我是渡一前端子辰老师。

今天来给大家分享的是一道非常有意思的算法笔试题。他精准地考察了你对二维数组“坐标”的认知和理解。

快来测试一下自己的逻辑能力吧

如上图所示，这道题要求我们生成一个二维数组，这里边的数字是呈漩涡状一直到数组的中心。

然后让你写一个函数，告诉你行和列的数量，让你生成这个二维数组。函数原型如下：

function vortex(n, m) {
  // n 是行数，m 是列数
  // 返回一个 n 行 m 列的二维数组
}

貌似看上去不是很难，让我们去写写试试。

解题思路

要解决这个问题，我们可以分为两个步骤：

• 第一步，生成一个全是0的二维数组
• 第二步，在数组里按照漩涡形式填充数字

第一步：生成全是0的二维数组

下面的 vortex 函数就是我们要实现的函数，告诉你行和列的数量，让你生成这个二维数组。函数原型如下：

function vortex(n, m) {}
console.log(vortex(5, 6));

那么首先要完成结果的二维数组，首先要生成一个全是 0 的二维数组。

于是就有了这样一个代码。

function vortex(n, m) {
  const nums = new Array(n).fill(0).map(() => []);
  return nums;
}
console.log("vortex >>>", vortex(5, 6));

通过 new Array() 创建一个数组，长度是 n，然后每一行填充一个数组。

这样我们就到了一个五行的数组。

列的话就简单了，我们只要在现在的行里填充指定的列数，然后每一列填充为 0 就可以了。

function vortex(n, m) {
  const nums = new Array(n).fill(0).map(() => new Array(m).fill(0));
  return nums;
}
console.log("vortex >>>", vortex(5, 6));

这样我们就得到了一个指定行数指定列数的全是 0 的二维数组。

第二步：按照漩涡形式填充数字

接下来就要依次以螺旋形式在数组里填充数字了。

我们可以使用两个变量 i 和 j 来表示当前位置在数组中的坐标，分别对应横坐标和纵坐标。

最开始是在左上角利用坐标去找到数组中对应的一项，给它填一个数字就行了，还需要一个变量 count 来表示当前要填充的数字。

然后循环填充就行了。

function vortex(n, m) {
  const nums = new Array(n).fill(0).map(() => new Array(m).fill(0));
  // 初始化坐标和计数器
  let i = 0,
    j = 0,
    count = 1;
  while (true) {
    // 填充当前位置
    nums[j][i] = count++;
    // 填充完之后改动 i 和 j
    // ...
  }
  return nums;
}

填充完了我们就要改动 i 和 j，然后根据改动后的值继续填充，但是现在我们还不知道如何改动。

我们可以这样想，无论我们是什么方向，你改动 i 和 j 无非就是在 i 上加某个值，在 j 上加某个值，我们可以用两个变量 stepi 来表示 i 加的值，stepj 来表示 j 加的值。

function vortex(n, m) {
  const nums = new Array(n).fill(0).map(() => new Array(m).fill(0));
  let i = 0,
    j = 0,
    count = 1;
    // 初始化步长
  let stepi = 1,
    stepj = 0;
  while (1) {
    nums[j][i] = count++;
    // 根据步长改动 i 和 j
    i += stepi;
    j += stepj;
    // ...
  }
  return nums;
}

比如这里 stepi 为 1，stepj 为 0，就意味着每次变动，i 加上 1，j 不变。

也就是说方向是上图这样由左至右的。

那么有些同学可能会说这么做的话如何转向呢？这个并不是我们首要考虑的问题，我们首要考虑的是什么时候转向。

第一种：当下一个位置为空时要转向。

第二种：当下一个位置已经填充过时要转向。

换句话说，只要下个位置不是 0，就要转向，无论超过了数组下标是 undefined，还是下个位置已经填充过。

那么我们可以写一个辅助函数来判断是否需要转向，同样也知道如何在循环里什么时候转向了。

function vortex(n, m) {
  // etc...
  // 是否需要转向
  function isTurn() {
    // 值为 undefined 或值不是 0 的时候
    return !nums[j] || nums[j][i] !== 0;
  }
  while (1) {
    nums[j][i] = count++;
    i += stepi;
    j += stepj;
    if (isTurn()) {
      // 转向
      // ...
    }
  }
  // etc...
}

那么我们如何转向？转向的第一步是不是要退回一步，因为已经前进了一步才知道下一步不能走，所以我们要先回来。

也就是说让 i 和 j 加上的值再减去就行，退回一步之后我们在进行转向。

function vortex(n, m) {
  // etc...
   while (true) {
     nums[j][i] = count++;
     i += stepi;
     j += stepj;
     if (isTurn()) {
       // 转向前先退回一步
       i -= stepi;
       j -= stepj;
       // 退回之后再进行转向
       // ...
     }
  // etc...
}

如何转向就特别有意思了，我们来找找规律。

通过上图我们可以知道，改变方向其实就是控制 stepi 和 stepj 的值。

也就是代码是这样写的。

function vortex(n, m) {
  // etc...
  while (1) {
    nums[j][i] = count++;
    i += stepi;
    j += stepj;
    if (isTurn()) {
      i -= stepi;
      j -= stepj;
      // 如果说 stepj 为 0 那么一定是在横向填充
      if (stepj === 0) {
        // 横向动变成纵向动
        stepj = stepi;
        stepi = 0;
      } else {
        // 纵向动变横向动
        stepi = -stepj;
        stepj = 0;
      }
    }
  }
  // etc...
}

现在我们已经转向了，转向后我们就要再次向前走一步了，所以利用新的 stepi 和 stepj 来走一步。

function vortex(n, m) {
  // etc...
  while (1) {
    nums[j][i] = count++;
    i += stepi;
    j += stepj;
    if (isTurn()) {
      i -= stepi;
      j -= stepj;
      if (stepj === 0) {
        stepj = stepi;
        stepi = 0;
      } else {
        stepi = -stepj;
        stepj = 0;
      }
      // 利用新的 stepi 和 stepj 来走一步。
      i += stepi;
      j += stepj;
    }
  }
  // etc...
}

这就完成了转向和继续前进了，但是什么时候我们退出循环呢？

就是说当我们即使转向也没有路的时候就退出循环。

function vortex(n, m) {
  const nums = new Array(n).fill(0).map(() => new Array(m).fill(0));
  let i = 0,
    j = 0,
    stepi = 1,
    stepj = 0,
    count = 1;
  function isTurn() {
    return !nums[j] || nums[j][i] !== 0;
  }
  while (1) {
    nums[j][i] = count++;
    i += stepi;
    j += stepj;
    if (isTurn()) {
      i -= stepi;
      j -= stepj;
      if (stepj === 0) {
        stepj = stepi;
        stepi = 0;
      } else {
        stepi = -stepj;
        stepj = 0;
      }
      i += stepi;
      j += stepj;
    }
    // 转向后也没有路就退出循环
    if (isTurn()) {
      break;
    }
  }
  return nums;
}
console.log("vortex >>>", vortex(5, 6));

现在我们已经全部实现了，运行一下看看。

可以看到输出的结果是没问题的。

总结

这个算法题虽然不难，但是考察了我们对数组和循环的掌握程度，以及对方向和坐标的理解能力。

希望这篇文章能够帮助你学习和巩固这些知识点。

虽然我们解出了这道题，但是我一直在想，这个东西能不能有数学的解，就是给你一个 i 和 j，有没有一个数学公式，可以直接算出某个位置的值。

有思路的同学可以在评论区留言。

本文来源自渡一官方公众号:Duing，欢迎关注获取最实时、最新、最全、最深入的技术讲解