LeetCode hot100

数据结构与算法的脑图

• 基础数据结构（必掌握）
  • 数组 & 字符串
    • 核心特性：连续内存、随机访问O(1)、增删O(n)
    • 刷题高频点：双指针、滑动窗口、前缀和、差分、字符串匹配(KMP)
    • 经典题型：两数之和、最长回文子串、滑动窗口最大值
  • 链表
    • 核心特性：非连续内存、顺序访问O(n)、增删O(1)（已知节点）
    • 刷题高频点：虚拟头节点、快慢指针、反转链表、环形链表
    • 经典题型：反转链表、合并两个有序链表、环形链表Ⅱ
  • 栈 & 队列
    • 栈：先进后出（FILO），核心操作push/pop/top
      • 高频场景：括号匹配、单调栈（接雨水、柱状图最大面积）
    • 队列：先进先出（FIFO），核心操作push/pop/front
      • 高频场景：BFS、单调队列（滑动窗口最大值）
    • 经典题型：有效的括号、用栈实现队列、滑动窗口最大值
  • 哈希表（字典/集合）
    • 核心特性：键值对存储、查询/增删O(1)（理想情况）
    • 刷题高频点：哈希映射（计数/去重）、哈希集合（存在性判断）
    • 经典题型：两数之和、字母异位词分组、最长连续序列
• 进阶数据结构（高频考点）
  • 树 & 二叉树
    • 基础概念：根节点、叶子节点、深度/高度、遍历方式
    • 核心遍历：前序/中序/后序（递归+迭代）、层序遍历（BFS）
    • 特殊二叉树：二叉搜索树(BST)、平衡二叉树(AVL)、完全二叉树
    • 经典题型：二叉树的层序遍历、验证二叉搜索树、路径总和
  • 堆（优先队列）
    • 核心特性：完全二叉树、大顶堆/小顶堆、插入/弹出O(logn)
    • 刷题高频点：topK问题、数据流中位数、贪心策略
    • 经典题型：数组中的第K个最大元素、数据流的中位数
  • 图
    • 基础表示：邻接矩阵、邻接表
    • 核心遍历：DFS（深度优先）、BFS（广度优先）
    • 高频算法：最短路径（Dijkstra/Floyd）、并查集（连通性）、拓扑排序
    • 经典题型：岛屿数量、课程表（拓扑排序）、网络延迟时间
  • 单调结构（单调栈/单调队列）
    • 核心思想：维护有序的栈/队列，降低时间复杂度
    • 适用场景：找下一个更大/更小元素、区间最值
    • 经典题型：每日温度、柱状图中最大的矩形、滑动窗口最大值
• 高级数据结构（提升效率）
  • 并查集（Disjoint Set Union, DSU）
    • 核心操作：查找(find)、合并(union)、路径压缩、按秩合并
    • 适用场景：连通性问题、分组问题
    • 经典题型：朋友圈、冗余连接、岛屿数量（进阶）
  • 前缀树（Trie树）
    • 核心特性：字符串前缀存储、高效查询前缀/单词
    • 适用场景：单词搜索、前缀匹配
    • 经典题型：实现Trie树、单词搜索Ⅱ
  • 线段树 & 树状数组
    • 线段树：区间查询、区间更新O(logn)，适用复杂区间操作
    • 树状数组：单点更新、前缀和查询O(logn)，适用简单区间操作
    • 经典题型：区域和检索 - 数组可修改、逆序对的数量
  • 哈希集合/映射进阶
    • 布隆过滤器：海量数据存在性判断（有一定误判率）
    • LRU缓存：最近最少使用，哈希表+双向链表实现
    • 经典题型：LRU缓存、LFU缓存
• 刷题策略 & 技巧
  • 按类型刷题：先刷基础结构，再攻进阶结构
  • 高频技巧：双指针、贪心、二分查找、递归/回溯、动态规划
  • 复杂度分析：时间复杂度（重点）、空间复杂度（优化方向）
  • 易错点：边界条件（空值、单元素）、索引越界、重复计算

数组

53. 最大子数组和

示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：
输入：nums = [1]
输出：1

示例 3：
输入：nums = [5,4,-1,7,8]
输出：23
  
class Solution {
    public int maxSubArray(int[] nums) {
        int preSum =0,maxAns = nums[0];
        for(int x:nums){
            preSum = Math.max(preSum+x,x);
            maxAns = Math.max(maxAns,preSum);
        }
        return maxAns;
        
    }
}

56. 合并区间

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
示例 3：

输入：intervals = [[4,7],[1,4]]
输出：[[1,7]]
解释：区间 [1,4] 和 [4,7] 可被视为重叠区间。
  
class Solution {
    public int[][] merge(int[][] intervals) {
        if(intervals.length ==0){
            return new int[0][2];
        }

        Arrays.sort(intervals,new Comparator<int[]>(){
            public int compare(int[] interval1,int[] interval2){
                return interval1[0] - interval2[0];
            }
        });
        List<int[]> merged = new ArrayList<int[]>();
        for(int i=0;i<intervals.length;i++){
            int L=intervals[i][0],R= intervals[i][1];
            // [1,3] [4,5] 当3<4 直接添加
            if(merged.size()==0 ||merged.get(merged.size()-1)[1]<L){
                merged.add(new int[]{L,R});
            }else{
                // [1,3] [2,5]-> [1,5]  
                // [1,6] [2,5]-> [1,6]  
                merged.get(merged.size()-1)[1] = 
                Math.max(merged.get(merged.size() -1)[1],R);
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }
}

189. 轮转数组

示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

示例 2:
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        int[] newArr = new int[n];
        for(int i=0;i<n;i++){
            newArr[ (i+k)%n ] = nums[i];
        }
        System.arraycopy(newArr,0,nums,0,n);
    }
}

238. 除了自身以外数组的乘积

示例 1:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]
示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];

        int[] L = new int[n];
        int[] R = new int[n];

        L[0] = 1;
        for(int i=1;i<n;i++){
            L[i] = nums[i-1] * L[i-1];
        }

        R[n -1] = 1;
        for(int i=n-2;i>=0;i--){
            R[i] = nums[i+1] * R[i+1];
        }
        for (int i = 0; i < n; i++) {
            res[i] = L[i] * R[i];
        }
        return res;
    }
}

###############################################################
核心技巧：双指针（快慢、左右）、滑动窗口、前缀和、模拟法。

重点题目：移动零、盛最多水的容器、三数之和、无重复字符的最长子串、接雨水。
###############################################################

———0128————数组
53.最大子数组和 -> 动态规划 记录可能性 选A,B
56.合并区间
189.轮转数组 取模
238.除了自身以外数组的乘积 左边乘积 右边乘积

———————矩阵
73.矩阵置零 - 辅助记录
54.螺旋矩阵 -> 注意边界
48.旋转图像
240.搜索二维矩阵 II

——————–字符串

双指针

###############################################################
核心技巧：用空间换时间，快速查找。常与数组、字符串结合。

重点题目：两数之和、字母异位词分组、最长连续序列。
###############################################################

———————哈希

###############################################################
核心技巧：虚拟头节点、双指针（找环、找中点）、反转链表。

重点题目：反转链表、环形链表、合并两个有序链表、LRU缓存机制。
###############################################################

———————链表

栈
堆
二叉树

回溯
二分查找
动态规划