02-21 09:17 广州软件学院前端工程师发布于广东

关注

Part8.前端面试指南：前端算法试炼(1/5)

数据结构入门：常用数据结构详解

数据结构是计算机程序设计中一个重要的概念，它指的是在计算机内存中组织和存储数据的方式。合理的数据结构不仅可以提高程序的效率，也可以使代码更易于管理和维护。以下是几种常用的数据结构的介绍。

1. 数组（Array）

定义：数组是一组相同类型的元素集合，它们在内存中是连续存储的。
特点：
- 支持随机访问，通过索引可以直接访问数组中的任意元素。
- 大小固定，创建时需要定义长度，无法动态增减。
应用：存储静态数据、实现各种算法等。

2. 链表（Linked List）

定义：链表是一种由一系列节点组成的数据结构，每个节点包含数据和指向下一个节点的指针。
特点：
- 动态大小，能够高效地在链表中插入和删除元素。
- 不支持随机访问，访问某个元素需要逐个遍历。
应用：实现栈、队列等抽象数据结构。

3. 栈（Stack）

定义：栈是一种后进先出（LIFO）的数据结构，最后插入的元素最先被移除。
特点：
- 只允许在一端进行插入和删除操作。
- 常用操作有入栈（push）、出栈（pop）和查看栈顶元素（top）。
应用：用于函数调用管理、表达式求值、回溯算法等。

4. 队列（Queue）

定义：队列是一种先进先出（FIFO）的数据结构，最早插入的元素最早被移除。
特点：
- 允许在一端进行插入操作（入队），在另一端进行删除操作（出队）。
- 常见变种有循环队列和双端队列（Deque）。
应用：用于任务调度、进程管理等场景。

5. 哈希表（Hash Table）

定义：哈希表是一种基于哈希函数实现的数据结构，通过键值对（key-value）来存储数据。
特点：
- 允许通过键快速访问对应的值，平均时间复杂度为O(1)。
- 可能会发生哈希冲突（不同的键映射到同一个索引），需要处理冲突。
应用：实现快速查找、缓存等。

6. 树（Tree）

定义：树是一种分层的数据结构，由节点组成，节点通过边连接，具有父子关系。
特点：
- 每个树至少有一个根节点，节点可以有多个子节点。
- 常见类型：二叉树（二叉搜索树、平衡树）、B树、红黑树等。
应用：用于实现数据库索引、文件系统、解析表达式等。

7. 图（Graph）

定义：图是一种由顶点（点）和边（连接顶点的线）组成的数据结构，可以表示复杂的关系。
特点：
- 可以是有向图或无向图，边可以带权重。
- 常用表示方法包括邻接矩阵和邻接表。
应用：社交网络、导航系统、网络流等。

8. 堆（Heap）

定义：堆是一种特殊的完全二叉树，分为最大堆和最小堆，最大堆每个节点都大于等于其子节点，最小堆则相反。
特点：
- 支持动态插入和删除操作，常用来实现优先队列。
- 可以高效地获取最大或最小值。
应用：优先队列、图算法（如Dijkstra算法）等。

总结

数据结构是软件开发中的基石，选择合适的数据结构可以显著提高程序的性能和可维护性。了解每种数据结构的优缺点及其应用场景，有助于开发者在解决问题时做出更好的选择。在实际开发中，通常会结合使用多种数据结构，以满足不同的需求。

算法实践：常见算法题深度剖析

以下是一些常见的算法题及其解析，提供相应的 JavaScript 代码示例。这些题涵盖排序、搜索、动态规划等基本算法，有助于提高算法思维。

1. 两数之和 (Two Sum)

题目：给定一个整数数组 nums 和一个目标值 target，请你在数组中找到和为目标值的那两个整数，并返回它们的索引。

解析：

使用哈希表存储遍历过的元素及其索引，逐一检查目标值减去当前元素是否在哈希表中。
时间复杂度：O(n)，空间复杂度：O(n)。

function twoSum(nums, target) {
    const map = new Map();
    
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (map.has(complement)) {
            return [map.get(complement), i];
        }
        map.set(nums[i], i);
    }
    
    return [];  // 如果没有找到，返回空数组
}

2. 冒泡排序 (Bubble Sort)

题目：实现冒泡排序算法，对给定数组进行排序。

解析：

冒泡排序的基本思想是重复地走访过要排序的元素，比较相邻的元素并交换顺序不正确的元素，直到没有需要交换的元素为止。
时间复杂度：O(n^2)，空间复杂度：O(1)。

function bubbleSort(arr) {
    const n = arr.length;
    
    for (let i = 0; i < n - 1; i++) {
        let swapped = false;
        for (let j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
                swapped = true;
            }
        }
        // 如果没有交换，证明已排序
        if (!swapped) break;
    }
    
    return arr;
}

3. 爬楼梯 (Climbing Stairs)

题目：假设你正在爬楼梯。需要 n 阶楼梯，每次可以爬 1 阶或 2 阶，你有多少种不同的方法可以爬到楼顶？

解析：

使用动态规划，设 dp[i] 表示爬到第 i 阶楼梯的不同方法，状态转移方程为 dp[i] = dp[i - 1] + dp[i - 2]。
时间复杂度：O(n)，空间复杂度：O(1)。

function climbStairs(n) {
    if (n <= 2) return n;
    
    let first = 1, second = 2;
    
    for (let i = 3; i <= n; i++) {
        const temp = second;
        second = first + second;
        first = temp;
    }
    
    return second;
}

4. 最长公共前缀 (Longest Common Prefix)

题目：编写一个函数来查找字符串数组中的最长公共前缀。

解析：

先将第一个字符串作为前缀，然后逐个与数组中的每个字符串进行比较，更新前缀。
时间复杂度：O(n * m)，其中 n 是字符串数组的长度，m 是最小字符串的长度。

function longestCommonPrefix(strs) {
    if (!strs.length) return "";
    
    let prefix = strs[0];
    
    for (let i = 1; i < strs.length; i++) {
        while (strs[i].indexOf(prefix) !== 0) {
            prefix = prefix.substring(0, prefix.length - 1);
            if (prefix === "") return "";
        }
    }
    
    return prefix;
}

5. 合并区间 (Merge Intervals)

题目：给出一个区间的集合，请合并所有重叠的区间。

解析：

首先将区间按起始位置进行排序，然后遍历排序后的区间，合并重叠的区间。
时间复杂度：O(n log n)，空间复杂度：O(n)。

function merge(intervals) {
    if (intervals.length === 0) return [];
    
    // 按区间开始位置排序
    intervals.sort((a, b) => a[0] - b[0]);
    
    const merged = [intervals[0]];
    
    for (let i = 1; i < intervals.length; i++) {
        const currentInterval = intervals[i];
        const lastMerged = merged[merged.length - 1];
        
        // 如果当前区间与最后合并的区间重叠
        if (currentInterval[0] <= lastMerged[1]) {
            lastMerged[1] = Math.max(lastMerged[1], currentInterval[1]);
        } else {
            merged.push(currentInterval);
        }
    }
    
    return merged;
}

以上是常见算法题的解析和 JavaScript 代码示例。每一道题目都可以帮助加深对算法的理解和运用。

数据结构挑战：常见数据结构题解析

以下是一些常见的数据结构题目及其解析，提供相应的 JavaScript 代码示例。这些题目涵盖栈、队列、链表、二叉树等数据结构，有助于提高对数据结构的理解和应用能力。

1. 有效的括号 (Valid Parentheses)

题目：给定一个只包含 (、)、{、}、[ 和 ] 的字符串，判断字符串是否有效。有效字符串需满足：左括号必须用相应的右括号闭合，且闭合顺序正确。

解析：

使用栈存储左括号，遇到右括号时检查栈顶元素是否匹配。
时间复杂度：O(n)，空间复杂度：O(n)。

function isValid(s) {
    const stack = [];
    const mapping = { ')': '(', '}': '{', ']': '[' };
    
    for (const char of s) {
        if (char in mapping) {
            const topElement = stack.length > 0 ? stack.pop() : '#';
            if (mapping[char] !== topElement) {
                return false;
            }
        } else {
            stack.push(char);
        }
    }
    
    return stack.length === 0;
}

2. 反转链表 (Reverse Linked List)

题目：反转一个单链表。

解析：

使用三个指针（prev、current、next）逐一反转链表中的节点。
时间复杂度：O(n)，空间复杂度：O(1)。

function ListNode(val, next = null) {
    this.val = val;
    this.next = next;
}

function reverseList(head) {
    let prev = null;
    let current = head;
    
    while (current) {
        const nextNode = current.next; // 记录下一个节点
        current.next = prev;            // 反转当前节点指向
        prev = current;                 // 移动 prev 到当前节点
        current = nextNode;             // 移动到下一个节点
    }
    
    return prev; // prev 现在是新头节点
}

3. 用栈实现队列 (Implement Queue using Stacks)

题目：使用两个栈实现队列，支持 push 和 pop 操作。

解析：

使用一个栈（inStack）来入队，出队时将 inStack 中的元素转移到另一个栈（outStack），然后出栈。
时间复杂度：每个操作平均 O(1)，最坏情况为 O(n)。

class MyQueue {
    constructor() {
        this.inStack = [];
        this.outStack = [];
    }

    push(x) {
        this.inStack.push(x);
    }

    pop() {
        this._moveInToOut();
        return this.outStack.pop();
    }

    peek() {
        this._moveInToOut();
        return this.outStack[this.outStack.length - 1];
    }

    empty() {
        return this.inStack.length === 0 && this.outStack.length === 0;
    }

    _moveInToOut() {
        if (this.outStack.length === 0) {
            while (this.inStack.length > 0) {
                this.outStack.push(this.inStack.pop());
            }
        }
    }
}

4. 二叉树的层序遍历 (Binary Tree Level Order Traversal)

题目：给定一个二叉树，返回其节点值的层序遍历（从左到右, 从上到下）。

解析：

使用队列实现广度优先搜索（BFS），每次将当前层的节点值添加到结果列表。
时间复杂度：O(n)，空间复杂度：O(n)。

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function levelOrder(root) {
    const result = [];
    if (!root) return result;
    
    const queue = [root]; // 初始化队列

    while (queue.length > 0) {
        const levelSize = queue.length;
        const currentLevel = [];
        
        for (let i = 0; i < levelSize; i++) {
            const currentNode = queue.shift(); // 出队
            currentLevel.push(currentNode.val); // 记录当前节点值
            
            // 将子节点加入队列
            if (currentNode.left) queue.push(currentNode.left);
            if (currentNode.right) queue.push(currentNode.right);
        }

        result.push(currentLevel); // 将当前层结果加入结果列表
    }

    return result;
}

5. 合并两个排序链表 (Merge Two Sorted Lists)

题目：将两个有序链表合并为一个新的有序链表，并返回新链表的头节点。

解析：

使用一个虚拟头节点，遍历两个链表，比较节点值，依次将较小的节点连接到结果链表中。
时间复杂度：O(n + m)，空间复杂度：O(1)。

function mergeTwoLists(l1, l2) {
    const dummy = new ListNode(0); // 虚拟头节点
    let current = dummy;

    while (l1 !== null && l2 !== null) {
        if (l1.val < l2.val) {
            current.next = l1;
            l1 = l1.next;
        } else {
            current.next = l2;
            l2 = l2.next;
        }
        current = current.next; // 移动到当前节点
    }

    // 将未处理完的链表连接到结果链表
    if (l1 !== null) {
        current.next = l1;
    } else {
        current.next = l2;
    }

    return dummy.next; // 返回合并后的链表头
}

以上是常见的数据结构题目的解析和 JavaScript 代码示例。每一道题都可以帮助加深对数据结构的理解，增强编程能力。