算法关键知识汇总

最近刷题的时候，会遇到定义Map，Set，二维数组等，还有深度/广度优先...等等，一开始对于这些的代码编写非常生疏，有想法但就是下不了笔，因此，想针对这方面的知识进行总结。

Map

Map 是一种键值对存储的数据结构，相比于普通对象 {}，它允许任何类型的键

let map = new Map();

// 添加元素
map.set('name', 'Alice');
map.set(1, 'Number Key');
map.set(true, 'Boolean Key');

// 获取元素
console.log(map.get('name')); // Alice
console.log(map.get(1)); // Number Key

// 删除元素
map.delete(1);

// 遍历
for (let [key, value] of map) {
    console.log(key, value);
}

常见方法：

• set(key, value): 添加键值对

• get(key): 获取值

• delete(key): 删除键值对

• has(key): 判断是否包含某个键

• size: 获取元素数量

• clear(): 清空 Map

Set

Set 是不重复值集合

let set = new Set();

// 添加元素
set.add(1);
set.add(2);
set.add(2); // 不会重复添加

// 检查是否存在
console.log(set.has(2)); // true

// 删除元素
set.delete(1);

// 遍历
for (let value of set) {
    console.log(value);
}

常见方法：

• add(value): 添加元素

• delete(value): 删除元素

• has(value): 判断元素是否存在

• size: 获取元素个数

• clear(): 清空 Set

二维数组

二维数组是数组的数组，常用于表示矩阵或棋盘等结构，一般题目的输入格式是：

['abcd', 'efgh', 'ijkl']

我们定义这个数组是charMatrix，首先确定行数和列数，也就是：

let row = charMatrix.length;
let col = charMatrix[0].length;

这时候我们要定义一个二维数组：

let charList = new Array();

for(let i = 0; i < row; i++) {
    charList[i] = new Array();
            
    for(let j = 0; j < col; j++) {
        charList[i][j] = 0;
    }
}

可以简化代码：

let charList = new Array(row);

for(let i = 0; i < charList.length; i++) {
    charList[i] = new Array(col).fill(0);
}

广度优先搜索

广度优先搜索（Breadth First Search, BFS）通常使用队列进行层级遍历

function bfs(matrix, startX, startY) {
    let queue = [[startX, startY]];
    let visited = new Set();
    visited.add(`${startX},${startY}`);

    while (queue.length > 0) {
        let [x, y] = queue.shift();
        console.log(matrix[x][y]);
        
        // 遍历四个方向
        let directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
        for (let [dx, dy] of directions) {
            let newX = x + dx, newY = y + dy;
            let key = `${newX},${newY}`;
            
            if (newX >= 0 && newY >= 0 && newX < matrix.length && newY < matrix[0].length && !visited.has(key)) {
                queue.push([newX, newY]);
                visited.add(key);
            }
        }
    }
}

深度优先搜索

深度优先搜索（Depth First Search, DFS）是一种递归或使用栈的搜索方式

1.递归实现

function dfs(matrix, i, j, visited) {
    if (i < 0 || j < 0 || i >= matrix.length || j >= matrix[0].length || visited[i][j]) {
        return;
    }
    visited[i][j] = true;
    
    // 递归搜索四个方向
    dfs(matrix, i + 1, j, visited);
    dfs(matrix, i - 1, j, visited);
    dfs(matrix, i, j + 1, visited);
    dfs(matrix, i, j - 1, visited);
}

2.栈实现

function dfsStack(matrix, startX, startY) {
    let stack = [[startX, startY]];
    let visited = new Set();
    
    while (stack.length > 0) {
        let [x, y] = stack.pop();
        let key = `${x},${y}`;
        
        if (visited.has(key)) continue;
        visited.add(key);
        
        // 处理当前节点
        console.log(matrix[x][y]);
        
        // 加入相邻节点（上下左右）
        let directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
        for (let [dx, dy] of directions) {
            let newX = x + dx, newY = y + dy;
            if (newX >= 0 && newY >= 0 && newX < matrix.length && newY < matrix[0].length) {
                stack.push([newX, newY]);
            }
        }
    }
}