题目思路1.两数之和哈希表2.两数相加链表操作3. 无重复字符的最长子串滑动窗口循环扩左不断尝试扩右Set即可4. 寻找两个正序数组的中位数5.最长回文子串从中间向两边扩展注意整个字符串都是回文串的边界情况10.正则表达式匹配动态规划要在两个字符前都加个空格11.盛水最多的容器左右双指针贪心15.三数之和排序双指针剪枝17.电话号码的字母组合回溯19.删除链表的倒数第N个节点快慢指针20.有效的括号栈注意栈pop前需要判断是否为空21.合并两个有序链表双指针22.括号生成回溯法用变量记录能生成的右括号数23.合并K个升序链表堆31.下一个排列1. 从后向前 查找第一个 相邻升序 的元素对 (i,j)满足 A[i] A[j]。此时 [j,end) 必然是降序 2.在 [j,end) 从后向前 查找第一个满足 A[i] A[k] 的 k 3.将 A[i] 与 A[k] 交换 4.可以断定这时 [j,end) 必然是降序逆置 [j,end)使其升序 5. 如果在步骤 1 找不到符合的相邻元素对说明当前 [begin,end) 为一个降序顺序则直接跳到步骤 432.最长有效括号33.搜索旋转排序数组二分查找有序的那一半的范围是可以确定的34.在排序数组中查找元素的第一个和最后一个位置二分查找39.组合总和递归能递归不要迭代42.接雨水每一格能接的水是左右两边最大值的较小值减这格的水46.全排列回溯48.旋转图像先对角线再轴对称49.字母异位词分组将字母排序后作为哈希值53.最大子数组和动态规划dp[i]为以第i个数为结尾的最大子数组和55.跳跃游戏贪心不断延伸能跳的范围看能否超过最大长度56.合并区间贪心按左边界从小到大排序不断延伸右边界62.不同路径动态规划64.最小路径和动态规划70.爬楼梯动态规划72.编辑距离dp[i][j] min(dp[i][j-1], dp[i][j],dp[i-1][j])1 (s[i] ! p[j]) dp[i][j] dp[i-1][j-1] (s[i] p[j])75.颜色分类快慢指针慢指针必须从-1开始无论相不相等都交换76.最小覆盖子串滑动窗口用一个哈希表来记录字母的次数78.子集回溯79.单词搜索回溯84.柱状图中的最大矩形85.最大矩形94.二叉树的中序遍历迭代借用栈不断压入左子树左子树压入完了再压入右子树96.不同的二叉搜索树动态规划98.验证二叉搜索树递归遍历需带有这棵树的最大最小值用long变量101.对称二叉树递归102.二叉树的层序遍历借助队列遍历每层前获取当前队列的数量确定该层的元素个数104.二叉树的最大深度递归105.从前序与中序遍历构造二叉树通过前序遍历将二叉树一分为二递归构建114.二叉树展开为链表递归121.买卖股票的最佳时机一次遍历用一个变量记录之前的最低值124.二叉树中的最大路径和类似于二叉树直径维护一个变量记录全局最大值node.val leftGain rightGain方法返回当前最大值node.val Math.max(leftGain, rightGain)128.最长连续序列剪枝如果比当前数小1的数存在则跳过136.只出现一次的数字位运算数异或自己等于0139.单词拆分动态规划141.环形链表快慢指针142.环形链表2快慢指针第一次相遇后将慢指针重新指向头节点再次相遇即为交点146.LRU缓存双向链表哈希表。记录头节点、尾节点初始化时需要建虚拟节点先写好插入头部和删除节点方法操作完链表后记得操作哈希表148.排序链表堆。归并排序先用快慢指针找到链表的中点对两边分别排序合并两个有序链表152.乘积最大子数组两个dp数组分别记录以dp[i]结尾的最大最小值根据nums[i]的正负号来确定dp[i]155.最小栈通过辅助栈判断注意判断相等用equals160.相交链表哈希表。快慢指针198.打家劫舍动态规划200.岛屿数量深度优先206.反转链表递归方式head.next.next head207.课程表208.实现Tire树Tire两个成员变量Tire[]和isEnd215.数组中的第K个最大元素堆、快排221.最大正方形dp[i][j] min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1] 1226.翻转二叉树递归234.回文链表先拆再翻转再比较236.二叉树的最近公共祖先如果一个节点是根节点则是该节点如果一个在左子树一个在右子树则为该节点否则递归获取238.除自身以外数组乘积两个前缀积数组239.滑动窗口最大值借助队列元素入队列时从队尾移除小于该数的数240.搜索二维矩阵2从右上角开始每次收缩列或行279.完全平方数动态规划283.移动零快慢指针将非0的数移到前面287.寻找重复数二分查找如果i重复那么小于等于i的数必定大于i297.二叉树的序列化和反序列化必须要添加空节点和分隔符300.最长递增子序列动态规划dp[i]为以i结尾的最长子序列309.买卖股票的最佳时机含冷冻期动态规划dp[i][0 or 1], 0,1表示持有或非持有状态312.戳气球322.零钱兑换完全背包问题337.打家劫舍3动态规划抢或不抢根节点338.比特位计数位运算n(n-1) 动态规划347.前K个高频元素哈希表计数堆394.字符串解码递归399.除法求值并查集406.根据身高重建队列按从小到大或从大到小重建队列416.分割等和子集0-1背包问题不能简化为1维数组会变成完全背包问题437.路径总和3动态规划选择根节点或不选根节点使用long变量防止越界438.找到字符串中所有字母异位词滑动窗口如果异位词的长度比原数组大则直接返回448.找到所有数组中消失的数字数组用作哈希表461.汉明距离位运算 n(n-1)494.目标和0-1背包问题转换为选负号的数的和sumtarget 或 (sum-target)%2 1 直接返回0 边界dp[0][0] 1538.把二叉搜索树转换为累加树树的遍历543.二叉树的直径在计算深度的时候顺便把直径算了直径左子树深度右子树深度1560.和为K的子数组前缀和哈希表优化在计算前缀和的过程中顺便记录路径数581.最短无序连续子数组从左往右遍历找到乱序左边界从右往左遍历找到乱序右边界。注意不需要重排的边界情况617.合并二叉树递归621.任务调度器647.回文子串两边扩展法739.每日温度单调栈二分查找范式intbinary_search(int[]nums,inttarget){intleft0,rightnums.length-1;while(leftright){intmidleft(right-left)/2;if(nums[mid]target){leftmid1;}elseif(nums[mid]target){rightmid-1;}elseif(nums[mid]target){// 直接返回returnmid;}}// 直接返回return-1;}// 寻找左边界收缩右边界返回左边界intleft_bound(int[]nums,inttarget){intleft0,rightnums.length-1;while(leftright){intmidleft(right-left)/2;if(nums[mid]target){leftmid1;}elseif(nums[mid]target){rightmid-1;}elseif(nums[mid]target){// 别返回锁定左侧边界rightmid-1;}}// 判断 target 是否存在于 nums 中if(left0||leftnums.length){return-1;}// 判断一下 nums[left] 是不是 targetreturnnums[left]target?left:-1;}// 寻找右边界收缩左边界返回右边界intright_bound(int[]nums,inttarget){intleft0,rightnums.length-1;while(leftright){intmidleft(right-left)/2;if(nums[mid]target){leftmid1;}elseif(nums[mid]target){rightmid-1;}elseif(nums[mid]target){// 别返回锁定右侧边界leftmid1;}}// 由于 while 的结束条件是 right left - 1且现在在求右边界// 所以用 right 替代 left - 1 更好记if(right0||rightnums.length){return-1;}returnnums[right]target?right:-1;}滑动窗口范式// 索引区间 [left, right) 是窗口intleft0,right0;while(rightnums.size()){// 增大窗口window.addLast(nums[right]);right;while(window needs shrink){// 缩小窗口window.removeFirst(nums[left]);left;}}// 先扩再缩intright-1;for(inti0;is.length();i){if(i0){window.removeFirst(nums[i]);}while(k!0right1s.length()){right;window.addLast(nums[right]);}}DFS范式classSolution{boolean[]vis;publicListListIntegerpermuteUnique(int[]nums){ListListIntegeransnewArrayListListInteger();ListIntegerpermnewArrayListInteger();visnewboolean[nums.length];Arrays.sort(nums);backtrack(nums,ans,0,perm);returnans;}publicvoidbacktrack(int[]nums,ListListIntegerans,intidx,ListIntegerperm){if(idxnums.length){ans.add(newArrayListInteger(perm));return;}for(inti0;inums.length;i){// 剪枝if(vis[i]||(i0nums[i]nums[i-1]!vis[i-1])){continue;}perm.add(nums[i]);vis[i]true;backtrack(nums,ans,idx1,perm);vis[i]false;perm.remove(idx);}}}二叉树范式是否可以通过遍历一遍二叉树得到答案如果可以用一个 traverse 函数配合外部变量来实现。是否可以定义一个递归函数通过子问题子树的答案推导出原问题的答案如果可以写出这个递归函数的定义并充分利用这个函数的返回值。无论使用哪一种思维模式你都要明白二叉树的每一个节点需要做什么需要在什么时候前中后序做。// 二叉树的遍历框架voidtraverse(TreeNoderoot){if(rootnull){return;}// 前序位置traverse(root.left);// 中序位置traverse(root.right);// 后序位置}BFS范式// 输入一棵二叉树的根节点层序遍历这棵二叉树voidlevelTraverse(TreeNoderoot){if(rootnull)return;QueueTreeNodeqnewLinkedList();q.offer(root);intdepth0;// 从上到下遍历二叉树的每一层while(!q.isEmpty()){intszq.size();// 从左到右遍历每一层的每个节点for(inti0;isz;i){TreeNodecurq.poll();// 将下一层节点放入队列if(cur.left!null){q.offer(cur.left);}if(cur.right!null){q.offer(cur.right);}}depth;}}买卖股票范式dp[i][k][0or1]0in-1,1kKn 为天数大K为交易数的上限0和1代表是否持有股票。 basecase dp[-1][...][0]dp[...][0][0]0dp[-1][...][1]dp[...][0][1]-infinity 状态转移方程 dp[i][k][0]max(dp[i-1][k][0],dp[i-1][k][1]prices[i])dp[i][k][1]max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i])快排范式publicclassQuickSort{/** * 快速排序入口 * param arr 待排序数组 */publicstaticvoidsort(int[]arr){if(arrnull||arr.length1){return;}quickSort(arr,0,arr.length-1);}/** * 快速排序递归主体 * param arr 数组 * param low 左边界含 * param high 右边界含 */privatestaticvoidquickSort(int[]arr,intlow,inthigh){if(lowhigh){return;}// 分区返回基准元素的最终位置intpivotIndexpartition(arr,low,high);// 递归排序左半部分quickSort(arr,low,pivotIndex-1);// 递归排序右半部分quickSort(arr,pivotIndex1,high);}/** * Lomuto 分区方案最经典的写法 * 选取最右侧元素为基准(pivot)将小于 pivot 的放左边大于 pivot 的放右边 * * param arr 数组 * param low 左边界 * param high 右边界 * return 基准元素的最终下标 */privatestaticintpartition(int[]arr,intlow,inthigh){intpivotarr[high];// 选择最右侧元素作为基准intilow;// i 指向小于 pivot 区域的右边界for(intjlow;jhigh;j){if(arr[j]pivot){swap(arr,i,j);i;}}// 将 pivot 放到正确的位置swap(arr,i,high);returni;}/** * 交换数组中两个元素 */privatestaticvoidswap(int[]arr,inta,intb){inttemparr[a];arr[a]arr[b];arr[b]temp;}}