淘宝请人做网站被骗,东莞网站的优化,服务提供网站,服装logo创意设计转载自 LeetCode常用算法模式大厂面试题整理
文章目录
1、滑动窗口 2、双指针 3、快慢指针 4、合并区间 5、循环排序 6、就地反转链表 7、堆-优先队列问题 8、Top K 9、归并 10、单调栈 11、回溯法 BATJ等大厂面试真题汇总 1、滑动窗口 1 一个左指针#xff0c;一个右…转载自 LeetCode常用算法模式大厂面试题整理
文章目录
1、滑动窗口 2、双指针 3、快慢指针 4、合并区间 5、循环排序 6、就地反转链表 7、堆-优先队列问题 8、Top K 9、归并 10、单调栈 11、回溯法 BATJ等大厂面试真题汇总 1、滑动窗口 1 一个左指针一个右指针。其中左指针用于缩小范围右指针用于扩大搜索范围。一般求滑动窗口的最小值都是在缩小左指针的时候取得的。 2 右指针扩展的条件时只要当前还没有满足条件就暴力增长直到第一次满足条件为止。 3 左指针收缩的条件只要当前指针的缩小还没影响窗口的可满足性就一直暴力向左增长。一但当前指针向前移动的时候影响了窗口的可满足性就记录下当前的窗口大小并更新目前为止满足条件的最小窗口记录。之后再次扩展右指针使得窗口满足题目的条件。 这也是自己比较熟练的一个算法以前用这个算法对华为的一道机考题进行了优化将时间复杂度由传统方法的Om*n降低到了On。博客链接
参考例题 生成窗口最大值数组 牛客网链接答案 最大值减去最小值小于或等于num的子数组数量 牛客网链接答案最短包含子串长度/最小覆盖子串待完善 2、双指针 双指针的基本思想是使用两个指针串联迭代数据结构知道一个或两个指针达到某个条件停止。在排序数组或链表中搜索元素对时两个指针通常很有用 例如将数组的每个元素与其他元素进行比较时。 双指针问题又可以分为指针在两端向中间行驶和指针在一侧向另一侧行驶问题
参考例题4-sum 3sum-closest 3-sum最长无重复子串长度最小的子数组蓄水池问题 3、快慢指针 也被称为“龟兔算法”基本思想是使用两个指针以不同的速度在数组或链表中移动。在处理循环链接列表或数组时此方法非常有用。通过以不同的速度移动例如在循环链表中算法证明两个指针必然会相遇。一旦两个指针都处于循环循环中快速指针就应该捕获慢速指针。 应用举例这一部分比较简单注意边界条件即可 链表或数组循环 用于找中间元素 需要知道某个元素的位置或链表的总长度 4、合并区间 合并间隔模式是处理重叠间隔的有效技术。在涉及间隔的许多问题中你可以需要找到重叠间隔或合并间隔如果它们重叠。给定两个间隔 a和 b可能存在6中不同的间隔交互情况
应用举例区间重叠问题区间列表的交集无重复区间问题借助HashMap的问题添加链接描述 5、循环排序 循环排序模式描述了一种处理涉及包含给定范围内的数字的数组问题的有趣方法。其一次遍历数组一个数字如果正在迭代的当前数字不是正确的索引则将其与正确索引处的数字交换。
应用举例第一个缺失的正整数有正有负循环排序代码比直接排序代码简单缺失数字有很多种解题方案循环排序方法的复杂度最优寻找重复数据其实笔试的过程中可以用空间换时间和代码复杂度 6、就地反转链表 在许多问题中可能会要求我们反转链表的一组节点之间的链接。通常约束就是需要就地执行此操作即使用现有节点对象而不使用额外内存。这是上述模式有用的地方。此模式一次反转一个节点从一个指向链表头部的变量当前开始一个变量上一个将指向已处理的上一个节点。以锁步方式将通过将当前节点指向前一个节点然后再转到下一个节点来反转当前节点。此外更新变量“previous”以始终指向您已处理的上一个节点。
应用例题添加链接描述添加链接描述 7、堆-优先队列问题 在许多问题中给出了一系列元素需要我们将其分成两部分。为了解决这个问题我们想要知道一个部分中的最小元素和另一个部分中的最大元素。这种模式是解决此类问题的有效方法。这种模式使用两个堆找到最小元素的Min Heap和找到最大元素的Max Heap。该模式的工作原理是将前半部分的数字存储在Max Heap中这是因为我们希望在上半部分找到最大的数字。然后将数字的后半部分存储在Min Heap中因为我们希望在后半部分找到最小的数字。在任何时候可以从两个堆的顶部元素计算当前数字列表的中值。
应用例题窗口的中位数–利用优先队列leetcode253. 会议室II(java)最小堆非常常见的一道题 高频高频数据流的中位数分金条的最小花费做项目的最大收益 8、Top K 其实这个问题可以归为顶堆问题由于更高频所以单独讨论任何要求我们在给定集合中找到最大/最小/频繁“K”元素的问题都属于这种模式。 跟踪’K’元素的最佳数据结构是Heap。这种模式将利用Heap来解决从一组给定元素一次处理’K’元素的多个问题。大致思路是这样的 根据问题将’K’元素插入到最小堆或最大堆中 迭代剩余的数字如果找到一个比堆中的数字大的数字则删除该数字并插入较大的数字。 Top-K 数字频率问题代码
class Solution {public int[] topKFrequent(int[] nums, int k) {HashMapInteger, Integer map new HashMap();PriorityQueueMap.EntryInteger, Integer maxheap new PriorityQueue((a,b) - b.getValue() - a.getValue());int[] result new int[k];for(int i 0; i nums.length; i){map.put(nums[i], map.getOrDefault(nums[i], 0) 1);}for(Map.EntryInteger, Integer m : map.entrySet()){maxheap.offer(m);}for(int i 0; i k; i){result[i] maxheap.poll().getKey();}return result;}
}词频Top-K问题代码注意一下比较器的定义
class Solution {public ListString topKFrequent(String[] words, int k) {MapString, Integer count new HashMap();for (String word: words) {count.put(word, count.getOrDefault(word, 0) 1);}PriorityQueueString heap new PriorityQueueString((w1, w2) - count.get(w1).equals(count.get(w2)) ?w2.compareTo(w1) : count.get(w1) - count.get(w2) );for (String word: count.keySet()) {heap.offer(word);if (heap.size() k) heap.poll();}ListString ans new ArrayList();while (!heap.isEmpty()) ans.add(heap.poll());Collections.reverse(ans);return ans;}
}
应用例题前K个高频元素前K个高频单词 9、归并 K-way Merge可以用于解决涉及一组排序数组的问题。给出’K’排序数组可以使用Heap有效地执行所有数组的所有元素的排序遍历。我们可以在Min Heap中push每个数组的最小元素以获得最小值。获得总体最小值后将下一个元素从同一个数组推送到堆中。然后重复此过程以对所有元素进行排序遍历。
应用例题合并K个排序链表计算小和 10、单调栈
参考文献 从名字上就听的出来单调栈中存放的数据应该是有序的所以单调栈也分为单调递增栈和单调递减栈 单调递增栈栈中数据出栈的序列为单调递增序列 单调递减栈栈中数据出栈的序列为单调递减序列
stackint st;
//此处一般需要给数组最后添加结束标志符具体下面例题会有详细讲解
for (遍历这个数组)
{if (栈空 || 栈顶元素大于等于当前比较元素){入栈;}else{while (栈不为空 栈顶元素小于当前元素){栈顶元素出栈;更新结果;}当前数据入栈;}
}
应用例题 视野总和柱状图中最大矩形解答柱状图中最大矩形左程云书籍单调栈问题链接—其实把这个搞懂其他的都是这个题的变形
文章参考自 educative 参考文献链接 11、回溯法
在另外一篇博客中
LeetCode算法总结-回溯法与深度优先搜索 、BATJ等大厂面试真题汇总
1.栈排序 单调栈问题上文有说明2.链表实现队列 https://blog.csdn.net/qq_21808961/article/details/762392253.最长连续递增序列(leetcode-674) https://leetcode-cn.com/problems/longest-continuous-increasing-subsequence/4.二维数组的打印问题回行打印 环形打印 之字打印5.根据数组建立二叉排序树平衡和非平衡两种 https://blog.csdn.net/Danielntz/article/details/534188436.一个数组实现两个栈共享栈问题7.二叉树宽度与深度 深度求解就是一个递归的过程求宽度就采用按层遍历即可。宽度优先遍历也可求出深度。8.二叉树是否对称二叉树的一系列递归问题都应该掌握9.链表m到n反转和每k个一组进行旋转 https://www.nowcoder.com/practice/b49c3dc907814e9bbfa8437c251b028e?tpId46tqId29154rp1ru/ta/leetcodeqru/ta/leetcode/question-ranking10.贪心算法N位数删除K个数字使剩下的数字串最小11.N皇后问题12.找出来数组中每个元素后边第一个比它大的值单调栈问题13.给你一个二叉树从上往下看然后左往右顺序输出你能看到节点同一个竖直方向上上面的节点把下面的节点遮挡住了14.链表反转分别用遍历与递归实现突然发现递归还挺有意思 https://www.jianshu.com/p/b2542324898e15.完全二叉树的最大深度与节点个数左程云书上原题 https://blog.csdn.net/qq_14842117/article/details/9986487516.两个栈实现队列/两个队列实现栈17.有序数组的交集和并集 https://blog.csdn.net/iteye_12801/article/details/8228072618.删除链表中的重复值节点包括保留问题和不保留问题 https://www.nowcoder.com/practice/c087914fae584da886a0091e877f2c79?tpId46tqId29096rp1ru/ta/leetcodeqru/ta/leetcode/question-ranking https://www.nowcoder.com/practice/71cef9f8b5564579bf7ed93fbe0b2024?tpId46tagstitlediffculty0judgeStatus0rp1ru/ta/leetcodeqru/ta/leetcode/question-ranking19.LeetCode 200. Number of Islands 岛屿的数量20.二叉搜索树转有序双向链表剑指offer原题21.回溯法-字符串全排列 可能有重复的要去重22.二叉搜索树第k个节点不用中序遍历23.有序数组查找重复元素个数24.数组实现队列大话数据结构中的实现非常好 https://www.iteye.com/blog/jim8757-206005025.用二分法求开方 https://blog.csdn.net/u011489043/article/details/7012604126.判断一颗树是不是二叉搜索树27.链表第k-1个节点28.手撕快排不要低估基础算法29.二分法的一系列问题不要低估基础算法30.数组中乘积最大的三个数 高端食材往往采用最简单的烹饪方法算法也是。。。 https://blog.csdn.net/tjumiao/article/details/81189269?utm_mediumdistribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-4.nonecasedepth_1-utm_sourcedistribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-4.nonecase31.求二叉树的深度不使用递归二叉树的问题挺高频 32.实现链表无序链表对链表值奇偶分离并排序空间复杂度O(1)33.单调不递减数组给一个target找出大于等于target的下标index34.单调不递减链表删除掉重复值 35.无序数组构建一棵二叉排序树 36.行和列都是有序的二维矩阵找一个target值37.是否是回文链表38.打印出根节点到叶子节点的最长路径39.不严格递增数组要求删除出现次数大于k的数字要求不要新建存储空间40.链表相邻元素交换跟每k个进行旋转的是同一个问题41.二叉树的最小公共祖先42.输出根节点到叶子节点路径之和为target的路径列表剑指offer原题 https://www.nowcoder.com/practice/b736e784e3e34731af99065031301bca?tpId13tqId11177rp1ru/ta/coding-interviewsqru/ta/coding-interviews/question-ranking43.【LeetCode】1038. 从二叉搜索树到更大和树 一道反向中序遍历的问题 https://blog.csdn.net/rabbitsockx/article/details/10435085844.任意一个整型数组判断是否可以将数组分为三个区间每个区间中数值的和相同(荷兰国旗问题)45.一个已经排序的数组去除里面重复的元素 leetcode中有个类似的问题去重的时候元素可以有两个数是重复的如果有三个以上的重复元素那么就留下两个比如3333 去重后为33 https://blog.csdn.net/feeltouch/article/details/4507758946.错位的全排列第一位不能是1第二位不能是247.k路链表合并 https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6?tpId46tqId29156rp1ru/ta/leetcodeqru/ta/leetcode/question-ranking48.二叉树的左视图 右视图问题都可以根据二叉树的按层遍历解决49.输入一个数字n构建一个完全二叉树并输出50.已知电影开始与结束时间看最多场电影
类似于这道题 https://leetcode-cn.com/problems/non-overlapping-intervals/submissions/1004. 最大连续1的个数 IIIleetcode 打家劫舍相关问题并查集实现相关
