技术面试要了解的算法和数据结构知识

目录 在线练习 在线编程面试 数据结构 算法 贪心算法 位运算 复杂度分析 视频教程 面试宝典 计算机科学资讯 文件结构

在线练习 LeetCode Virtual Judge CareerCup HackerRank CodeFights Kattis HackerEarth Codility Code Forces Code Chef Sphere Online Judge – SPOJ

在线编程面试 Gainlo Refdash

数据结构 链表 链表是一种由节点(Node)组成的线性数据集合,每个节点通过指针指向下一个节点。它是一种由节点组成,并能用于表示序列的数据结构。 单链表 :每个节点仅指向下一个节点,最后一个节点指向空(null)。 双链表 :每个节点有两个指针p,n。p指向前一个节点,n指向下一个节点;最后一个节点指向空。 循环链表 :每个节点指向下一个节点,最后一个节点指向第一个节点。 时间复杂度:索引:O(n) 查找:O(n) 插入:O(1) 删除:O(1)

栈 栈是一个元素集合,支持两个基本操作:push用于将元素压入栈,pop用于删除栈顶元素。 后进先出的数据结构(Last In First Out, LIFO) 时间复杂度索引:O(n) 查找:O(n) 插入:O(1) 删除:O(1)

队列 队列是一个元素集合,支持两种基本操作:enqueue 用于添加一个元素到队列,dequeue 用于删除队列中的一个元素。 先进先出的数据结构(First In First Out, FIFO)。 时间复杂度索引:O(n) 查找:O(n) 插入:O(1) 删除:O(1)

树 树是无向、联通的无环图。

二叉树 二叉树是一个树形数据结构,每个节点最多可以有两个子节点,称为左子节点和右子节点。 满二叉树(Full Tree) :二叉树中的每个节点有 0 或者 2 个子节点。

大数据

完美二叉树(Perfect Binary) :二叉树中的每个节点有两个子节点,并且所有的叶子节点的深度是一样的。 完全二叉树 :二叉树中除最后一层外其他各层的节点数均达到最大值,最后一层的节点都连续集中在最左边。

二叉查找树 二叉查找树(BST)是一种二叉树。其任何节点的值都大于等于左子树中的值,小于等于右子树中的值。 时间复杂度索引:O(log(n)) 查找:O(log(n)) 插入:O(log(n)) 删除:O(log(n))

大数据

字典树 字典树,又称为基数树或前缀树,是一种用于存储键值为字符串的动态集合或关联数组的查找树。树中的节点并不直接存储关联键值,而是该节点在树中的位置决定了其关联键值。一个节点的所有子节点都有相同的前缀,根节点则是空字符串。

大数据

树状数组 树状数组,又称为二进制索引树(Binary Indexed Tree,BIT),其概念上是树,但以数组实现。数组中的下标代表树中的节点,每个节点的父节点或子节点的下标可以通过位运算获得。数组中的每个元素都包含了预计算的区间值之和,在整个树更新的过程中,这些计算的值也同样会被更新。 时间复杂度区间求和:O(log(n)) 更新:O(log(n))

大数据

线段树 线段树是用于存储区间和线段的树形数据结构。它允许查找一个节点在若干条线段中出现的次数。 时间复杂度区间查找:O(log(n)) 更新:O(log(n))

大数据

堆 堆是一种基于树的满足某些特性的数据结构:整个堆中的所有父子节点的键值都满足相同的排序条件。堆分为最大堆和最小堆。在最大堆中,父节点的键值永远大于等于所有子节点的键值,根节点的键值是最大的。最小堆中,父节点的键值永远小于等于所有子节点的键值,根节点的键值是最小的。 时间复杂度索引:O(log(n)) 查找:O(log(n)) 插入:O(log(n)) 删除:O(log(n)) 删除最大值/最小值:O(1)

大数据

哈希 哈希用于将任意长度的数据映射到固定长度的数据。哈希函数的返回值被称为哈希值、哈希码或者哈希。如果不同的主键得到相同的哈希值,则发生了冲突。 Hash Maphash map 是一个存储键值间关系的数据结构。HashMap 通过哈希函数将键转化为桶或者槽中的下标,从而便于指定值的查找。 冲突解决链地址法( Separate Chaining :在链地址法中,每个桶(bucket)是相互独立的,每一个索引对应一个元素列表。处理HashMap 的时间就是查找桶的时间(常量)与遍历列表元素的时间之和。 开放地址法( Open Addressing :在开放地址方法中,当插入新值时,会判断该值对应的哈希桶是否存在,如果存在则根据某种算法依次选择下一个可能的位置,直到找到一个未被占用的地址。开放地址即某个元素的位置并不永远由其哈希值决定。

大数据

图 图是G =(V,E)的有序对,其包括顶点或节点的集合 V 以及边或弧的集合E,其中E包括了两个来自V的元素(即边与两个顶点相关联 ,并且该关联为这两个顶点的无序对)。 无向图 :图的邻接矩阵是对称的,因此如果存在节点 u 到节点 v 的边,那节点 v 到节点 u 的边也一定存在。 有向图 :图的邻接矩阵不是对称的。因此如果存在节点 u 到节点 v 的边并不意味着一定存在节点 v 到节点 u 的边。

大数据

算法 排序 快速排序 稳定:否 时间复杂度最优:O(nlog(n)) 最差:O(n^2) 平均:O(nlog(n))

大数据

合并排序 合并排序是一种分治算法。这个算法不断地将一个数组分为两部分,分别对左子数组和右子数组排序,然后将两个数组合并为新的有序数组。 稳定:是 时间复杂度:最优:O(nlog(n)) 最差:O(nlog(n)) 平均:O(nlog(n))

桶排序 桶排序是一种将元素分到一定数量的桶中的排序算法。每个桶内部采用其他算法排序,或递归调用桶排序。 时间复杂度最优:Ω(n + k) 最差: O(n^2) 平均:Θ(n + k)

大数据

基数排序 基数排序类似于桶排序,将元素分发到一定数目的桶中。不同的是,基数排序在分割元素之后没有让每个桶单独进行排序,而是直接做了合并操作。 时间复杂度最优:Ω(nk) 最差: O(nk) 平均:Θ(nk)

图算法 深度优先 搜索 深度优先搜索是一种先遍历子节点而不回溯的图遍历算法。 时间复杂度:O(|V| + |E|)

大数据

广度优先 搜索 广度优先搜索是一种先遍历邻居节点而不是子节点的图遍历算法。 时间复杂度:O(|V| + |E|)

大数据

拓扑排序 拓扑排序是有向图节点的线性排序。对于任何一条节点 u 到节点 v 的边,u 的下标先于 v。 时间复杂度:O(|V| + |E|)

Dijkstra算法 Dijkstra 算法是一种在有向图中查找单源最短路径的算法。 时间复杂度:O(|V|^2)

大数据

Bellman-Ford算法 *Bellman-Ford * 是一种在带权图中查找单一源点到其他节点最短路径的算法。 虽然时间复杂度大于 Dijkstra 算法,但它可以处理包含了负值边的图。 时间复杂度:最优:O(|E|) 最差:O(|V||E|)

大数据

Floyd-Warshall 算法 *Floyd-Warshall * 算法是一种在无环带权图中寻找任意节点间最短路径的算法。 该算法执行一次即可找到所有节点间的最短路径(路径权重和)。 时间复杂度:最优:O(|V|^3) 最差:O(|V|^3) 平均:O(|V|^3)

最小生成树算法 最小生成树算法是一种在无向带权图中查找最小生成树的贪心算法。换言之,最小生成树算法能在一个图中找到连接所有节点的边的最小子集。 时间复杂度:O(|V|^2)

Kruskal 算法 *Kruskal * 算法也是一个计算最小生成树的贪心算法,但在 Kruskal 算法中,图不一定是连通的。 时间复杂度:O(|E|log|V|)

贪心算法 贪心算法总是做出在当前看来最优的选择,并希望最后整体也是最优的。 使用贪心算法可以解决的问题必须具有如下两种特性:最优子结构问题的最优解包含其子问题的最优解。

贪心选择每一步的贪心选择可以得到问题的整体最优解。

实例-硬币选择问题 给定期望的硬币总和为 V 分,以及 n 种硬币,即类型是 i 的硬币共有 coinValue[i] 分,i的范围是 [0…n – 1]。假设每种类型的硬币都有无限个,求解为使和为 V 分最少需要多少硬币? 硬币:便士(1美分),镍(5美分),一角(10美分),四分之一(25美分)。 假设总和 V 为41,。我们可以使用贪心算法查找小于或者等于 V 的面值最大的硬币,然后从 V 中减掉该硬币的值,如此重复进行。V = 41 | 使用了0个硬币 V = 16 | 使用了1个硬币(41 – 25 = 16) V = 6 | 使用了2个硬币(16 – 10 = 6) V = 1 | 使用了3个硬币(6 – 5 = 1) V = 0 | 使用了4个硬币(1 – 1 = 0)

运算 位运算即在比特级别进行操作的技术。使用位运算技术可以带来更快的运行速度与更小的内存使用。 测试第 k 位:s & (1 << k); 设置第k位:s |= (1 << k); 关闭第k位:s &= ~(1 << k); 切换第k位:s ^= (1 << k); 乘以2n:s << n; 除以2n:s >> n; 交集:s & t; 并集:s | t; 减法:s & ~t; 提取最小非0位:s & (-s); 提取最小0位:~s & (s + 1); 交换值:x ^= y; y ^= x; x ^= y;

运行时分析 大 O 表示 大 O 表示用于表示某个算法的上界,用于描述最坏的情况。

大数据

小 O 表示 小 O 表示用于描述某个算法的渐进上界,二者逐渐趋近。

大 Ω 表示 大 Ω 表示用于描述某个算法的渐进下界。

大数据

小 ω 表示 小 ω 表示用于描述某个算法的渐进下界,二者逐渐趋近。

Theta Θ 表示 Theta Θ 表示用于描述某个算法的确界,包括最小上界和最大下界。

大数据

视频教程 数据结构UC Berkeley Data Structures MIT Advanced Data Structures

算法MIT Introduction to Algorithms MIT Advanced Algorithms

面试宝典 Competitive Programming 3 – Steven Halim & Felix Halim Cracking The Coding Interview – Gayle Laakmann McDowell Cracking The PM Interview – Gayle Laakmann McDowell & Jackie Bavaro Introduction to Algorithms – Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest & Clifford Stein

End.

http://www.36dsj.com/archives/80717

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏chenjx85的技术专栏

leetcode-78-子集(用bfs解决)

vector<vector<int>> subsets(vector<int>& nums)

4791
来自专栏SeanCheney的专栏

《Pandas Cookbook》第05章 布尔索引1. 计算布尔值统计信息2. 构建多个布尔条件3. 用布尔索引过滤4. 用标签索引代替布尔索引5. 用唯一和有序索引选取6. 观察股价7. 翻译SQ

第01章 Pandas基础 第02章 DataFrame运算 第03章 数据分析入门 第04章 选取数据子集 第05章 布尔索引 第06章 索引对齐 ...

2052
来自专栏算法修养

树形DP总结,持续更新

自己做了动态规划的题目已经有了一个月,但是成效甚微,所以来总结一下动态规划,希望自己能够温故知新。这个博客是关于树形dp的,动态规划的一类题目。 ...

7296
来自专栏TensorFlow从0到N

讨厌算法的程序员 5 - 合并算法

本篇介绍的“合并”算法,是为后面学习“归并排序”的一个准备。合并算法是归并排序中的一个子算法,请注意两者之间的关系和差异。 之所以把它独立成一篇,一方面是一旦...

3515
来自专栏null的专栏

每周算法练习——最近对问题

一、最近对问题的解释     看到算法书上有最近对的问题,简单来讲最近对问题要求出一个包含 ? 个点的集合中距离最近的两个点。抽象出来就是求解任意两个点之间的距...

4396
来自专栏前端杂谈

前端算法-基本排序算法比较

37913
来自专栏灯塔大数据

每周学点大数据 | No.22 外排序

No.22期 外排序(一) Mr. 王:接下来我们看一看在磁盘算法中一个比较典型的例子——外排序。 小可:那什么又是外排序呢? Mr. 王:外排序是相...

3746
来自专栏数据结构与算法

1200 同余方程

1200 同余方程 2012年NOIP全国联赛提高组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond 题目...

2874
来自专栏糊一笑

关于一道面试题【字符串 '1 + (5 - 2) * 3',怎么算出结果为10,'eval'除外】

最近徘徊在找工作和继续留任的纠结之中,在朋友的怂恿下去参加了一次面试,最后一道题目是: 写一个函数,输入一个字符串的运算式,返回计算之后的结果。例如这样的: ...

57010
来自专栏CDA数据分析师

学会这8个(组)excel函数,轻松解决工作中80%的难题

文 | 兰色幻想-赵志东 函数是excel中最重要的分析工具,面对400多个excel函数新手应该从哪里入手呢?下面是实际工作中最常用的8个(组)函数,学会后工...

2017

扫码关注云+社区

领取腾讯云代金券