面试锦囊之知识整理系列
面试锦囊系列一直有收到大家的反馈,包括后台内推成功的消息、朋友的同事从创业小公司成功跳到huawei等等,非常高兴小破号的这些整理分享能够真正地帮助到大家
好了不废话啦,今天文章的主题就是分享14种解决面试算法编程题的思路(来自educative[1]),经过本人之前笔试面试经验证明确实确实非常非常高频,一定要十分熟悉。对于每一种思路会给出
enjoy!
滑动窗口模式用于对给定数组或链表的特定窗口大小执行所需操作,例如查找包含所有1的最长子序列。滑动窗口从第一个元素开始,每次向右移动一个元素并根据要解决的问题调整窗口的长度。在某些情况下,窗口的大小保持不变,而在其他情况下,大小会增大或缩小。
okay,理解了滑动窗口原理之后,那么什么情况下我们会需要用到它呢?
来看看实际应用滑动窗口解决的问题
双指针的基本思想是使用两个指针串联迭代数据结构,知道一个或两个指针达到某个条件停止。在排序数组或链表中搜索元素对时,两个指针通常很有用, 例如将数组的每个元素与其他元素进行比较时。
通常我们需要两个指针是因为如果只采用单个指针,必须不断循环数组才能找到答案。这种解决方案虽然确实可行,但是对时间和空间复杂度来说明显是低效的
。在许多情况下,使用双指针可以帮助你找到具有更好空间或时间复杂度的解决方案。
也被称为“龟兔算法”,基本思想是使用两个指针以不同的速度在数组或链表中移动。在处理循环链接列表或数组时,此方法非常有用。通过以不同的速度移动(例如,在循环链表中),算法证明两个指针必然会相遇。一旦两个指针都处于循环循环中,快速指针就应该捕获慢速指针。
合并间隔模式是处理重叠间隔的有效技术。在涉及间隔的许多问题中,你可以需要找到重叠间隔或合并间隔(如果它们重叠)。给定两个间隔
和
,可能存在6中不同的间隔交互情况:
该模式基于广度优先搜索(BFS)技术来遍历树,并使用队列在跳到下一层之前记录下该层的所有节点。使用这种方法可以有效地解决涉及以逐级顺序遍历树的任何问题。Tree BFS模式的基本思想是将根节点push到队列然后不断迭代直到队列为空。对于每次迭代,删除队列头部的节点并“访问”该节点。从队列中删除每个节点后,我们还将其所有子节点push进队列。
树DFS基于深度优先搜索(DFS)技术来遍历树。Tree DFS的基本思想是使用递归(或迭代方法的堆栈)在遍历时跟踪所有先前(父)节点。从树的根开始,如果节点不是叶子,则需要做三件事:
大量的编程面试问题涉及处理一组给定元素的排列和组合。Subsets模式描述了一种有效的广度优先搜索(BFS)方法来处理所有这些问题。例如给定一个数组 [1, 5, 3]
[[ ]]
[[], [1]]
[[], [1], [5], [1, 5]]
[[], [1], [5], [1, 5], [3], [1, 3], [5, 3], [1, 5, 3]]
[1]
educative: https://hackernoon.com/14-patterns-to-ace-any-coding-interview-question-c5bb3357f6ed
[2]
滑动窗口的最大值(剑指offer): https://www.nowcoder.com/practice/1624bc35a45c42c0bc17d17fa0cba788?tpId=13&tqId=11217&tPage=4&rp=4&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[3]
滑动窗口中位数(LEETCODE): https://leetcode-cn.com/problems/sliding-window-median/
[4]
最小覆盖子串(LEETCODE): https://leetcode-cn.com/problems/minimum-window-substring/
[5]
K 个不同整数的子数组(LEETCODE): https://leetcode-cn.com/problems/subarrays-with-k-different-integers/
[6]
无重复字符的最长自创(LEETCODE): https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
[7]
接雨水(LEETCODE): https://leetcode-cn.com/problems/trapping-rain-water/
[8]
长度最小的子数组(LEETCODE): https://leetcode-cn.com/problems/minimum-size-subarray-sum/
[9]
环形链表(LEETCODE): https://leetcode-cn.com/problems/linked-list-cycle/
[10]
相交链表(LEETCODE): https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
[11]
环形链表入口节点(LEETCODE): https://leetcode-cn.com/problems/linked-list-cycle-ii/
[12]
合并区间(LEETCODE): https://leetcode-cn.com/problems/merge-intervals/
[13]
会议室(LEETCODE): https://leetcode-cn.com/problems/meeting-rooms-ii/
[14]
Range模块(LEETCODE): https://leetcode-cn.com/problems/range-module/
[15]
区间列表的交集(LEETCODE): https://leetcode-cn.com/problems/interval-list-intersections/
[16]
N叉树的层序遍历(LEETCODE): https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/
[17]
二叉树的层序遍历(LEETCODE): https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
[18]
二叉树的锯齿形层次遍历: https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/
[19]
求根到叶子节点数字之和(LEETCODE): https://leetcode-cn.com/problems/sum-root-to-leaf-numbers/
[20]
二叉树的最大深度(LEETCODE): https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
[21]
从中序与后序遍历序列构造二叉树(LEETCODE): https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
[22]
路径总和系列(LEETCODE): https://leetcode-cn.com/problems/path-sum/
[23]
子集系列(LEETCODE): https://leetcode-cn.com/problems/subsets/
[24]
字母大小写全排列(LEETCODE): https://leetcode-cn.com/problems/letter-case-permutation/
[25]
列举单词的全部缩写(LEETCODE): https://leetcode-cn.com/problems/generalized-abbreviation/
[26]
单词子集(LEETCODE): https://leetcode-cn.com/problems/word-subsets/