也许你看过很多面经里都讲到面试会问一些奇奇怪怪的算法题，说实话，手撕红黑树做不出来不丢人，很难的动态规划没思路也没关系，但是二维数组相关的题目还是希望你了解一下。
不同于一些奇怪的算法题让你面试造核弹，二维数组算法题目很能考察到逻辑能力、程序边界问题，而且有相当一部分二维数组可以使用递归来解决，可以说是程序员居家之必备题。
此类问题，重点是从数组的下标中发现规律，写代码的时候要注意程序的边界问题，常见于 Z 字形打印二维数组、蛇形打印二维数组、杨辉三角等等问题。
LeetCode.118 ，难度简单
给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。 示例:
输入: 5
输出:[ [1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1] ]
观察给出的例子，可以发现规律，比如对于 arr1=[1,2,1]和 arr2=[1,3,3,1]来说：
可以看出规律来：
反过来思路就是：
/**
* @param {number} numRows
* @return {number[][]}
*/
var generate = function(n) {
if(n === 0)
return [];
if(n === 1)
return [ [1] ];
let res = [[1]];
for(let i = 1;i < n;i++) {
let lastArr = res[i-1];
let newArr = [];
for(let j = 0;j < lastArr.length;j++) {
if(j === 0)
newArr.push(1);
if(j === lastArr.length-1)
newArr.push(1);
else {
newArr.push(lastArr[j]+lastArr[j+1]);
}
}
res.push(newArr);
}
return res;
};
LeetCode.498 ，难度中等
给定一个含有 M x N 个元素的矩阵（ M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素，对角线遍历如下图所示。 示例:
输入: [
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]输出: [1,2,4,7,5,3,6,8,9]
观察一个例子，对于下面这个二维数组来说，对角线遍历的顺序如下：
[
A, B, C, D,
E, F, G, H,
I, J, K, L
]
可以看出来一些规律：
/**
* @param {number[][]} matrix
* @return {number[]}
*/
var findDiagonalOrder = function(matrix) {
if(matrix === null || matrix.length === 0 || matrix[0].length === 0)
return [];
let rows = matrix.length;
let cols = matrix[0].length;
let count = 0;
let res = [];
while(count < rows+cols-1) {
let r1 = count < rows ? count : rows-1;
let c1 = count - r1;
while(r1 >= 0 && c1 < cols) {
res.push(matrix[r1][c1]);
r1--;
c1++;
}
count++;
if(count >= rows+cols-1)
break;
let c2 = count < cols ? count : cols-1;
let r2 = count - c2;
while(c2 >= 0 && r2 < rows) {
res.push(matrix[r2][c2]);
r2++;
c2--;
}
count++
}
return res;
};
LeetCode.54 ，难度中等
给定一个包含 m x n 个元素的矩阵（ m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。
示例 1:
输入: [
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ] ]
输出: [1,2,3,6,9,8,7,4,5]
示例 2:
输入: [
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12] ]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]
从题目给出的例子可以看出，螺旋遍历矩阵其实就是按照顺时针一层一层的遍历。注意好边界的划分，以及特殊情况比如一行和一列的处理。
/**
* @param {number[][]} matrix
* @return {number[]}
*/
var traverseLayer = function(m, startRow, endRow, startCol, endCol, res) {
if(startRow === endRow) {
// 一列的情况
for(let i = startCol;i <= endCol;i++) {
res.push(m[startRow][i]);
}
} else if(startCol === endCol) {
for(let i = startRow;i <= endRow;i++) {
res.push(m[i][startCol]);
}
} else {
let curR = startRow;
let curC = startCol;
while(curC < endCol) {
res.push(m[curR][curC]);
curC++;
}
while(curR < endRow) {
res.push(m[curR][curC]);
curR++;
}
while(curC > startCol) {
res.push(m[curR][curC]);
curC--;
}
while(curR > startRow) {
res.push(m[curR][curC]);
curR--;
}
}
}
var spiralOrder = function(matrix) {
if(matrix === void 0 || matrix.length === 0 || matrix[0].length === 0)
return [];
let res = [];
let startRow = 0;
let endRow = matrix.length-1;
let startCol = 0;
let endCol = matrix[0].length-1;
while(startRow <= endRow && startCol <= endCol) {
traverseLayer(matrix, startRow, endRow, startCol, endCol, res);
startRow++;
endRow--;
startCol++;
endCol--;
}
return res;
};
对于此类问题，最重要的是要注意到不是简单地找数组下标的规律就能解决的，要把问题抽象成递归的思路，递归入口、递归调用、递归结束条件，这三点缺一不可。
LeetCode.547 ，难度中等
班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。
给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果 M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。
示例 1:
输入:
[[1,1,0],
[1,1,0],
[0,0,1]]输出: 2
说明：已知学生 0 和学生 1 互为朋友，他们在一个朋友圈。 第 2 个学生自己在一个朋友圈。所以返回 2 。
示例 2:
输入:
[[1,1,0],
[1,1,1],
[0,1,1]]输出: 1
说明：已知学生 0 和学生 1 互为朋友，学生 1 和学生 2 互为朋友，所以学生 0 和学生 2 也是朋友，所以他们三个在一个朋友圈，返回 1 。
注意： N 在[1,200]的范围内。 对于所有学生，有 M[i][i] = 1 。 如果有 M[i][j] = 1，则有 M[j][i] = 1 。
看一下这道题的示例，可以看出来如果 arr[0,1]=1，0 和 1 是朋友，那接下来就要去检查 1 和其他的人是否是朋友，再依次检查下去，说到这里就可以考虑深度优先的搜索方法了。
/**
* @param {number[][]} M
* @return {number}
*/
var findCircleNum = function(M) {
// 深度优先
let visited = [];
for(let i = 0;i < M.length;i++) {
visited.push(false);
}
let res = 0;
for(let i = 0;i < visited.length;i++) {
if(visited[i])
continue;
traverse(M, i, visited);
res++;
}
return res;
};
function traverse(M, cur, visited) {
visited[cur] = true;
for(let i = 0;i < M.length;i++) {
if(visited[i] || !M[cur][i])
continue;
traverse(M, i, visited);
}
}
LeetCode.695 ，难度中等
给定一个包含了一些 0 和 1 的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。
找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 。)
示例 1:
[[0,0,1,0,0,0,0,1,0,0,0,0,0], [0,0,0,0,0,0,0,1,1,1,0,0,0], [0,1,1,0,1,0,0,0,0,0,0,0,0], [0,1,0,0,1,1,0,0,1,0,1,0,0], [0,1,0,0,1,1,0,0,1,1,1,0,0], [0,0,0,0,0,0,0,0,0,0,1,0,0], [0,0,0,0,0,0,0,1,1,1,0,0,0], [0,0,0,0,0,0,0,1,1,0,0,0,0]]
对于上面这个给定矩阵应返回 6 。
注意答案不应该是 11，因为岛屿只能包含水平或垂直的四个方向的‘1’。
示例 2:
[[0,0,0,0,0,0,0,0]]
对于上面这个给定的矩阵, 返回 0 。
注意: 给定的矩阵 grid 的长度和宽度都不超过 50 。
对于[[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]这样的矩阵来说，从最左上角的 1 出发，分别再考察它的四周（上下左右）是否为 1，它的上下左右再考察自己的四周是否为 1，遇到是 1 则可以加 1，遇到是 0 则不处理即可，说到这里基本就可以确定可以使用递归了，即有一个自己调用自己的过程；这里面有个细节，处理过的 1 需要置为 0，否则会有重复计算的问题。
代码如下：
/**
* @param {number[][]} grid
* @return {number}
*/
var maxAreaOfIsland = function(grid) {
if(grid === null || grid.length === 0)
return 0;
let res = 0;
for(let i = 0;i < grid.length;i++) {
for(let j = 0;j < grid[0].length;j++) {
if(grid[i][j] === 1)
res = Math.max(res, help(grid, i, j));
}
}
return res;
};
var help = function(grid, i, j) {
grid[i][j] = 0;
let sum = 1;
if(i > 0 && grid[i-1][j] === 1)
sum += help(grid, i-1, j);
if(i < grid.length-1 && grid[i+1][j] === 1)
sum += help(grid, i+1, j);
if(j > 0 && grid[i][j-1] === 1)
sum += help(grid, i, j-1);
if(j < grid[0].length-1 && grid[i][j+1] === 1)
sum += help(grid, i, j+1);
return sum;
}
这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。
V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。
V2EX is a community of developers, designers and creative people.