五、JavaScript 数组
这一章将集中讨论 JavaScript 数组的使用。作为一个 JavaScript 开发者，你会经常用到数组；它是最常用的数据结构。JavaScript 中的数组有很多内置方法。事实上，对于每个用例，有各种方法可以进行相同类型的数组操作。本章结束时，你将理解如何使用数组，并能够根据情况选择正确的方法。
阵列简介
数组是最基本的数据结构之一。如果你以前编程过，你很可能使用过数组。
1 var array1 = [1,2,3,4];
对于任何数据结构，开发人员感兴趣的是与四个基本操作相关的时间和空间复杂性:访问、插入、删除和搜索。(关于 Big-O 符号的回顾，请参考第 1 章。)
插入
插入意味着在数据结构中添加一个新元素。JavaScript 用.push(element)方法实现数组插入。此方法在数组末尾添加一个新元素。
1 var array1 = [1,2,3,4];
2 array1.push(5); //array1 = [1,2,3,4,5]
3 array1.push(7); //array1 = [1,2,3,4,5,7]
4 array1.push(2); //array1 = [1,2,3,4,5,7,2]
该运算的时间复杂度理论上为 O(1)。应该注意的是，实际上，这取决于运行代码的 JavaScript 引擎。这适用于所有本地支持的 JavaScript 对象。
删除
JavaScript 用.pop()方法实现数组删除。此方法移除数组中最后添加的元素。这也将返回移除的元素。
1 var array1 = [1,2,3,4];
2 array1.pop(); //returns 4, array1 = [1,2,3]
3 array1.pop(); //returns 3, array1 = [1,2]
与.push类似，.pop的时间复杂度为 O(1)。
另一种从数组中移除元素的方法是使用.shift()方法。此方法将移除第一个元素并返回它。
1 array1 = [1,2,3,4];
2 array1.shift(); //returns 1, array1 = [2,3,4]
3 array1.shift(); //returns 2, array1 = [3,4]
接近
访问指定索引处的数组只需要 O(1)，因为该进程使用该索引直接从内存中的地址获取值。这是通过指定索引来完成的(记住索引从 0 开始)。
1 var array1 = [1,2,3,4];
2 array1[0]; //returns 1
3 array1[1]; //returns 2
循环
迭代是访问数据结构中包含的每一项的过程。JavaScript 中有多种方法可以遍历数组。它们都具有 O( n )的时间复杂度，因为迭代正在访问 n 个元素。
for(变量；条件；修改)
for是最常见的迭代方法。它通常以这种形式使用:
1 for ( var i=0, len=array1.length; i<len; i++ ) {
2 console.log(array1[i]);
3 }
前面的代码简单来说就是初始化变量i，在执行主体(i<len)之前检查条件是否为假，然后修改(i++)，直到条件为假。同样，你可以使用一个while循环。但是，计数器必须设置在室外。
1 var counter=0;
2 while(counter<array1.length){
3 // insert code here
4 counter++;
5 }
您可以使用while循环实现无限循环，如下所示:
1 while(true){
2 if (breakCondition) {
3 break;
4 }
5 }
类似地，for循环可以通过不设置条件来实现无限循环，如下所示:
1 for ( ; ;) {
2 if (breakCondition) {
3 break
4 }
5 }
对于(在)
另一种迭代 JavaScript 数组的方法是逐个调用索引。在in之前指定的变量是数组的index，如下所示:
1 var array1 = ['all','cows','are','big'];
2
3 for (var index in array1) {
4 console.log(index);
5 }
这将打印以下内容:0,1,2,3。
要打印内容，请使用:
1 for (var index in array1) {
2 console.log(array1[index]);
3 }
这将打印出all、cows、are和big。
对于(的)
在of之前指定的变量是数组的element(值)，如下所示:
1 for (var element of array1) {
2 console.log(element);
3 }
这将打印出all、cows、are和big。
forEach()
forEach和其他迭代方法的最大区别是forEach不能中断迭代或者跳过数组中的某些元素。forEach通过遍历每一个元素，更加具有表现力和明确性。
1 var array1 = ['all','cows','are','big'];
2
3 array1.forEach( function (element, index){
4 console.log(element);
5 });
6
7 array1.forEach( function (element, index){
8 console.log(array1[index]);
9 });
都打印all、cows、are和big。
助手功能
以下部分讨论了其他常用的处理帮助函数。此外，还将介绍如何使用数组。
。切片(开始，结束)
这个 helper 函数返回一个现有数组的一部分，而不修改数组。.slice()接受两个参数:数组的开始索引和结束索引。
1 var array1 = [1,2,3,4];
2 array1.slice(1,2); //returns [2], array1 = [1,2,3,4]
3 array1.slice(2,4); //returns [3,4], array1 = [1,2,3,4]
如果只传递开始的索引，那么结尾将被认为是最大的索引。
1 array1.slice(1); //returns [2,3,4], array1 = [1,2,3,4]
2 array1.slice(1,4); //returns [2,3,4], array1 = [1,2,3,4]
如果没有传递任何东西，这个函数只返回数组的一个副本。需要注意的是，array1.slice() === array1评估为false。这是因为尽管数组的内容是相同的，但是这些数组所在的内存地址是不同的。
1 array1.slice(); //returns [1,2,3,4], array1 = [1,2,3,4]
这对于在 JavaScript 中复制数组很有用。记住 JavaScript 中的数组是基于引用的，这意味着如果你给一个数组赋值一个新的变量，对该变量的修改会应用到原来的数组。
1 var array1 = [1,2,3,4],
2 array2 = array1;
3
4 array1 // [1,2,3,4]
5 array2 // [1,2,3,4]
6
7 array2[0] = 5;
8
9 array1 // [5,2,3,4]
10 array2 // [5,2,3,4]
array2的 changing 元素意外改变了原数组，因为它是对原数组的引用。要创建一个新的数组，可以使用.from()。
1 var array1 = [1,2,3,4];
2 var array2 = Array.from(array1);
3
4 array1 // [1,2,3,4]
5 array2 // [1,2,3,4]
6
7 array2[0] = 5;
8
9 array1 // [1,2,3,4]
10 array2 // [5,2,3,4]
.from()取 O( n ，其中 n 是数组的大小。这很直观，因为复制数组需要复制数组的所有 n 个元素。
。拼接(开始、尺寸、元素 1、元素 2…)
这个 helper 函数通过删除现有元素和/或添加新元素来返回和更改数组的内容。
.splice()接受三个参数:起始索引、要删除的内容的大小和要添加的新元素。在第一个参数指定的位置添加新元素。它返回删除的元素。
1 var array1 = [1,2,3,4];
2 array1.splice(); //returns [], array1 = [1,2,3,4]
3 array1.splice(1,2); //returns [2,3], array1 = [1,4]
这个例子演示了删除。[2,3]被返回，因为它从索引 1 开始选择了两个项目。
1 var array1 = [1,2,3,4];
2 array1.splice(); //returns [], array1 = [1,2,3,4]
3 array1.splice(1,2,5,6,7); //returns [2,3],array1 = [1,5,6,7,4]
任何东西(任何对象类型)都可以添加到数组中。这就是 JavaScript 的美妙之处(也是奇怪的地方)。
1 var array1 = [1,2,3,4];
2 array1.splice(1,2,[5,6,7]); //returns [2,3], array1 = [1,[5,6,7],4]
3 array1 = [1,2,3,4];
4 array1.splice(1,2,{'ss':1}); //returns [2,3], array1 = [1,{'ss':1},4]
.splice()是，最坏的情况，O( n )。类似于复制，如果指定的范围是整个数组，每个 n 项都必须被删除。
。concat()
这将在数组末尾添加新元素，并返回数组。
1 var array1 = [1,2,3,4];
2 array1.concat(); //returns [1,2,3,4], array1 = [1,2,3,4]
3 array1.concat([2,3,4]); //returns [1,2,3,4,2,3,4],array1 = [1,2,3,4]
。长度属性
属性返回数组的大小。将此属性更改为较小的大小会从数组中删除元素。
1 var array1 = [1,2,3,4];
2 console.log(array1.length); //prints 4
3 array1.length = 3; // array1 = [1,2,3]
传播算子
由三个句点表示的扩展运算符(...)，用于在应该没有参数的地方扩展参数。
1 function addFourNums(a, b, c, d) {
2 return a + b + c + d;
3 }
4 var numbers = [1, 2, 3, 4];
5 console.log(addFourNums(...numbers)); // 10
Math.max和Math.min函数都接受无限数量的参数，因此您可以使用 spread 操作符进行以下操作。
要查找数组中的最大值，请使用以下命令:
1 var array1 = [1,2,3,4,5];
2 Math.max(array1); // 5
要查找数组中的最小值，请使用以下命令:
1 var array2 = [3,2,-123,2132,12];
2 Math.min(array2); // -123
练习
所有练习的代码都可以在 GitHub 上找到。 1
在一个数组中找出两个相加为一个数的数组元素
问题:给定数组arr，找到并返回数组中两个加起来为weight的索引，如果没有加起来为weight的组合，则返回-1。
比如像[1，2，3，4，5]这样的数组，有哪些数字加起来是 9？
答案当然是 4 和 5。
简单的解决方案是通过两个for循环来尝试每种组合，如下所示:
1 function findSum(arr, weight) {
2 for (var i=0,arrLength=arr.length; i<arrLength; i++){
3 for (var j=i+1; j<arrLength; j++) {
4 if (arr[i]+arr[j]==weight){
5 return [i,j];
6 }
7 }
8 }
9 return -1;
10 }
这个解决方案遍历一个数组，查看是否存在匹配对。
数组的 n 元素上的两个for循环产生高时间复杂度。但是，没有创建额外的内存。类似于时间复杂度如何描述相对于输入大小 n 完成算法所需的时间，空间复杂度描述实现所需的额外存储器。空间复杂度 O(1)是常数。
时间复杂度:O(nT4】2
空间复杂度: O(1)
我们来想想在 O( n )的线性时间内如何做到这一点。
如果存储了任何以前看到的数组元素并且可以很容易地进行检查，那会怎么样呢？
输入如下:
1 var arr = [1,2,3,4,5];
2 var weight = 9;
这里 4 和 5 是组合，它们的索引是[3,4]。当访问 5 时，如何确定解决方案存在？
如果当前值为 5，权重为 9，则剩余的所需权重仅为 4 (9-5=4)。由于在数组中 4 显示在 5 之前，这个解决方案可以在 O( n )中工作。最后，为了存储看到的元素，使用一个 JavaScript 对象作为哈希表。散列表的实现和使用将在后面的章节中讨论。存储和检索 JavaScript 对象属性在时间上是 O(1)。
1 function findSumBetter(arr, weight) {
2 var hashtable = {};
3
4 for (var i=0, arrLength=arr.length; i<arrLength; i++) {
5 var currentElement = arr[i],
6 difference = weight - currentElement;
7
8 // check the right one already exists
9 if (hashtable[currentElement] != undefined) {
10 return [i, hashtable[weight-currentElement]];
11 } else {
12 // store index
13 hashtable[difference] = i;
14 }
15 }
16 return -1;
17 }
时间复杂度: O( n
空间复杂度: O( n
存储到哈希表中并从哈希表中查找一个项目只需要 O(1)。空间复杂度增加到 O( n )来存储哈希表中的访问过的数组索引。
实现数组。Slice()函数从头开始
让我们回顾一下.slice()函数的作用。
.slice()接受两个参数:数组的开始索引和最后一个结束索引。它返回现有数组的一部分，而不修改数组函数arraySlice ( array、beginIndex、endIndex)。
1 function arraySlice(array, beginIndex, endIndex) {
2 // If no parameters passed, return the array
3 if (! beginIndex && ! endIndex) {
4 return array;
5 }
6
7 // If only beginning index is found, set endIndex to size
8 endIndex = array.length;
9
10 var partArray = [];
11
12 // If both begin and end index specified return the part of the array
13 for (var i = beginIndex; i < endIndex; i++ ) {
14 partArray.push(array[i]);
15 }
16
17 return partArray;
18 }
19 arraySlice([1 , 2 , 3 , 4 ], 1 , 2 ); // [2]
20 arraySlice([1 , 2 , 3 , 4 ], 2 , 4 ); // [3,4]
时间复杂度: O( n
空间复杂度 : O( n
时间复杂度为 O( n )，因为必须访问数组中的所有 n 项。复制数组时空间复杂度也是 O( n )容纳所有 n 项。
求两个大小相同的排序数组的中间值
回想一下，偶数集合中的中位数是两个中间数的平均值。如果数组是排序的，这就简单了。
这里有一个例子:
[1，2，3，4]的中位数为(2+3)/2 = 2.5。
1 function medianOfArray(array) {
2 var length = array.length;
3 // Odd
4 if (length % 2 == 1) {
5 return array[Math.floor(length/2)];
6 } else {
7 // Even
8 return (array[length/2]+array[length/2 - 1])/2;
9 }
10 }
现在，您可以遍历这两个数组，比较哪个更大，以跟踪中位数。如果两个数组大小相同，则总大小将是一个偶数。
这是因为两个偶数和两个奇数加起来就是一个偶数。请参阅第 8 章了解更多背景信息。
因为两个数组都是排序的，所以这个函数可以递归调用。每次，它都会检查哪个中值更大。
如果第二个数组的中值较大，则第一个数组被切成两半，只有较高的一半被递归传递。
如果第一个数组的中值较大，则第二个数组被切成两半，只有较高的一半作为下一个函数调用的第一个数组被传入，因为函数中的array2参数必须总是大于array1参数。最后，需要用pos表示的数组的大小来检查数组的大小是偶数还是奇数。
这是另一个例子:
数组 1 = [1，2，3]和数组 2 = [4，5，6]
这里，array1的中位数是 2，array2的中位数是 5。因此，中位数必须在[2，3]和[4，5]之间。由于只剩下四个元素，中值可以计算如下:
max(arr1[0]，arr2[0]) + min(arr1[1]，arr 2[1])/2；
1 function medianOfArray(array) {
2 var length = array.length;
3 // Odd
4 if (length % 2 == 1 ) {
5 return array[Math .floor(length / 2 )];
6 } else {
7 // Even
8 return (array[length / 2 ] + array[length / 2 - 1 ]) / 2 ;
9 }
10 }
11 // arr2 is the bigger array
12 function medianOfTwoSortedArray(arr1, arr2, pos) {
13 if (pos <= 0 ) {
14 return -1 ;
15 }
16 if (pos == 1 ) {
17 return (arr1[0] + arr2[0]) / 2 ;
18 }
19 if (pos == 2 ) {
20 return (Math .max(arr1[0], arr2[0]) + Math .min(arr1[1], arr2[1])) / 2 ;
21 }
22
23 var median1 = medianOfArray(arr1),
24 median2 = medianOfArray(arr2);
25
26 if (median1 == median2) {
27 return median1;
28 }
29
30 var evenOffset = pos % 2 == 0 ? 1 : 0 ,
31 offsetMinus = Math .floor(pos / 2 ) - evenOffset,
32 offsetPlus = Math .floor(pos / 2 ) + evenOffset;
33
34
35 if (median1 < median2) {
36 return medianOfTwoSortedArray(arr1.slice(offsetMinus), arr2.slice(offsetMinus), offsetPlus);
37 } else {
38 return medianOfTwoSortedArray(arr2.slice(offsetMinus), arr1.slice(offsetMinus), offsetPlus);
39 }
40 }
41
42 medianOfTwoSortedArray([1 , 2 , 3 ], [4 , 5 , 6 ], 3 ); // 3.5
43 medianOfTwoSortedArray([11 , 23 , 24 ], [32 , 33 , 450 ], 3 ); // 28
44 medianOfTwoSortedArray([1 , 2 , 3 ], [2 , 3 , 5 ], 3 ); // 2.5
时间复杂度:O(log2(n))
通过每次将数组大小减半，实现了对数时间复杂度。
在 K 排序数组中寻找公共元素
1 var arr1 = [1, 5, 5, 10];
2 var arr2 = [3, 4, 5, 5, 10];
3 var arr3 = [5, 5, 10, 20];
4 var output = [5 ,10];
在这个有三个数组的例子中， k =3。
为此，只需迭代每个数组并计算每个元素的实例数。但是，不要跟踪重复的(5 和 5.5 应该在一次数组迭代中计算一次)。为此，在递增之前检查最后一个元素是否相同。这只有在排序的情况下才会起作用。
迭代完所有三个数组后，遍历哈希表的属性。如果该值与 3 匹配，则意味着该数字出现在所有三个数组中。这可以通过将 k 循环检查放入另一个for循环中来推广到 k 个数组。
1 function commonElements(kArray) {
2 var hashmap = {},
3 last, answer = [];
4
5 for (var i = 0 , kArrayLength = kArray.length; i < kArrayLength; i++ ) {
6 var currentArray = kArray[i];
7 last = null ;
8 for (var j = 0 , currentArrayLen = currentArray.length;
9 j < currentArrayLen; j++ ) {
10 var currentElement = currentArray[j];
11 if (last != currentElement) {
12 if (! hashmap[currentElement]) {
13 hashmap[currentElement] = 1 ;
14 } else {
15 hashmap[currentElement]++ ;
16 }
17 }
18 last = currentElement;
19 }
20 }
21
22 // Iterate through hashmap
23 for (var prop in hashmap) {
24 if (hashmap[prop] == kArray.length) {
25 answer.push(parseInt (prop));
26 }
27 }
28 return answer;
29 }
30
31 commonElements([[1 ,2 ,3 ],[1 ,2 ,3 ,4 ],[1 ,2 ]]); // [ 1, 2 ]
时间复杂度: O( kn
空间复杂度: O( n
这里， n 是最长的数组长度， k 是数组的个数。
JavaScript 函数数组方法
JavaScript 的某些部分可以像函数式编程语言一样编写。与命令式编程不同，JavaScript 并不关注程序的状态。它不使用循环，只使用函数(方法)调用。你可以从 Anto Aravinth (Apress，2017)的开始函数式 JavaScript 中了解更多关于 JavaScript 的函数式编程。
在本节中，将只探讨 JavaScript 中的三种函数数组方法:map、filter和reduce。这些方法不会改变原始数组内容。
地图
map 函数将传递的函数转换应用于数组中的每个元素，并返回应用了这些转换的新数组。
例如，您可以将每个元素乘以 10，如下所示:
1 [1,2,3,4,5,6,7].map(function (value){
2 return value*10;
3 });
4 // [10, 20, 30, 40, 50, 60, 70]
过滤器
filter 函数只返回满足传递的条件参数的数组元素。同样，这不会改变原始数组。
例如，这会过滤大于 100 的元素:
1 [100,2003,10,203,333,12].filter(function (value){
2 return value > 100;
3 });
4 // [2003, 203, 333]
减少
reduce 函数使用传递的转换函数参数将数组中的所有元素组合成一个值。
例如，这将添加所有元素:
1 var sum = [0,1,2,3,4].reduce( function (prevVal, currentVal, index, array) {
2 return prevVal + currentVal;
3 });
4 console.log(sum); // prints 10
这个函数也可以将initialValue作为第二个参数，它初始化 reduce 值。例如，在前面的示例中提供 1 的initialValue将产生 11，如下所示:
1 var sum = [0,1,2,3,4].reduce( function (prevVal, currentVal, index, array) {
2 return prevVal + currentVal;
3 }, 1);
4 console.log(sum); // prints 11
多维数组
与 Java 和 C++不同，JavaScript 没有多维数组(见图 5-1 )。
图 5-1
多维数组
取而代之的是“锯齿状”阵列。一个交错数组是一个数组，它的元素是数组。交错数组的元素可以有不同的维度和大小(参见图 5-2 )。
图 5-2
锯齿状阵列
这里有一个帮助器函数来创建一个类似图 5-3 中的交错数组:
图 5-3
三乘三矩阵
1 function Matrix(rows, columns) {
2 var jaggedarray = new Array(rows);
3 for (var i=0; i < columns; i +=1) {
4 jaggedarray[i]=new Array(rows);
5 }
6 return jaggedarray;
7 }
8 console.log(Matrix(3,3));
要访问交错数组中的元素，请指定一行和一列(参见图 5-4 )。
图 5-4
三乘三的数字矩阵
1 var matrix3by3 = [[1,2,3],[4,5,6],[7,8,9]];
2 matrix3by3[0]; // [1,2,3]
3 matrix3by3[1]; // [4,5,6]
4 matrix3by3[1]; // [7,8,9]
5
6 matrix3by3[0][0]; // 1
7 matrix3by3[0][1]; // 2
8 matrix3by3[0][2]; // 3
9
10 matrix3by3[1][0]; // 4
11 matrix3by3[1][1]; // 5
12 matrix3by3[1][2]; // 6
13
14 matrix3by3[2][0]; // 7
15 matrix3by3[2][1]; // 8
16 matrix3by3[2][2]; // 9
练习
所有练习的代码都可以在 GitHub 上找到。 2
螺旋印刷
让我们用矩阵做一个例题。给定一个矩阵，按照螺旋顺序打印元素，如图 5-5 所示。
图 5-5
螺旋印刷
起初，这看起来是一项艰巨的任务。然而，这个问题可以分解为五个主要部分。
-
从左向右打印
-
从上到下打印
-
从右向左打印
-
从下到上打印
-
对这四种操作进行限制
换句话说，保留四个关键变量，这四个变量表明:
-
顶行
-
底端行
-
左列
-
右列
每当四个print函数中的一个被成功执行时，简单地增加四个变量中的一个。例如，打印完第一行后，将其递增 1。
1 var M = [
2 [1, 2, 3, 4, 5],
3 [6, 7, 8, 9, 10],
4 [11, 12, 13, 14, 15],
5 [16, 17, 18, 19, 20]
6 ];
7 function spiralPrint(M) {
8 var topRow = 0,
9 leftCol = 0,
10 btmRow = M.length - 1,
11 rightCol = M[0].length - 1;
12
13 while (topRow < btmRow && leftCol < rightCol) {
14 for (var col = 0; col <= rightCol; col++) {
15 console.log(M[topRow][col]);
16 }
17 topRow++;
18 for (var row = topRow; row <= btmRow; row++) {
19 console.log(M[row][rightCol]);
20 }
21 rightCol--;
22 if (topRow <= btmRow) {
23 for (var col = rightCol; col >= 0; col--) {
24 console.log(M[btmRow][col]);
25 }
26 btmRow--;
27 }
28 if (leftCol <= rightCol) {
29 for (var row = btmRow; row > topRow; row--) {
30 console.log(M[row][leftCol]);
31 }
32 leftCol++;
33 }
34 }
35 }
36 spiralPrint(M);
时间复杂度: O( mn
空间复杂度: O(1)
这里， m 是行数， n 是列数。矩阵中的每个项目只被访问一次。
井字游戏
给定一个代表井字游戏棋盘的矩阵，确定是否有人赢了，是否是平局，或者游戏是否还没有结束。 3
这里有一些例子。
这里，X 赢了:
OX-
-XO
OX
这里是作为一个矩阵:[['O', 'X', '-'], ['-' ,'X', 'O'], ['O', 'X', '-']]。
在这里，O 赢了:
O-X
-O-
-XO
这里是作为一个矩阵:[['O','-','X'], ['-','O','-'], ['-','X','O']]。
为此，使用for循环检查所有三行，使用for循环检查所有列，并检查对角线。
1 function checkRow ( rowArr, letter ) {
2 for ( var i=0; i < 3; i++) {
3 if (rowArr[i]!=letter) {
4 return false;
5 }
6 }
7 return true;
8 }
9
10 function checkColumn ( gameBoardMatrix, columnIndex, letter ) {
11 for ( var i=0; i < 3; i++) {
12 if (gameBoardMatrix[i][columnIndex]!=letter) {
13 return false;
14 }
15 }
16 return true;
17 }
18
19 function ticTacToeWinner ( gameBoardMatrix, letter) {
20
21 // Check rows
22 var rowWin = checkRow(gameBoardMatrix[0], letter)
23 || checkRow(gameBoardMatrix[1], letter)
24 || checkRow(gameBoardMatrix[2], letter);
25
26 var colWin = checkColumn(gameBoardMatrix, 0, letter)
27 || checkColumn(gameBoardMatrix, 1, letter)
28 || checkColumn(gameBoardMatrix, 2, letter);
29
30 var diagonalWinLeftToRight = (gameBoardMatrix[0][0]==letter && gameBoardMatrix[1][1]==letter && gameBoardMatrix[2][2]==letter);
31 var diagonalWinRightToLeft = (gameBoardMatrix[0][2]==letter && gameBoardMatr ix[1][1]==letter && gameBoardMatrix[2][0]==letter);
32
33 return rowWin || colWin || diagonalWinLeftToRight || diagonalWinRightToLeft;
34 }
35
36 var board = [['O','-','X'],['-','O','-'],['-','X','O']];
37 ticTacToeWinner(board, 'X'); // false
38 ticTacToeWinner(board, 'O'); // true
路由选择
在图 5-6 中，给定位置 x ，找到出口 e 。
图 5-6
寻找一条路
\n是 JavaScript 中用来换行的字符集，就像在许多标准编程语言中一样。将它与反斜线结合起来，可以在变量到字符串的赋值过程中创建换行符。
1 var board =
2 `%e%%%%%%%%%\n
3 %...%.%...%\n
4 %.%.%.%.%%%\n
5 %.%.......%\n
6 %.%%%%.%%.%\n
7 %.%.....%.%\n
8 %%%%%%%%%x%`;
var rows = board.split("\n")
然后在数组上使用.map将某些字符分成每一列。
function generateColumnArr (arr) {
return arr.split("");
}
var mazeMatrix = rows.map(generateColumnArr);
这将生成适当的矩阵，其中每一行都是字符的数组，棋盘是这些行的数组。
现在，首先找到入口， e ，和出口， x 。该函数将返回要搜索的字符的行位置 i 和列位置 j :
1 function findChar(char , mazeMatrix) {
2 var row = mazeMatrix.length,
3 column = mazeMatrix[0 ].length;
4
5 for (var i = 0 ; i < row; i++ ) {
6 for (var j = 0 ; j < column; j++ ) {
7 if (mazeMatrix[i][j] == char ) {
8 return [i, j];
9 }
10 }
11 }
12 }
当然，还需要一个函数将矩阵很好地打印为字符串，如下所示:
1 function printMatrix(matrix) {
2 var mazePrintStr = "" ,
3 row = matrix.length,
4 column = matrix[0 ].length;
5
6 for (var i = 0 ; i < row; i++ ) {
7
8 for (var j = 0 ; j < column; j++ ) {
9 mazePrintStr += mazeMatrix[i][j];
10 }
11
12 mazePrintStr += "\n" ;
13
14 }
15 console.log(mazePrintStr);
16 }
最后，定义一个名为path的函数。这递归地检查上，右，下，左。
Up: path(x+1,y)
Right: path(x,y+1)
Down: path(x-1,y)
Left: path(x,y-1)
function mazePathFinder(mazeMatrix) {
var row = mazeMatrix.length,
column = mazeMatrix[0].length,
startPos = findChar('e', mazeMatrix),
endPos = findChar('x', mazeMatrix);
path(startPos[0], startPos[1]);
function path(x, y) {
if (x > row - 1 || y > column - 1 || x < 0 || y < 0) {
return false;
}
// Found
if (x == endPos[0] && y == endPos[1]) {
return true;
}
if (mazeMatrix[x][y] == '%' || mazeMatrix[x][y] == '+') {
return false;
}
// Mark the current spot
mazeMatrix[x][y] = '+';
printMatrix(mazeMatrix);
if (path(x, y - 1) || path(x + 1, y) || path(x, y + 1) || path(x - 1, y)) {
return true;
}
mazeMatrix[x][y] = '.';
return false;
}
}
图 5-7 显示控制台输出。
图 5-7
控制台输出
时间复杂度: O( mn
空间复杂度: O(1)
这里， m 是行长度， n 是列长度。每个元素只被访问一次。
矩阵旋转
将矩阵向左旋转 90 度。
例如，以下内容:
101
001
111
旋转到此:
111
001
101
图 5-8 所示为旋转。
图 5-8
矩阵逆时针旋转
如图 5-8 所示，向左旋转 90 度时，会出现以下情况:
-
矩阵的第三列成为结果的第一行。
-
矩阵的第二列成为结果的第二行。
-
矩阵的第一列成为结果的第三行。
以下旋转将转动原稿的第三列:
1 var matrix = [[1,0,1],[0,0,1],[1,1,1]];
2
3
4 function rotateMatrix90Left (mat){
5 var N = mat.length;
6
7 // Consider all squares one by one
8 for (var x = 0; x < N / 2; x++) {
9 // Consider elements in group of 4 in
10 // current square
11 for (var y = x; y < N-x-1; y++) {
12 // store current cell in temp variable
13 var temp = mat[x][y];
14
15 // move values from right to top
16 mat[x][y] = mat[y][N-1-x];
17
18 // move values from bottom to right
19 mat[y][N-1-x] = mat[N-1-x][N-1-y];
20
21 // move values from left to bottom
22 mat[N-1-x][N-1-y] = mat[N-1-y][x];
23
24 // assign temp to left
25 mat[N-1-y][x] = temp;
26 }
27 }
28 }
29 rotateMatrix90Left(matrix);
30 console.log(matrix); // [[1,1,1],[0,0,1],[1,0,1]]
时间复杂度: O( mn
空间复杂度: O(1)
这里， m 是行长度， n 是列长度。每个元素只被访问一次。空间复杂度为 O(1 ),因为原始数组被修改而不是创建新数组。
摘要
本章涵盖了各种本机实现的数组函数，并在表 5-1 中进行了总结。
表 5-1
数组函数摘要
|
功能
|
使用
|
| --- | --- |
| push(element) | 将元素添加到数组的末尾 |
| pop() | 移除数组的最后一个元素 |
| shift() | 移除数组的第一个元素 |
| slice(beginIndex, endIndex) | 返回从beginIndex到endIndex的数组的一部分 |
| splice(beginIndex, endIndex) | 返回从beginIndex到endIndex的数组的一部分，并通过删除这些元素来修改原始数组 |
| concat(arr) | 在数组末尾添加新元素(来自arr) |
除了标准的while和for循环机制，数组元素的迭代可以使用表 5-2 中所示的替代循环机制。
表 5-2
迭代摘要
|
功能
|
使用
|
| --- | --- |
| for ( var 道具进场) | 按数组元素的索引进行迭代 |
| for | 通过数组元素的值进行迭代 |
| arr.forEach(fnc) | 在每个元素上应用fnc值 |
最后，回想一下 JavaScript 利用交错数组(数组的数组)来获得多维数组行为。使用二维数组，可以很容易地表示二维表面，如井字游戏棋盘和迷宫。
Footnotes [1](#Fn1_source) [T2`https://github.com/Apress/js-data-structures-and-algorithms`](https://github.com/Apress/js-data-structures-and-algorithms) [2](#Fn2_source) [T2`https://github.com/Apress/js-data-structures-and-algorithms`](https://github.com/Apress/js-data-structures-and-algorithms) [3](#Fn3_source) 欲了解更多井字游戏规则，请访问 [`https://en.wikipedia.org/wiki/Tic-tac-toe`](https://en.wikipedia.org/wiki/Tic-tac-toe) 。版权属于：月萌API www.moonapi.com，转载请注明出处
