力扣 hot100知识点记录

图论

​​​​​​1. 208. 实现 Trie (前缀树)

b站知识点讲解：【【数据结构 10】Trie｜前缀树｜字典树】

可以理解为26叉树,c-'a' 将小写字母映射为 0～25 的索引

回溯

回溯是递归的副产品，只要有递归就会有回溯

回溯法，一般可以解决如下几种问题：

• 组合问题：N个数里面按一定规则找出k个数的集合
• 切割问题：一个字符串按一定规则有几种切割方式
• 子集问题：一个N个数的集合里有多少符合条件的子集
• 排列问题：N个数按一定规则全排列，有几种排列方式
• 棋盘问题：N皇后，解数独等等

17. 电话号码的字母组合

StringBuilder VS String，涉及到拼接，使用前者更高效

39. 组合总和

关于list的用法

https://www.qianwen.com/share/chat?share_id=d7a76970c0b7442c8460a4f5b0e80395

要保存多个path，就应该使用深拷贝

46. 全排列

在全排列的问题中，不能仅关注本层的元素判断，要注意上层已使用元素在后续新选择中的排除，因此需要使用used数组进行统计

131. 分割回文串

StringBuilder的作用是：作为当前候选子串的可变缓冲区

截取字符串子串：

22. 括号生成

• 固定长度路径 + 顺序构建→ 用char[]覆盖（高效）
• 每个if分支代表一种合法的决策
• 两个if是独立判断，可能都执行（产生两个子分支）

79. 单词搜索

基本类型在递归过程的值传递是传递副本，不改变原有值，所以必要时设置为全局变量

二分查找

74. 搜索二维矩阵

方法1：排除法

每一行>上一行,每一行中保持递增。由于这个特点，从右上角元素开始判断，可以整行整列的删除元素

方法2：二分查找法

这个矩阵类似可以依次展开为递增的一维数组

注意二维数组的右边界为m*n-1，左边界为0

//该元素在一维数组中的位置-->得到其在二维数组中的行与列 int x=matrix[mid/n][mid%n];

34. 在排序数组中查找元素的第一个和最后一个位置

思路：通过两次二分查找依次找到左边界和右边界，返回即可

//找第一个等于target的位置 if(nums[mid]==target){ first=mid; right=mid-1; } //最后一个等于target的位置 if(nums[mid]==target){ last=mid; left=mid+1; }

33. 搜索旋转排序数组

困惑点：二分查找针对的事有序数组，但旋转后的数组非有序。只保证局部数据是有序的

破题点：只旋转了一次，故我们将数组从中间分开成左右两部分的时候，一定有一部分的数组是有序的-------对有序的那一侧先进行判断，判断目标值是否在有序这一侧------若不在，变换区间left，right值，继续进行二分判断，每一次判断舍弃一半的区间

定理一：只有在顺序区间内才可以通过区间两端的数值判断target是否在其中。

定理二：判断顺序区间还是乱序区间，只需要对比 left 和 right 是否是顺序对即可，left <= right，顺序区间，否则乱序区间。

定理三：每次二分都会至少存在一个顺序区间

每一步都利用旋转数组的结构性质，确保至少一半区间可被高效排除

153. 寻找旋转排序数组中的最小值

二分的思想在于，每次淘汰一半（记住这个思想，是所有二分题目的关键）普遍规律如下：

思路：我们考虑数组中的最后一个元素 x：在最小值右侧的元素（不包括最后一个元素本身），它们的值一定都严格小于 x；而在最小值左侧的元素，它们的值一定都严格大于 x

收获：设计到排序数组以及排序数组的旋转，以及复杂度要求，注意思考能否通过二分查找排除范围

栈

20. 有效的括号

字符串转为字符数组方法：s.toCharArray()

解题思路：1. 利用栈的特性，栈相关的方法自己要熟悉；

2. 正常情况正常处理，剩下的事异常情况直接返回false即可。只要是左边的括号，先入栈，右边的括号，如果顶部合适，也继续弹出，剩下的情况是false可以提前结束判断。注意记得最后检测栈是否为空，以及最开始的栈数量是否为奇数，进行排除

贪心算法

贪心解题步骤：

• 将问题分解为若干个子问题
• 找出适合的贪心策略
• 求解每一个子问题的最优解
• 将局部最优解堆叠成全局最优解

121. 买卖股票的最佳时机

思路：买卖一次，什么时候获得的利润最大?

当在第i个元素卖出时，肯定是前i-1个元素最低价买入时，利润最大，动态更新整个数组的最大利润值和前面最小元素值

55. 跳跃游戏

在覆盖范围内更新最大的覆盖范围，不纠结具体是如何到达某一点，只要最大覆盖范围能到最后值即可

45. 跳跃游戏 II

思路：以最小的步数增加最大的覆盖范围，直到覆盖范围覆盖了终点，这个范围内最少步数一定可以跳到，不用管具体是怎么跳的，不纠结于一步究竟跳一个单位还是两个单位

核心思想：在当前这一跳能到达的所有位置中，一轮循环算一次，找出下一步能跳得最远的那个，作为下一次跳跃的目标

763. 划分字母区间

思路：在遍历的过程中相当于是要找每一个字母的边界，如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了。此时前面出现过所有字母，最远也就到这个边界了。

• 统计每一个字符最后出现的位置
• 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点

知识点：1. 用26个int[26]的元素数组来存储26个字母的最远值; 2.字符串转字符数组 char[] chars = s.toCharArray();

动态规划

区分：动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的

动规五部曲：

1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组

List<List<Integer>> result=new ArrayList<>(numRows);//List是一个接口，不可以通过new来实例化，常见的实现类有ArrayList,LinkedList

279. 完全平方数

本质（完全背包问题）：完全平方数就是物品（可以无限件使用），凑个正整数n就是背包，问凑满这个背包最少有多少物品？

遍历顺序：

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

dp数组含义：看本题要求的是什么

01背包+完全背包

01背包：一维数组求解时倒叙，完全背包遍历时正序

思路一：二维数组

1. dp数组：dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

2. 递推公式：

以上过程，抽象化如下：

• 不放物品i：背包容量为j，里面不放物品i的最大价值是dp[i - 1][j]。

• 放物品i：背包空出物品i的容量后，背包容量为j - weight[i]，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]且不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值

递归公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

初始化：dp[0][j] 和 dp[i][0]

思路二：一维数组

300. 最长递增子序列

核心思想：dp[i]表示i之前包括i的以nums[i]结尾（因为要比较结尾数字）的最长递增子序列的长度

for (int i = 1; i < dp.length; i++) { //对i之前的结尾序列进行判断 for (int j = 0; j < i; j++) { if (nums[i] > nums[j]) { dp[i] = Math.max(dp[i], dp[j] + 1); } } //结束完一个末尾值跟新比较一下res，因为最长序列可能在过程中出现 res = Math.max(res, dp[i]); }

1143. 最长公共子序列

思路：用一个二维数组dp[i][j]记录：下标为[0, i - 1]的字符串text1与下标为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]

为了减少第一行、第一列初始化时需遍历，这样的话dp[i][0]均为0，

72. 编辑距离

思路：两个单词都可以进行操作，与最长公共子序列求解思路接近，dp数组含义一样，递推公式中取{删除和增加的次数是一样的（一个字符串需要增加=另一个字符串需要）+替换的次数}

需要对第一行、第一列的数据进行操作。结合语境，进行初始化

堆

347. 前 K 个高频元素

思想：使用大顶堆或小顶堆求一个组合中前k个高频或者低频的元素

定义一个大小为k的大顶堆，在每次移动更新大顶堆的时候，每次弹出都把最大的元素弹出去了，

大顶推需要对所有元素进行排序，然后一次从队头弹出k个，就是出现频率前k高的元素。

也可以用小顶堆，因为要统计最大前k个元素，只有小顶堆每次将最小的元素弹出，最后小顶堆里积累的才是前k个最大元素

解题思路：

1. 统计频率
   • 用HashMap<Integer, Integer>记录每个数字出现的次数 ✅
2. 维护大小为 k 的最小堆
   • 堆中存储[数字, 频率]
   • 比较器按频率升序：(o1, o2) -> o1[1] - o2[1]→ 最小频率在堆顶 ✅
   • 这样堆里始终保留频率最高的 k 个元素（因为低频的会被poll()掉）✅
3. 最后弹出堆中所有元素作为结果
   • 虽然弹出顺序是“频率从小到大”，但题目不要求顺序，所以合法 ✅

🎯 这就是经典的“Top K 问题” + “最小堆优化”思路，时间复杂度 O(n log k)，空间 O(n)，非常高效！

215. 数组中的第K个最大元素

核心思想：

• 不排序整个数组
• 每次随机选一个基准值（pivot）
• 将数组划分为三部分：
  • 大于 pivot 的元素（big）
  • 等于 pivot 的元素（equal）
  • 小于 pivot 的元素（small）
• 根据k的位置，决定在哪一部分继续查找