鱼人学习小计（五）

算法题：
1）数组与链表区别
数组在内存中是连续存放的，每个元素都有相同的内存空间，可以通过下标迅速的找到数组中的元素，但是如果修改数组元素，则需要移动数组中所有元素，申请新的内存空间，比较麻烦。而链表相反，它在内存中是不连续的，每个元素都包含有指向下一个元素的指针，如果查找元素，则要从链表首元素开始通过指针查找，但是如果要添加和删除链表则比较简单，修改指针就可以。

2）两个长链表求交点（考虑环）
分两种情况，两个无环单链表，则去遍历链表长度，遍历完看结尾地址是否相同，相同则有交点。让长链表先走长度差的步数，再将两个链表同时走，相等时得到交点。
带环交点。判断有环，再求环的起点。判断有环，快慢指针如果相交则有环。此时在交点位置上，将快指针调慢，慢指针回到起点，再次相交则为环的起点。

3）堆排序，以及建堆的过程
堆排序是常用的一种排序算法。它的思路是将一个数组先建成一个大堆，去掉堆顶（堆顶为已知最大或最小）元素后，再讲剩下的元素重新做堆，直至全部排序。
建堆思路，输出堆顶元素后将堆底元素放到堆顶，然后跟子节点比较替换，恢复堆的性质。

4）反转单链表，反转单链表的部分区间
每次将区间的表头的后面那个元素放到区间前一个元素的后面。

5）删除原排序数组内重复次数超过三次的数字（不开辅助空间）

6）百万数据寻找最大的十个数
建堆。
7）连续子数组的最大和
暴力法，遍历数组每个元素，求和对比。
分治法，去中间点将数组分为三种，左数组，右数组，包含中点数组，对三种求和对比，递归分析。
8）快排的理解、时间复杂度，什么情况下时间复杂度最高
快排实现就是在数组中取一个基准值，将数组分为大于基准值和小于基准值部分实现基准值的准确定位，再讲剩余两部分做递归分析。对有序数组快排时间复杂度最高。
9）如何判断一个链表有环，以及入口点在那里
见（2）
10）反转字符串“I LOVE YOU” 为 “YOU LOVE I”
全盘反转，然后部分反转。
11）找第一个不重复的字符
两个遍历，拿每个字符遍历字符数组，取得不重复的。
哈希列表，存元素值与重复次数。
12）哈希的原理，以及处理冲突的方式。
HashMap的底层主要是基于数组和链表来实现的，它之所以有相当快的查询速度主要是因为它是通过计算散列码来决定存储的位置。HashMap中主要是通过key的hashCode来计算hash值的，只要hashCode相同，计算出来的hash值就一样。如果存储的对象对多了，就有可能不同的对象所算出来的hash值是相同的，这就出现了所谓的hash冲突。主要通过链表来解决hash冲突的。当出现冲突的时候，它通过释放原来的数组结构，并进行分配大一个数组结构来存放新的元素的。它的劣势很明显，如果冲突比较多会频繁的alloc和free。类似将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。第二种方法，当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。
哈希表的构造方法：如果事先知道关键字集合，并且每个关键字的位数比哈希表的地址码位数多时，可以从关键字中选出分布较均匀的若干位，构成哈希地址。