Jeskson-微服务分布式

数据结构与算法

# 数据结构与算法

# 📋 学习目标

  • 掌握基本数据结构的实现原理
  • 理解算法的时间和空间复杂度
  • 能够选择合适的数据结构解决问题
  • 熟练实现常用算法

# 🏗️ 数据结构分类

# 线性结构

# 数组 (Array)

  • 特点：连续内存，随机访问O(1)
  • 应用：排序、查找、动态规划
  • 经典题目：
    • 两数之和
    • 最大子数组和
    • 旋转数组

# 链表 (Linked List)

  • 特点：动态内存，插入删除O(1)
  • 应用：LRU缓存、图的邻接表
  • 经典题目：
    • 反转链表
    • 合并两个有序链表
    • 环形链表检测

# 栈 (Stack)

  • 特点：后进先出(LIFO)
  • 应用：表达式求值、函数调用
  • 经典题目：
    • 有效的括号
    • 最小栈
    • 逆波兰表达式

# 队列 (Queue)

  • 特点：先进先出(FIFO)
  • 应用：BFS、任务调度
  • 经典题目：
    • 用栈实现队列
    • 滑动窗口最大值
    • 二叉树层序遍历

# 树形结构

# 二叉树 (Binary Tree)

  • 遍历方式：前序、中序、后序、层序
  • 应用：表达式树、决策树
  • 经典题目：
    • 二叉树的最大深度
    • 对称二叉树
    • 路径总和

# 二叉搜索树 (BST)

  • 特点：左子树 < 根 < 右子树
  • 应用：快速查找、范围查询
  • 经典题目：
    • 验证二叉搜索树
    • 二叉搜索树的最近公共祖先
    • 将有序数组转换为BST

# 堆 (Heap)

  • 特点：完全二叉树，父节点大于/小于子节点
  • 应用：优先队列、堆排序
  • 经典题目：
    • 数组中的第K个最大元素
    • 合并K个排序链表
    • 前K个高频元素

# 图结构

# 图的表示

  • 邻接矩阵：适合稠密图
  • 邻接表：适合稀疏图

# 图的遍历

  • 深度优先搜索(DFS)：递归或栈实现
  • 广度优先搜索(BFS)：队列实现

# 经典算法

  • 最短路径：Dijkstra、Floyd-Warshall
  • 最小生成树：Kruskal、Prim
  • 拓扑排序：Kahn算法、DFS

# 🎯 经典题目详解

# 1. 两数之和 🟢

题目：给定一个整数数组和目标值，找出数组中和为目标值的两个数的索引。

解法：哈希表

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[]{map.get(complement), i};
        }
        map.put(nums[i], i);
    }
    return new int[]{};
}

时间复杂度：O(n) 空间复杂度：O(n)

# 2. 反转链表 🟡

题目：反转一个单链表。

解法：迭代

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
  
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
  
    return prev;
}

时间复杂度：O(n) 空间复杂度：O(1)

# 3. 二叉树的最大深度 🟢

题目：给定一个二叉树，找出其最大深度。

解法：递归

public int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
  
    int leftDepth = maxDepth(root.left);
    int rightDepth = maxDepth(root.right);
  
    return Math.max(leftDepth, rightDepth) + 1;
}

时间复杂度：O(n) 空间复杂度：O(h)，h为树的高度

# 💡 解题技巧

# 数组相关

  1. 双指针技巧：左右指针、快慢指针
  2. 滑动窗口：固定/可变窗口大小
  3. 前缀和：快速计算区间和

# 链表相关

  1. 虚拟头节点：简化边界处理
  2. 快慢指针：检测环、找中点
  3. 递归思维：分解子问题

# 树相关

  1. 递归模板：明确递归函数定义
  2. 层序遍历：使用队列BFS
  3. 路径问题：回溯算法

# 图相关

  1. DFS模板：递归或栈实现
  2. BFS模板：队列实现
  3. 状态压缩：位运算优化

# 📚 推荐资源

# 书籍

  • 《算法导论》- 理论基础
  • 《数据结构与算法分析》- 实现细节
  • 《剑指Offer》- 面试必备

# 在线平台

  • LeetCode - 题目丰富
  • 牛客网 - 笔试练习
  • HackerRank - 国际平台

# 可视化工具

  • VisuAlgo - 算法可视化
  • Data Structure Visualizations - 数据结构动画

继续深入学习，掌握数据结构的精髓！🚀

动态规划