跳到文档正文
数据结构 / 二维数组
04 / 18
我们的可视化工具扩展到二维数组，将其表示为矩形网格。每个单元格显示其值，网格布局自然地展示了二维数组的行列结构。该工具提供行列索引，使得理解元素位置和访问模式变得容易。
在操作过程中，该工具突出显示当前访问的元素，同时显示行列索引。这种视觉反馈对于理解嵌套循环和复杂的矩阵操作特别有价值。
让我们看看一些常见的二维数组算法及其可视化效果：
// @ignore-function-tree
function matrixMultiply(A, B) {
if (A[0].length !== B.length) {
return null; // 维度无效
}
const rowsA = A.length;
const colsA = A[0].length;
const colsB = B[0].length;
const result = Array(rowsA).fill().map(() => Array(colsB).fill(0));
for (let i = 0; i < rowsA; i++) {
for (let j = 0; j < colsB; j++) {
for (let k = 0; k < colsA; k++) {
result[i][j] += A[i][k] * B[k][j];
}
}
}
return result;
}
// 使用示例
const A = [[1, 2], [3, 4]];
const B = [[5, 6], [7, 8]];
const result = matrixMultiply(A, B);
// @ignore-function-tree
function transpose(matrix) {
const rows = matrix.length;
const cols = matrix[0].length;
const result = Array(cols).fill().map(() => Array(rows).fill(0));
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
result[j][i] = matrix[i][j];
}
}
return result;
}
// 使用示例
const matrix = [[1, 2, 3], [4, 5, 6]];
const transposed = transpose(matrix);
// @ignore-function-tree
function spiralOrder(matrix) {
if (!matrix.length) return [];
const result = [];
let top = 0, bottom = matrix.length - 1;
let left = 0, right = matrix[0].length - 1;
while (top <= bottom && left <= right) {
// 向右遍历
for (let j = left; j <= right; j++) {
result.push(matrix[top][j]);
}
top++;
// 向下遍历
for (let i = top; i <= bottom; i++) {
result.push(matrix[i][right]);
}
right--;
if (top <= bottom) {
// 向左遍历
for (let j = right; j >= left; j--) {
result.push(matrix[bottom][j]);
}
bottom--;
}
if (left <= right) {
// 向上遍历
for (let i = bottom; i >= top; i--) {
result.push(matrix[i][left]);
}
left++;
}
}
return result;
}
// 使用示例
const matrix = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
];
const result = spiralOrder(matrix);
// @ignore-function-tree
function diagonalTraverse(matrix) {
if (!matrix.length) return [];
const rows = matrix.length;
const cols = matrix[0].length;
const result = [];
for (let d = 0; d < rows + cols - 1; d++) {
const temp = [];
// 找到当前对角线的行和列
let r = d < cols ? 0 : d - cols + 1;
let c = d < cols ? d : cols - 1;
// 收集对角线上的元素
while (r < rows && c >= 0) {
temp.push(matrix[r][c]);
r++;
c--;
}
// 对偶数对角线进行反转
if (d % 2 === 0) {
result.push(...temp.reverse());
} else {
result.push(...temp);
}
}
return result;
}
// 使用示例
const matrix = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
];
const result = diagonalTraverse(matrix);
// @ignore-function-tree
function bfsShortestPath(grid, start, end) {
if (!grid.length || grid[start[0]][start[1]] === 1 || grid[end[0]][end[1]] === 1) {
return -1;
}
const rows = grid.length;
const cols = grid[0].length;
const searchPath = [[start[0], start[1], 0]]; // [x, y, 距离]
const visited = new Set([`${start[0]},${start[1]}`]);
while (searchPath.length) {
const [x, y, dist] = searchPath.shift();
if (x === end[0] && y === end[1]) {
return dist;
}
const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
for (const [dx, dy] of directions) {
const newX = x + dx;
const newY = y + dy;
const key = `${newX},${newY}`;
if (newX >= 0 && newX < rows &&
newY >= 0 && newY < cols &&
grid[newX][newY] === 0 &&
!visited.has(key)) {
visited.add(key);
searchPath.push([newX, newY, dist + 1]);
}
}
}
return -1;
}
// 使用示例
const grid = [
[0, 1, 0],
[0, 1, 0],
[0, 0, 0]
];
const start = [0, 0];
const end = [2, 0];
const shortestDistance = bfsShortestPath(grid, start, end);
// @ignore-function-tree
function maximalSquare(matrix) {
if (!matrix.length) return 0;
const rows = matrix.length;
const cols = matrix[0].length;
const dp = Array(rows + 1).fill().map(() => Array(cols + 1).fill(0));
let maxSide = 0;
for (let i = 1; i <= rows; i++) {
for (let j = 1; j <= cols; j++) {
if (matrix[i-1][j-1] === '1') {
dp[i][j] = Math.min(
dp[i-1][j],
dp[i][j-1],
dp[i-1][j-1]
) + 1;
maxSide = Math.max(maxSide, dp[i][j]);
}
}
}
return maxSide * maxSide;
}
// 使用示例
const matrix = [
["1", "0", "1", "0", "0"],
["1", "0", "1", "1", "1"],
["1", "1", "1", "1", "1"],
["1", "0", "0", "1", "0"]
];
const maxArea = maximalSquare(matrix);
// @ignore-function-tree
function uniquePaths(m, n) {
// 初始化 dp 数组
const dp = Array(m).fill().map(() => Array(n).fill(1));
// 填充 dp 数组
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];
}
// 使用示例
const rows = 3;
const cols = 7;
const totalPaths = uniquePaths(rows, cols);