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
#笔试题目#
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-09 16:15
我应届生,去年10月份开始在这家公司实习,到今年10月份正好一年想(实习+试用期),在想要不要提前9月份就离职,这样好找工作些,但又差一个月满一年,又怕10月份国庆回来离职,容易错过了下半年的金九银十,到年底容易gap到年后
小破站_程序员YT:说这家公司不好吧,你干了快一年 说这家公司好吧,你刚毕业就想跑路说你不懂行情吧,你怕错过金九银十说 你懂行情吧,校招阶段在实习,毕业社招想换工作 哥们,我该怎么劝你留下来呢
应届生,你找到工作了吗
点赞 评论 收藏
分享
流浪的神仙:无恶意,算法一般好像都得9硕才能干算法太卷啦
点赞 评论 收藏
分享
评论
1
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务