LeetCode中解决问题讨论技巧

LeetCode中解决问题讨论技巧

🧠 一、暴力枚举（Brute Force）

• 特点：直接枚举所有可能性，逐个检查是否满足条件。
• 适用场景：数据量较小时，作为初步思考方向或对数值范围明确时可用。
• 典型题目：两数之和、全排列。

---

🔁 二、双指针（Two Pointers）

• 常见形式：

  • 快慢指针（判断链表是否有环）
  • 左右夹逼（适用于有序数组/字符串/子数组）
• 适用题型：排序数组、字符串匹配、滑动窗口、链表等。
• 典型题目：盛最多水的容器、三数之和、删除有序数组中的重复项。

---

🔍 三、哈希表（Hash Map / Set）

• 用途：

  • 快速查找是否存在某元素
  • 记录频率、前缀和等中间状态
• 适用题型：查重问题、频率统计、前缀和问题。
• 典型题目：两数之和、最长无重复子串、和为K的子数组。

---

🧮 四、前缀和与差分数组（Prefix Sum / Difference）

• 用途：

  • 优化区间求和时间复杂度
  • 快速处理区间更新
• 适用题型：区间频繁查询与更新类题目。
• 典型题目：区域和检索、和为K的子数组。

---

🌊 五、滑动窗口（Sliding Window）

• 核心思想：维护一个窗口（通常是子数组或子串），滑动更新解。
• 适用题型：最小覆盖子串、最长子串、固定长度子数组。
• 典型题目：最小覆盖子串、无重复字符的最长子串。

---

⛓️ 六、链表操作（Linked List）

• 重点技巧：

  • 虚拟头结点 dummy
  • 快慢指针找中点或环

• 典型题目：链表反转、合并链表、判断是否有环。

---

🔢 七、排序（Sort）+ 二分查找（Binary Search）

• 排序技巧：

  • 快排、归并、桶排等

• 二分查找用途：

  • 找上下界、满足条件的最小/最大值

• 典型题目：搜索插入位置、寻找旋转数组最小值。

---

📊 八、栈与单调栈（Stack / Monotonic Stack）

• 用途：

  • 括号匹配、逆序遍历、维护最大/最小值位置

• 典型题目：每日温度、柱状图中最大的矩形。

---

🌳 九、树与二叉树（Tree / Binary Tree）

• 常见解法：

  • 递归前中后序遍历
  • BFS层序遍历（使用队列）
  • DFS递归/非递归实现

• 典型题目：对称二叉树、二叉树最大深度、二叉搜索树验证。

---

🗺️ 十、图与图算法（Graph / DFS / BFS / 并查集）

• 主要技巧：

  • DFS/BFS 图遍历
  • 拓扑排序
  • 并查集（Union Find）判断连通性

• 典型题目：岛屿数量、课程表、冗余连接。

---

🔄 十一、回溯（Backtracking）

• 本质：枚举所有可能解 + 剪枝
• 适用题型：排列组合、子集、数独等。
• 典型题目：N皇后问题、子集、组合总和。

---

🔣 十二、动态规划（Dynamic Programming，DP）

• 常见类型：

  • 一维/二维DP
  • 状态压缩DP（位运算）
  • 记忆化搜索（Top-down）
  • 完全背包 / 01背包

• 典型题目：打家劫舍、编辑距离、最长公共子序列、零钱兑换。

---

📐 十三、位运算（Bit Manipulation）

• 技巧：判断奇偶、交换变量、集合子集表示等。
• 典型题目：只出现一次的数字、汉明距离、子集生成。

---

📌 十四、贪心算法（Greedy）

• 核心思想：每一步都选择当前最优，希望得到全局最优。
• 典型题目：跳跃游戏、合并区间、分发饼干。

---

🔄 十五、并查集（Union-Find）

• 用途：判断连通性、集合合并、路径压缩
• 典型题目：冗余连接、朋友圈数量。

---

📚 十六、字典树（Trie）

• 适用题型：前缀匹配、单词搜索、自动补全
• 典型题目：实现Trie、单词搜索 II。

---

🧮 十七、数学技巧（Math）

• 质数筛选（埃氏筛）
• 模运算
• 最大公约数（GCD）、最小公倍数（LCM）
• 快速幂
• 数论基础题等