力扣 hot100知识点记录

图论​​​​​​1. 208. 实现 Trie (前缀树)b站知识点讲解【【数据结构 10】Trie前缀树字典树】可以理解为26叉树,c-a 将小写字母映射为 025 的索引回溯回溯是递归的副产品只要有递归就会有回溯回溯法一般可以解决如下几种问题组合问题N个数里面按一定规则找出k个数的集合切割问题一个字符串按一定规则有几种切割方式子集问题一个N个数的集合里有多少符合条件的子集排列问题N个数按一定规则全排列有几种排列方式棋盘问题N皇后解数独等等17. 电话号码的字母组合StringBuilder VS String涉及到拼接使用前者更高效39. 组合总和关于list的用法https://www.qianwen.com/share/chat?share_idd7a76970c0b7442c8460a4f5b0e80395要保存多个path就应该使用深拷贝46. 全排列在全排列的问题中不能仅关注本层的元素判断要注意上层已使用元素在后续新选择中的排除因此需要使用used数组进行统计131. 分割回文串StringBuilder的作用是作为当前候选子串的可变缓冲区截取字符串子串22. 括号生成固定长度路径 顺序构建→ 用char[]覆盖高效每个if分支代表一种合法的决策两个if是独立判断可能都执行产生两个子分支79. 单词搜索基本类型在递归过程的值传递是传递副本不改变原有值所以必要时设置为全局变量二分查找74. 搜索二维矩阵方法1排除法每一行上一行,每一行中保持递增。由于这个特点从右上角元素开始判断可以整行整列的删除元素方法2二分查找法这个矩阵类似可以依次展开为递增的一维数组注意二维数组的右边界为m*n-1左边界为0//该元素在一维数组中的位置--得到其在二维数组中的行与列 int xmatrix[mid/n][mid%n];34. 在排序数组中查找元素的第一个和最后一个位置思路通过两次二分查找依次找到左边界和右边界返回即可//找第一个等于target的位置 if(nums[mid]target){ firstmid; rightmid-1; } //最后一个等于target的位置 if(nums[mid]target){ lastmid; leftmid1; }33. 搜索旋转排序数组困惑点二分查找针对的事有序数组但旋转后的数组非有序。只保证局部数据是有序的破题点只旋转了一次故我们将数组从中间分开成左右两部分的时候一定有一部分的数组是有序的-------对有序的那一侧先进行判断判断目标值是否在有序这一侧------若不在变换区间leftright值继续进行二分判断每一次判断舍弃一半的区间定理一只有在顺序区间内才可以通过区间两端的数值判断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();动态规划区分动态规划中每一个状态一定是由上一个状态推导出来的这一点就区分于贪心贪心没有状态推导而是从局部直接选最优的动规五部曲确定dp数组dp table以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组ListListInteger resultnew ArrayList(numRows);//List是一个接口不可以通过new来实例化常见的实现类有ArrayList,LinkedList279. 完全平方数本质完全背包问题完全平方数就是物品可以无限件使用凑个正整数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]均为072. 编辑距离思路两个单词都可以进行操作与最长公共子序列求解思路接近dp数组含义一样递推公式中取{删除和增加的次数是一样的一个字符串需要增加另一个字符串需要替换的次数}需要对第一行、第一列的数据进行操作。结合语境进行初始化堆347. 前 K 个高频元素思想使用大顶堆或小顶堆求一个组合中前k个高频或者低频的元素定义一个大小为k的大顶堆在每次移动更新大顶堆的时候每次弹出都把最大的元素弹出去了大顶推需要对所有元素进行排序然后一次从队头弹出k个就是出现频率前k高的元素。也可以用小顶堆因为要统计最大前k个元素只有小顶堆每次将最小的元素弹出最后小顶堆里积累的才是前k个最大元素解题思路统计频率用HashMapInteger, Integer记录每个数字出现的次数 ✅维护大小为 k 的最小堆堆中存储[数字, 频率]比较器按频率升序(o1, o2) - o1[1] - o2[1]→ 最小频率在堆顶 ✅这样堆里始终保留频率最高的 k 个元素因为低频的会被poll()掉✅最后弹出堆中所有元素作为结果虽然弹出顺序是“频率从小到大”但题目不要求顺序所以合法 ✅ 这就是经典的“Top K 问题” “最小堆优化”思路时间复杂度 O(n log k)空间 O(n)非常高效215. 数组中的第K个最大元素核心思想不排序整个数组每次随机选一个基准值pivot将数组划分为三部分大于 pivot 的元素big等于 pivot 的元素equal小于 pivot 的元素small根据k的位置决定在哪一部分继续查找