视频1 视频21 视频41 视频61 视频文章1 视频文章21 视频文章41 视频文章61 推荐1 推荐3 推荐5 推荐7 推荐9 推荐11 推荐13 推荐15 推荐17 推荐19 推荐21 推荐23 推荐25 推荐27 推荐29 推荐31 推荐33 推荐35 推荐37 推荐39 推荐41 推荐43 推荐45 推荐47 推荐49 关键词1 关键词101 关键词201 关键词301 关键词401 关键词501 关键词601 关键词701 关键词801 关键词901 关键词1001 关键词1101 关键词1201 关键词1301 关键词1401 关键词1501 关键词1601 关键词1701 关键词1801 关键词1901 视频扩展1 视频扩展6 视频扩展11 视频扩展16 文章1 文章201 文章401 文章601 文章801 文章1001 资讯1 资讯501 资讯1001 资讯1501 标签1 标签501 标签1001 关键词1 关键词501 关键词1001 关键词1501 专题2001
JavaScript趣题:螺旋矩阵
2020-11-27 20:26:05 责编:小采
文档
 给定一个n * n的二维数组,使用螺旋矩阵算法,遍历它,并返回路径。

例子如下:

array = [[1,2,3], 
 [4,5,6], 
 [7,8,9]] 
snail(array) // => [1,2,3,6,9,8,7,4,5]

这个程序的例子可能不太直观,那就上个图来展示下它这个过程。

大家可以看到,就好比一个人在迷宫里面前进,它首先位于(0,0)这个位置,接着向右走,遇到边界,就改为向下走,又遇到了边界,改为向左走....

细心的人,很快就可以发现一个规律:

迷宫里的这个人有四种基本行进策略。

1.当向右走,如果遇到边界,或者右边的格子已经走过,那么就向下走,否则继续向右走。

2.当向下走,如果遇到边界,或者下边的格子已经走过,那么就向左走,否则继续向下走。

3.当向左走,如果遇到边界,或者左边的格子已经走过,那么就向上走,否则继续向左走。

4.当向上走,如果遇到边界,或者上边的格子已经走过,那么就向右走,否则继续向上走。

大家可以看出来,这是一个递归的过程,那么,何时终止呢?

当每一个格子,这个人都访问过了时,那么就终止了。

我下面写的程序,用到了一个boolean类型的二维数组,记录格子是否已经走过。

引入了上下左右四种函数,分别表示四种策略。

function snail(array) { 
 //当前行 
 var row = 0; 
 //当前列 
 var col = 0; 
 //对应的存放boolean值的二维数组 
 var hasVisited = []; 
 //存放结果的数组 
 var result = []; 
 //数组元素个数 
 var size = array.length * array[0].length; 
 
 //boolean二维数组初始化 
 for (var i = 0; i < array.length; i++) { 
 var temp = []; 
 var len = array[i].length; 
 for (var j = 0; j < len; j++) { 
 temp.push(false); 
 } 
 hasVisited.push(temp); 
 } 
 
 function right() { 
 if (result.length < size) { 
 result.push(array[row][col]); 
 hasVisited[row][col] = true; 
 if (col + 1 >= array.length || hasVisited[row][col + 1]) { 
 row += 1; 
 down(); 
 } else { 
 col += 1; 
 right(); 
 } 
 } 
 } 
 
 function down() { 
 if (result.length < size) { 
 result.push(array[row][col]); 
 hasVisited[row][col] = true; 
 if (row + 1 >= array.length || hasVisited[row + 1][col]) { 
 col -= 1; 
 left(); 
 } else { 
 row += 1; 
 down(); 
 } 
 } 
 } 
 
 function left() { 
 if (result.length < size) { 
 result.push(array[row][col]); 
 hasVisited[row][col] = true; 
 if (col == 0 || hasVisited[row][col - 1]) { 
 row -= 1; 
 up(); 
 } else { 
 col -= 1; 
 left(); 
 } 
 } 
 } 
 
 function up() { 
 if (result.length < size) { 
 result.push(array[row][col]); 
 hasVisited[row][col] = true; 
 if (hasVisited[row - 1][col]) { 
 col += 1; 
 right(); 
 } else { 
 row -= 1; 
 up(); 
 } 
 } 
 } 
 //首先往右走 
 right(); 
 return result; 
}

下载本文
显示全文
专题