Wenqian Blog

从现在开始就不算晚

「算法总结系列」：双指针

Two Pointers

什么是两个指针 两个指针指的是在解题过程中我们会先声明两个指针left和right，分别指向目标（通常是数组）的两点（通常是同一点或者数组的两端），指针如何移动，哪个指针应该移动通常是由两个指针指向的点所决定的。不断移动两个指针直到某个条件不满足为止（比如left > right或者right >= length等等）。 什么情况下会用到两个指针 两个指针一般分为以下几种情...

Posted by Wenqian on November 22, 2019

「算法总结系列」：Trie树

Trie Tree

什么是Trie树 Trie树又叫前缀树或字典树，是一种有序树，它的键值通常是字符串。其实前面所说的“前缀树”和“字典树”已经非常形象地将Trie树的特点阐述了出来。 为什么叫它“前缀树”？这是因为Trie树中某个节点的所有子孙都拥有相同的前缀，也就是说通过Trie数我们可以很方便地知道这些词中存在哪些前缀。 为什么叫它“字典树”？这是因为通常我们会将一组词建立一个Trie树，而Trie树查...

Posted by Wenqian on November 22, 2019

「算法总结系列」：扫描线

Sweep Line

什么是扫描线算法 这里所说的扫描线算法其实是一种简化，特指用一根与x轴相垂直的直线扫过整个平面时，根据其与平面上其他线的交点计算最终我们需要的结果。 什么时候会用到扫描线算法 扫描线算法一般用在区间问题上。比如最经典的Number of Airplanes in the Sky，题目给你几个区间分别表示不同航班的起飞和降落时间，问你天上最多同时有几架飞机。那么我们以时间为x轴，飞机数量...

Posted by Wenqian on November 22, 2019

「算法总结系列」：栈

Stack

什么是栈 栈是一种后进先出（LIFO）的数据结构。它通常具备以下几种操作：（1）pop：提出栈顶元素。（2）push：将一个元素压进栈中。（3）peek：返回栈顶元素。（4）empty：判断栈是否为空。 什么时候会用到栈 一般来说有以下几种情况： （1）明确的考察你是否真的理解栈这种数据结构，比如让你用栈来实现一些特殊功能，或者用栈来实现其他数据结构。例如：Min Stack和Impl...

Posted by Wenqian on November 22, 2019

「算法总结系列」：堆

Heap

什么是堆 这里说的堆是一种数据结构，通常是由一个被看做树的数组构成。堆分为最大堆（Max-Heap）和最小堆（Min-Heap），他们的不同点在于最大堆的根节点为所有元素的最大值，同时它的左右子树也都是最大堆，而最小堆则恰恰相反，其根节点为所有元素的最小值，而左右子树也都是最小堆。下图是一个最大堆的例子。 什么情况下会用到堆 我个人感觉以下几种情况通常会用到堆： （1）题目直接让你...

Posted by Wenqian on November 22, 2019

「算法总结系列」：动态规划

Dynamic Programming

什么是动态规划 动态规划往往应用于最优化问题，即做出一组选择从而得到一个最优解（可以同时存在多个最优解）。一组选择作为一个整体可以被分化成一个个子问题，而这些子问题中往往存在重复，我们要做的就是保存不同的子问题结果从而在遇到重复问题时可以节省时间。最终由一个个子问题的结果自下而上得出最后的最优解。 动态规划的类型 （1） 序列型动态规划。构造一个一维或二维数组来顺序的存放中间结果。这类题...

Posted by Wenqian on November 22, 2019

「算法总结系列」：深度优先算法

Depth First Search

什么是深度优先算法 深度优先算法同BFS类似，也是一种用来遍历或搜索树或图的方法。与BFS不同的是，它更注重于“深度”，即尽可能深的搜索树的分支，只有当某个分支被完全搜索完后，他才会返回上一个节点并搜索下一个分支，直到所有分支都被搜索完后才结束。 什么时候会用到深度优先算法 （1）对树的深度很感兴趣时，可以用dfs。例如Maximum Depth of Binary Tree。 （2）...

Posted by Wenqian on November 22, 2019

「算法总结系列」：广度优先算法

Breath First Search

什么是广度优先算法 广度优先算法即BFS（Breath-First-Search），是一种图形搜索算法。它一般从一个根节点出发（有时是任意的一个节点），向外一层一层（同一层的节点到根节点的距离相同）的搜索，直到所有节点都被遍历为止。 什么时候会用到广度优先算法 之前也提到了，BFS是一种图形搜索算法，所以用到的BFS的题目一般也都与图相关。这个图可以是一个二维数组（每个点表示一个节点，...

Posted by Wenqian on November 22, 2019

「算法总结系列」：二分搜索法

Binary Search

什么是二分法搜索 通过二分方法对一个排序过的数组进行搜索，判断某个数是否在数组内。所谓的二分方法及不断将一段数中的中间值与目标值进行比较，如果目标值较大，就将搜索区域缩小为中间值的右侧，如果目标值较小，则将搜索区域缩小为中间值的右侧。如此反复进行，直到找到目标值或者搜索区域缩小为0。 什么时候会用到二分法搜索 使用二分法搜索有一个前提，那就是数组一定要是排序好的。因此一般用到二分法的题...

Posted by Wenqian on November 22, 2019

FEATURED TAGS
算法 机器学习 深度学习 广告算法 推荐算法 实时竞价 联邦学习 学习笔记 经典算法 经典网络 NLP
ABOUT ME

Love csy

FRIENDS