盒子
盒子
文章目录
  1. 重要参考链接https://juejin.im/post/58ca051f61ff4b0060165122
  2. 堆与栈(http://blog.csdn.net/hairetz/article/details/4141043/)
  3. hashmap的基础数据结构
  4. 循环队列
    1. 循环队列的优点:
    2. 循环队列的缺点:
  5. 栈结构与队列的区别?
  6. 二叉树的深度优先遍历(递归与非递归(非递归后序最难))
  7. 写出一次快排后的具体变化情况
  8. 什么是红黑树。
  9. 红黑树的插入和删除
  10. 写一个快排。
  11. 一个单链表怎么判断有没有环?环的起点怎么找? 如何找出环的连接点在哪里?带环链表的长度是多少?
  12. 哈希表解决冲突的方法
  13. 散列表查找的复杂度
  14. 动态规划,最长公共子串等 最长递增子序列(nlogn的算法)
  15. 排序:快排、归并、堆,时间复杂度是一样的,有什么区别?为什么平均情况下快排最快?
  16. 给定一棵树,除左右节点外,还有一个random域,不一定指向哪,可能是空节点,可能是树中的其他节点,做树拷贝。
  17. 大整数加、减、乘、除、求模运算实现
  18. 二叉查找
  19. 二叉搜索树
  20. Top(k)
  21. 单链表翻转(两个指针如何实现)、查找、删除、插入以及双向链表、有序链表合并
  22. 判断一个整数是否是2的整数次幂.
  23. 数组中只有一个数出现了两次,求这个数,并使得空间效率最优(用位图bitmap,比O(n)的线性空间更优)
  24. 二分查找(注意边界条件)
  25. 常见排序算法的实现以及稳定性(快排跟归并考的很多)
  26. 字符串翻转(O(n))、匹配(KMP算法)
  27. 指定一个数组,求2个数的和等于指定的和(某一个数),如果是3,4,5,n个等于个的和(某一个数)呢?(可以看作背包问题)
  28. 跳台阶问题
  29. 一堆数据怎么找中位数(分两种,内存是不是能一次装下所用数据,能的话用快排,不能用分桶)
  30. 找出一个字符串中只出现一次且是第一个的字符
  31. 在不使用额外空间的情况下,交换两个数?

面试内容整理—数据结构

重要参考链接https://juejin.im/post/58ca051f61ff4b0060165122

堆与栈(http://blog.csdn.net/hairetz/article/details/4141043/)

栈区(stack)由编译器自动分配释放,存放方法(函数)的参数值,局部变量的值等。
堆区(heap)一般由程序员分配与释放,若程序员不释放,则会内存溢出。
栈:只要栈的剩余空间大于所申请空间,系统将为程序提供内存,否则将报异常提示栈溢出。
堆:首先应该知道操作系统有一个记录空闲内存地址的链表,当系统收到程序的申请时,会遍历该链表,寻找第一个空间大于所申请空间的堆结点,然后将该结点从空闲结点链表中删除,并将该结点的空间分配给程序,另外,对于大多数系统,会在这块内存空间中的首地址处记录本次分配的大小,这样,代码中的delete语句才能正确的释放本内存空间。
另外,由于找到的堆结点的大小不一定正好等于申请的大小,系统会自动的将多余的那部分重新放入空闲链表中。
栈:在Windows下,栈是向低地址扩展的数据结构,是一块连续的内存的区域。这句话的意思是栈顶的地址和栈的最大容量是系统预先规定好的,在WINDOWS下,栈的大小是2M(也有的说是1M,总之是一个编译时就确定的常数),如果申请的空间超过栈的剩余空间时,将提示overflow。因此,能从栈获得的空间较小。
堆:堆是向高地址扩展的数据结构,是不连续的内存区域。这是由于系统是用链表来存储的空闲内存地址的,自然是不连续的,而链表的遍历方向是由低地址向高地址。堆的大小受限于计算机系统中有效的虚拟内存。由此可见,堆获得的空间比较灵活,也比较大。

hashmap的基础数据结构

HashMap基于hashing原理,我们通过put()和get()方法储存和获取对象。当我们将键值对传递给put()方法时,它调用键对象的hashCode()方法来计算hashcode,让后找到bucket位置来储存值对象。当获取对象时,通过键对象的equals()方法找到正确的键值对,然后返回值对象。HashMap使用LinkedList来解决碰撞问题,当发生碰撞了,对象将会储存在LinkedList的下一个节点中。 HashMap在每个LinkedList节点中储存键值对对象。

循环队列

循环队列的优点:

  可以有效的利用资源。用数组实现队列时,如果不移动,随着数据的不断读写,会出现假满队列的情况。即尾数组已满但头数组还是空的;循环队列也是一种数组,只是它在逻辑上把数组的头和尾相连,形成循环队列,当数组尾满的时候,要判断数组头是否为空,不为空继续存放数据。

循环队列的缺点:

  循环队列中,由于入队时尾指针向前追赶头指针;出队时头指针向前追赶尾指针,造成队空和队满时头尾指针均相等。因此,无法通过条件front==rear来判别队列是”空”是”满”。

解决这个问题有两个办法:一是增加一个参数,用来记录数组中当前元素的个数;第二个办法是,少用一个存储空间,也就是数组的最后一个存数空间不用,当(rear+1)%maxsiz=front时,队列满

栈结构与队列的区别?

栈(stack):限定只能在表的一端进行插入和删除操作的线性表。
队列(queue):限定只能在表的一端插入和在另一端进行删除操作的线性表。
1)队列先进先出,栈先进后出。
2)对插入和删除操作的“限定”不同。
3)遍历数据速度不同。队列遍历数据的速度要快得多。

二叉树的深度优先遍历(递归与非递归(非递归后序最难))

写出一次快排后的具体变化情况

什么是红黑树。

红黑树是每个节点都带有颜色属性的二叉查找树,颜色或红色或黑色。在二叉查找树强制一般要求以外,对于任何有效的红黑树我们增加了如下的额外要求:
性质1. 节点是红色或黑色。
性质2. 根节点是黑色。
性质3 每个叶节点(NIL节点,空节点)是黑色的。
性质4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例,这个在高度上的理论上限允许红黑树在最坏情况下都是高效的,而不同于普通的二叉查找树。

红黑树的插入和删除

写一个快排。

Quick Sort是目前已知最快的排序法,平均复杂度为O(NlogN),可是最坏情况下将达O(N^2)。
Quick Sort算法可以叙述如下。假设S代表将被处理的序列:
1、如果S的元素个数为0或1,结束。
2、取S中的任何一个元素,当做枢轴(pivot) v。
3、将S分割为L、R两段,使L内的每一个元素都小于或等于v,R内的每一个元素都大于或等于v。
4、对L、R递归执行Quick Sort。

一个单链表怎么判断有没有环?环的起点怎么找? 如何找出环的连接点在哪里?带环链表的长度是多少?

1、对于问题1,使用追赶的方法,设定两个指针slow、fast,从头指针开始,每次分别前进1步、2步。如存在环,则两者相遇;如不存在环,fast遇到NULL退出。
2、对于问题2,记录下问题1的碰撞点p,slow、fast从该点开始,再次碰撞所走过的操作数就是环的长度s。
3、问题3:有定理:碰撞点p到连接点的距离=头指针到连接点的距离,因此,分别从碰撞点、头指针开始走,相遇的那个点就是连接点。
该定理的证明可参考:http://fayaa.com/tiku/view/7/
4、问题3中已经求出连接点距离头指针的长度,加上问题2中求出的环的长度,二者之和就是带环单链表的长度

哈希表解决冲突的方法

  • 开放定址法(当关键字key的哈希地址p=H(key)出现冲突时,以p为基础,产生另一个哈希地址p1,如果p1仍然冲突,再以p为基础,产生另一个哈希地址p2,…,直到找出一个不冲突的哈希地址pi ,将相应元素存入其中,线性探测再散列,二次探测再散列,伪随机探测再散列)
  • 再哈希法(这种方法是同时构造多个不同的哈希函数)
  • 链地址法(这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表)
  • 建立一个公共溢出区(将哈希表分为基本表和溢出表两部分,凡是和基本表发生冲突的元素,一律填入溢出表)

    散列表查找的复杂度

    O(1)

    动态规划,最长公共子串等 最长递增子序列(nlogn的算法)

    http://blog.csdn.net/joylnwang/article/details/6766317

    排序:快排、归并、堆,时间复杂度是一样的,有什么区别?为什么平均情况下快排最快?

    给定一棵树,除左右节点外,还有一个random域,不一定指向哪,可能是空节点,可能是树中的其他节点,做树拷贝。

    大整数加、减、乘、除、求模运算实现

    二叉查找

    二叉搜索树

    Top(k)

    1.将输入内容(假设用数组存放)进行完全排序,从中选出排在前K的元素即为所求。有了这个思路,我们可以选择相应的排序算法进行处理,目前来看快速排序,堆排序和归并排序都能达到O(nlogn)的时间复杂度。
    2.对输入内容进行部分排序,即只对前K大的元素进行排序(这K个元素即为所求)。此时我们可以选择冒泡排序或选择排序进行处理,即每次冒泡(选择)都能找到所求的一个元素。这类策略的时间复杂度是O(Kn)。
    3.对输入内容不进行排序,显而易见,这种策略将会有更好的性能开销。我们此时可以选择两种策略进行处理:
            a)利用小根堆维护一个大小为K的数组,目前该小根堆中的元素是排名前K的数,其中根是最小的数。此后,每次从原数组中取一个元素与根进行比较,如大于根的元素,则将根元素替换并进行堆调整(下沉),即保证小根堆中的元素仍然是排名前K的数,且根元素仍然最小;否则不予处理,取下一个数组元素继续该过程。该算法的时间复杂度是O(nlogK),一般来说企业中都采用该策略处理top-K问题,因为该算法不需要一次将原数组中的内容全部加载到内存中,而这正是海量数据处理必然会面临的一个关卡。
            b)利用快速排序的分划函数找到分划位置K,则其前面的内容即为所求。该算法是一种非常有效的处理方式,时间复杂度是O(n)。对于能一次加载到内存中的数组,该策略非常优秀。
    

    单链表翻转(两个指针如何实现)、查找、删除、插入以及双向链表、有序链表合并

    判断一个整数是否是2的整数次幂.

    (n&(n-1))

    数组中只有一个数出现了两次,求这个数,并使得空间效率最优(用位图bitmap,比O(n)的线性空间更优)

    位运算
    利用异或的特性,x^y^x=y^x^x=y

    二分查找(注意边界条件)

    二分查找算法的填空(PS:注意陷阱:数会溢出的问题)
    定中间值的时候写错了 mind = low+high/2 ,后面回来一查,说这样子会溢出 low+high 会越界溢出,查阅相关资料 mind = low+(high-low)>>1,这样 才可以,果然,哪里有这么简单的题目…注意陷阱……

    常见排序算法的实现以及稳定性(快排跟归并考的很多)

    字符串翻转(O(n))、匹配(KMP算法)

    指定一个数组,求2个数的和等于指定的和(某一个数),如果是3,4,5,n个等于个的和(某一个数)呢?(可以看作背包问题)

    跳台阶问题

    一堆数据怎么找中位数(分两种,内存是不是能一次装下所用数据,能的话用快排,不能用分桶)

    http://blog.csdn.net/jiyanfeng1/article/details/8088237

    找出一个字符串中只出现一次且是第一个的字符

    建立一个hash表,遍历一遍字符串,记录每个字符出现的次数

    在不使用额外空间的情况下,交换两个数?

    位操作(异或)或者加减

呼呼呼山(http://code4fun.me)
18 Sep 2017 9:04 PM