# 考察数组下标规律和边界

### 杨辉三角

LeetCode.118，难度简单

[ [1],

[1,1],

[1,2,1],

[1,3,3,1],

[1,4,6,4,1] ]

#### 思路

1. arr2[0] = 1
2. arr2[1] = arr1[0] + arr1[1]
3. arr2[2] = arr1[1] + arr1[2]
4. arr[3] = 1

• 遍历arr1，index=0时，arr2.push(1)
• 如果index=arr1.length-1，arr2.push(1)
• 否则，arr2.push(arr1[index] + arr1[index+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，难度中等

[ 1, 2, 3 ],

[ 4, 5, 6 ],

[ 7, 8, 9 ]

]

#### 思路

1. (0,0)
2. (0,1), (1,0)
3. (2,0), (1,1), (0,2)
4. (0,3), (1,2), (2,1)
5. (2,2), (1,3)
6. (2,3)

[

A, B, C, D,

E, F, G, H,

I, J, K, L

]

• 按打印一次对角线来算，一共要打印6次，也就是行数+列数-1次
• 按最开始那一次算第count=0次的话，如果count小于行数，那x=count且y=count-x，否则x=行数-1且y=count-x，对于列数来说也是一样的道理

#### 代码

/**
* @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，难度中等

[ 1, 2, 3 ],

[ 4, 5, 6 ],

[ 7, 8, 9 ] ]

[1, 2, 3, 4],

[5, 6, 7, 8],

[9,10,11,12] ]

#### 代码

/**
* @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，难度中等

[[1,1,0],

[1,1,0],

[0,0,1]]

[[1,1,0],

[1,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,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]]

[[0,0,0,0,0,0,0,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;
}

|
9天前
|
NoSQL Java 关系型数据库
BAT最新java800+合集面试复盘，能掌握80%就去进BATJTMD

55 0
|
7月前
|

【面试必刷TOP101】二分查找-I & 二维数组中的查找
【面试必刷TOP101】二分查找-I & 二维数组中的查找
29 0
|
9天前
(力扣)面试题04. 二维数组中的查找
(力扣)面试题04. 二维数组中的查找
23 0
|
2天前
|
C++
【一刷《剑指Offer》】面试题 3：二维数组中的查找
【一刷《剑指Offer》】面试题 3：二维数组中的查找
7 0
|
7天前
|
JavaScript 前端开发 算法
JQuery 基本使用，2024BAT大厂Web前端社招面试题
JQuery 基本使用，2024BAT大厂Web前端社招面试题
6 0
|
7天前
|

Angular 调用导入百度地图API接口，2024春招BAT面试真题详解
Angular 调用导入百度地图API接口，2024春招BAT面试真题详解
12 1
|
7天前
|

2024年Android最新知识体系最强总结(全方面覆盖Android知识结构，BAT面试&学习进阶)
2024年Android最新知识体系最强总结(全方面覆盖Android知识结构，BAT面试&学习进阶)
14 0
|
9天前
|

BAT等大厂年薪30W+面试清单：JVM\MySQL\设计模式\分布式\微服务

99 0
|
9天前
LeetCode(面试题：二维数组中的查找)
LeetCode(面试题：二维数组中的查找)
22 0
|
8月前
|

60 1