首页 > n阶螺旋矩阵/半矩阵 JavaScript实现
头像
牛客715576831号
编辑于 2020-09-04 19:21
+ 关注

n阶螺旋矩阵/半矩阵 JavaScript实现

以下分别是

  1. n阶螺旋矩阵 (JavaScript实现)
  2. n阶螺旋半矩阵 (JavaScript实现)
    的实现,其中2分别用了迭代法和递归法实现。

递归法参考下面链接的思想:求解n阶螺旋矩阵问题(C++)
特别感谢

n阶螺旋矩阵 递归法

 01 02 03 04 05 06
 20 21 22 23 24 07
 19 32 33 34 25 08
 18 31 36 35 26 09
 17 30 29 28 27 10
 16 15 14 13 12 11

// n阶螺旋矩阵,递归实现
let n = 6;

// 创建二维数组,默认填充0
const a = Array.from({ length: n }, () => Array.from({ length: n }, () => 0));

helixMatrix(n, 1, n, 0);

console.log(format(a));

// n: n阶
// num0: 自增的填充值,用来确定输出的数字
// len: 用来表示当前调用的是哪个递归
// m: 用来确定输出坐标!!
function helixMatrix(n, num0, len, m) {
  if (len == 1) {
    return (a[m][m] = num0);
  }
  if (len == 2) {
    a[m][m] = num0++;
    a[m][m + 1] = num0++;
    a[m + 1][m + 1] = num0++;
    a[m + 1][m] = num0;
    return;
  }

  let x = m, //坐标最小值
    y = n - 1 - m; //坐标最大值 (第一层是 n -1, 第二层是n-1-1)

  if (len >= 3) {
    //先处理外围
    //上
    for (let i = x; i <= y; i++) {
      a[x][i] = num0++;
    }
    //右
    for (let i = x + 1; i <= y; i++) {
      a[i][y] = num0++;
    }
    //下
    for (let i = y - 1; i >= x; i--) {
      a[y][i] = num0++;
    }
    //左
    for (let i = y - 1; i >= x + 1; i--) {
      a[i][x] = num0++;
    }
    //然后处理内部, 递归调用小于2层的
    helixMatrix(n, num0, len - 2, m + 1);
  }
}

// 格式化输出最终结果
function format(a) {
  return a.reduce((accu, item) => {
    return (
      accu +
      item.reduce((suba, subi) => {
        subi = subi.toString();
        subi = subi.length > 1 ? subi : "0" + subi;
        return suba + " " + subi;
      }, "") +
      "\n"
    );
  }, "");
}
//n阶螺旋半矩阵
// 1  2  3  4 5
// 12 13 14 6
// 11 15 7
// 10 8
// 9

n阶螺旋半矩阵 方法1 迭代法

const n = 10;
const log = (...args) => {  // 辅助调试用
  //   console.log(...args);
};
console.log(outputN(n));

// 迭代法
// 最重要是两点:
// 1. 确定循环体结束条件
// 2. 确定循环体内循环时的游标控制
//      边界条件设定 以及 min/max的变化
function outputN(n) {
  let i = (j = iMin = jMin = cur = 0),
    iMax = (jMax = n - 1);
  // 双数组存放
  let a = Array.from({ length: n }, () => {
    return Array.from({ length: n }, () => '');
  });

  // 结束条件
  while (iMin <= iMax && jMin <= jMax) {
    i = iMin;
    j = jMin;
    debuglog();
    //循环体 1: 水平方向 i自增
    while (i <= iMax) {
      add();
      i++;
    }
    log("1:", a);
    i = --iMax;
    j = ++jMin;
    debuglog();

    //循环体 2:对角线方向 i--, j++
    while (i >= iMin && j <= jMax) {
      add();
      i--;
      j++;
    }
    log("2:", a);

    j = --jMax;
    --iMax;
    i = iMin;
    debuglog();

    //循环体 3:左轴方向 j--
    while (j >= jMin) {
      add();
      j--;
    }
    iMin++;
    jMax--;
    log("3:", a);
  }

  // 格式化输出
  a = a.reduce((accu, item) => accu + item.join(" ") + "\n", "");
  return a;

  function add() {
    let res = (++cur).toString();
    a[j][i] = res.length > 1 ? res : "0" + res;
  }
  function debuglog() {
    // console.log(i, j, [iMin, iMax], [jMin, jMax]);
  }
}

n阶螺旋半矩阵 方法2 递归

// testcase: 批量测试  
// 1 2 3 4 5 7 8 9 10
Array.from({ length: 10 }).forEach((item, index) => {
  let n = index;
  // 创建二维数组保存结果
  const a = Array.from({ length: n }, () => {
    return Array.from({ length: n }, () => "");
  });
  triangleHelixMatrix(a, n, 0, n);
  console.log("------------" + n + "---------");
  console.log(format(a));
});

// 通篇参考这里的思想: https://blog.nowcoder.net/n/b4600b3c00a6494088c942f89e009d66
// a 是数组,方便批量测试用,不重要
// n 
// m 是个游标,在最大值 x - y 之间移动
// value 是自增的值,需要传递
// 递归设计两个要素:
// 递归出口: n = 1~3时,是固定值
// 递归体: 
// len 是当前执行的阶数,从手动写出 n = 1~7 的规律发现:
// n的输出等于 n 外围输出 + (n-3)的输出, 所以可以递归
function triangleHelixMatrix(a, n, m, len, value = 1) {
  if (len < 1) {
    return;
  }
  if (len === 1) {
    a[m][m] = value;
    return;
  }
  if (len === 2) {
    a[m][m] = value++;
    a[m][m + 1] = value++;
    a[m + 1][m] = value;
    return;
  }
  if (len === 3) {
    a[m][m] = value++;
    a[m][m + 1] = value++;
    a[m][m + 2] = value++;
    a[m + 1][m + 1] = value++;
    a[m + 2][m] = value++;
    a[m + 1][m] = value++;
    return;
  }
  let x = m, // 坐标下限
    y = n - 1 - m; // 坐标上限

  n !== len && y--; // 坐标上限需要减 2

  // 先输出外围
  // 上
  for (let i = x; i <= y; i++) {
    a[x][i] = value++;
  }
  // 中
  for (let i = y - 1, j = x + 1; i >= x && j <= y; i--, j++) {
    a[j][i] = value++;
  }
  // 左
  for (let i = x, j = y - 1; j > x; j--) {
    a[j][i] = value++;
  }

  triangleHelixMatrix(a, n, m + 1, len - 3, value);
}

// 格式化输出
function format(a) {
  return a.reduce((accu, item) => {
    return (
      accu +
      item.reduce((suba, subi) => {
        subi =
          subi === "" ? 
            "" : 
            subi.toString().length > 1 
                ? subi 
                : "0" + subi;
        return suba + " " + subi;
      }, "") +
      "\n"
    );
  }, "");
}

批量测试输出结果:

------------0---------

------------1---------
 01

------------2---------
 01 02
 03

------------3---------
 01 02 03
 06 04
 05

------------4---------
 01 02 03 04
 09 10 05
 08 06
 07

------------5---------
 01 02 03 04 05
 12 13 14 06
 11 15 07
 10 08
 09

------------6---------
 01 02 03 04 05 06
 15 16 17 18 07
 14 21 19 08
 13 20 09
 12 10
 11

------------7---------
 01 02 03 04 05 06 07
 18 19 20 21 22 08
 17 27 28 23 09
 16 26 24 10
 15 25 11
 14 12
 13

------------8---------
 01 02 03 04 05 06 07 08
 21 22 23 24 25 26 09
 20 33 34 35 27 10
 19 32 36 28 11
 18 31 29 12
 17 30 13
 16 14
 15

------------9---------
 01 02 03 04 05 06 07 08 09
 24 25 26 27 28 29 30 10
 23 39 40 41 42 31 11
 22 38 45 43 32 12
 21 37 44 33 13
 20 36 34 14
 19 35 15
 18 16
 17

全部评论

(0) 回帖
加载中...
话题 回帖

相关热帖

近期热帖

近期精华帖

热门推荐