Hot100部分

普通数组最大子数组和dp[i]表示以第 i 个元素结尾的最大子数组和通过判断前序子数组和是否为正dp[i -1]0决定是否延续合并区间排序贪心 所有区间按左端点升序排序再遍历区间若当前区间与结果列表中最后一个区间重叠则更新其右端点为两者最大值否则直接加入结果列表轮转数组先将数组整体反转再分别反转前 k 个元素和剩余元素k 对数组长度取模通过三次反转实现数组向右旋转 k 步的效果除了自身意外的数组的乘积先正向遍历数组将每个元素左侧所有数的乘积存入结果数组再反向遍历累积右侧所有数的乘积与结果数组中对应位置的左侧乘积相乘得到每个元素除自身外的乘积缺失的的第一个数组哈希归位通过原地交换将数组中 1~n 范围内的正整数归位到其对应位置数值 x 对应下标 x-1再遍历数组找到第一个位置与数值不匹配的下标 1 即为缺失的最小正整数若全部匹配说明缺失的是 n1。链表相交链表两个指针分别从两个链表头节点出发遍历完自身链表后跳至另一链表的头节点继续遍历当两指针相遇时相遇节点即为两链表第一个相交节点反转链表借助 pre和 cur双指针遍历链表通过临时变量tmp保存 cur 的下一个节点逐个将 cur 的 next 指向 pre 完成节点反转回文链表先通过快慢指针找到链表的中间节点反转中间节点开始的后半段链表再将原链表前半段与反转后的后半段逐个比对节点值全部相等则为回文链表否则不是环形链表快慢指针相遇则有环环形链表Ⅱ和技巧里寻找重复数一样先用快慢指针找到环内相遇点再让头指针与慢指针从起点和相遇点同步单步移动二者相遇的位置即为环的入口合并两个有序链表mergeTwoLists函数直接合并比较l1和l2的头结点哪个大两数相加借助虚拟头节点构建结果链表循环累加两个逆序链表的对应节点值与进位逐位通过取余得到当前位结果、取商更新进位直至链表遍历完毕且无进位最终返回虚拟头节点的下一个节点删除链表的倒数第n个节点想象一把尺子也要创建一个虚拟头结点防止删第一个元素长度为n从左到右平移尺子左端点就是倒数第n个两两相交链表的节点递归链表为空或仅含一个节点” 为终止条件将整体问题拆解为 “处理当前前两个节点” 和 “递归处理剩余子链表” 两部分K个一组翻转链表统计链表总节点数以哨兵节点dummy为辅助循环将链表按每 k 个节点为一组进行反转每组反转完成后重新拼接该组与前后链表随机链表的赋值通过 HashMap 建立原链表节点与仅复制了值的新节点的一一映射关系再遍历原链表利用该映射为每个新节点设置对应的 next 和 random 指针指向新节点而非原节点排序链表基于归并排序的分治思想先通过快慢指针找到链表中点递归将链表拆分为左右子链并各自排序再合并两个有序子链表得到整体有序的链表合并k个升序链表链表排序1个循环用ans维护结果LRU缓存LRU 缓存是遵循「最近最少使用」淘汰规则的缓存结构缓存容量满时会淘汰最久未被访问的元素保证常用数据优先留存解题核心是利用LinkedHashMap的插入 / 访问有序性通过 “删除再插入” 将访问 / 更新的元素标记为最近使用移至链表尾部容量满时删除链表头部的最久未用元素二叉树前面的题目都是简单dfs二叉树的直径后序遍历递归计算每个节点的左右子树深度同时记录以该节点为拐点的路径最大节点数层序遍历BFS队列实现二叉树的层序遍历先将根节点入队每次循环获取当前队列大小即当前层节点数遍历处理当前层所有节点并收集值同时将子节点入队二叉树的右视图同层序遍历将有序数组转化为二叉搜树和链表类似都是用分治递归但是链表找中点要快慢指针选取有序数组的中间元素作为当前子树的根节点递归将左半区间数组构建为左子树、右半区间数组构建为右子树验证二叉搜索树利用特性中序遍历结果严格递增二叉搜索树第k小的元素利用二叉树中序遍历结果严格递增特性进行中序遍历遍历过程中对节点计数通过递减 k 实现当 k 递减至 0 时当前节点值即为第 k 小的元素二叉树展开为链表先前序遍历将二叉树的所有节点按顺序存入列表再遍历列表重新拼接节点将每个节点的左子树置空右子树指向列表中的下一个节点从前序与中序遍历构造二叉树用哈希表存储中序遍历的元素索引前序遍历的首个元素作为当前根节点根据根节点在中序数组中的位置分割左右子树递归构建整棵二叉树。路径总和Ⅲ通过前缀和 DFS 回溯遍历二叉树用哈希表记录前缀和出现次数快速统计和为目标值的路径数量递归后回溯保证分支独立。二叉树的最近公共祖先递归终止条件为遇到空节点、p 或 q 节点直接返回当前节点。分别遍历左右子树单侧无结果返回另一侧两侧均有结果则当前节点为最终答案二叉树的最大路径和采用后序递归遍历以每个节点为路径最高点计算左 右 自身的路径和并更新全局最大值递归返回当前节点能向上提供的最大单链贡献值回溯全排列回溯算法递归枚举所有数字组合用used数组标记已选数字避免重复path记录当前排列排列填满时保存副本递归后撤销选择回溯最终穷举得到所有全排列子集通过startIndex控制只能从当前位置往后选元素避免生成重复子集递归时先把当前路径直接加入结果电话号码的组合和全排列的思路很像先建立数字与字母的映射表逐位遍历数字对应的字母并拼接拼完所有数字位就保存组合递归后撤销最后拼接的字母回溯最终穷举所有合法的字母组合组数总和先排序数组通过固定起始下标避免重复组合递归累加数值等于目标值时保存组合超过则直接终止循环最后回溯撤销选择括号生成回溯满足两个规则左括号比n小能随便加右括号比左括号少才能加总的字符数等于了2n停止动态规划爬楼梯dp[i] dp[i -1] dp[i - 2]杨辉三角每一个位置【i,j】的值为它正上方的值【i - 1,j】和它左上方【i - 1,j - 1】的值相加获得每行的第一个位置j0和最后一个位置ji直接赋值为 1打家劫舍dp[i] Math.max(dp[i - 1],dp[i -2] nums[i])注以下三个题格式化思路很橡完全平方数、零钱兑换、单词拆分完全平方数外层遍历目标数(1到n)内层遍历所有其平方小于i的数j²≤i 组成 i 的最少完全平方数个数为dp[i - j * j]的最小值 1零钱兑换外层遍历目标金额 i1 到 amount内层遍历所有硬币 coins [j]组成 i 的最少硬币个数为 dp [i - coins [j]] 的最小值 1补无法凑出的情况初始化dp的每个值均为amount1dp [amount] 超过 amount 则返回 - 1单词拆分外层遍历字符串前 i 个字符i 从 1 到 s.length ()内层遍历拆分点 jj 从 0 到 i-1若 dp [j] 为 true 且子串 s [j,i) 在字典中则 dp [i] 为 true最长递增子序列dp [i] 为以每个元素 nums [i] 结尾的最长递增子序列长度初始值为1遍历其之前所有更小的元素 nums [j] 并将 dp [i] 更新为 dp [j]1 的最大值乘积最大子数组两数组分别维护每个位置的最大值和最小值当前位置的乘积最大值为Math.max(当前值当前值*上一索引的最大值上一索引的最小值)分割等和子集转为01背包问题dp[j]记录容量 j 背包能装的最大和逆序遍历容量避免重复选数通过dp[target] target判断是否可分割最长有效括号dp[i]为以第i个字符结尾的最长有效括号长度仅当s[i]为)时更新若前一个字符是(则直接匹配加 2 并衔接前序有效长度若前一个是)则向前找匹配的(并累加嵌套 / 衔接的有效长度最终取dp数组最大值。多维动态规划*不同路径初始化后 dp[i][j] dp[i - 1][j] dp[i][j - 1];*最小路径和初始化后 dp[i][j] Math.min(dp[i - 1][j],dp[i][j - 1]) grid[i][j];注以下三题都是字符串相关的多维dp最长回文子串dp[i][j]表示字符串s中从索引i到j的子串是否为回文通过固定右边界j左边界i从0到j-1遍历若两端字符相等且内部子串s[i1..j-1]是回文则s[i..j]是回文同时记录最长回文的起始位置和长度最长公共子序列dp[i][j]表示text1前i个字符和text2前j个字符的最长公共子序列长度。遍历两个字符串若当前字符相等则dp[i][j] dp[i-1][j-1] 1否则取dp[i-1][j]和dp[i][j-1]的最大值编辑距离dp[i][j]表示将word1的前i个字符转换成word2的前j个字符所需的最少操作次数若当前字符相等则直接继承dp[i-1][j-1]无需对当前位操作若不等则取删除dp[i-1][j]1、插入dp[i][j-1]1、替换dp[i-1][j-1]1三者的最小值。技巧只出现一次的数字任何数异或0都为本身相同位异或为0不同位或为1循环异或返回多数元素排序后找中位数颜色分类双指针用 p0/p1 标记 0 和 1 的待填充位置通过先占 2 的位再反向填充 0/1的单遍历策略原地完成三色排序。下一个排列从后往前找到第一个升序对的左边界在其右侧找到比它大的最小数交换最后反转该边界右侧的元素以此得到字典序下最小的更大排列寻找重复数将数组映射为带环链表先用快慢指针找到环内相遇点再让头指针与慢指针从起点和相遇点同步单步移动二者相遇的位置即为环的入口也就是数组中的重复数