寻找一数组中前K个最大的数。
- 暴力破解：该解法是大部分能想到的，也是第一想到的方法。假设数据量不大，可以先用快速排序或堆排序，他们的平均时间复杂度为O(N logN),然后取出前K个，时间复杂度为O(K)，总的时间复杂度为O(NlogN)+O(K).
- 利用快排的划分：假设N个数存储在数组S中，从数组中随机找一个元素X，将数组分成两部分Sa和Sb。Sa中的元素大于等于X,Sb中的元素小于X。出现如下两种情况：
(1)若Sa组的个数大于或等于K，则继续在sa分组中找取最大的K个数字。
(2)若Sa组中的数字小于K，其个数为T，则继续在sb中找取K-T个数字。
一直这样递归下去，不断把问题分解成小问题，平均时间复杂度为O(N*logK)。- 利用最小堆：用容量为K的最小堆来存储最大的K个数。最小堆的堆顶元素就是最大K个数中的最小的一个。每次扫描一个数据X，如果X比堆顶元素Y小，则不需要改变原来的堆。如果X比堆顶元素大，那么用X替换堆顶元素Y，在替换之后，X可能破坏了最小堆的结构，需要调整堆来维持堆的性质。调整过程时间复杂度为O(logK)。 全部的时间复杂度为O(NlogK)。这种方法当数据量比较大的时候，比较方便。因为对所有的数据只会遍历一次，第一种方法则会多次遍历数组。 如果所查找的K的数量比较大。可以考虑先求出k‘ ，然后再求出看k’+1 到 2 k‘之间的数据，然后一次求取。
求一个数组中连续子数组的最大和？
动态规划思想：如果用函数f(i)表示以第i个数字结尾的子数组的最大和，那么我们需要求出max(f[0…n])。我们可以给出如下递归公式求f(i)：
(1)f(x) = pData[i]， 当i = 0 || f(i-1) <= 0时；
(2)f(x) = pData[i] + f(i-1)， 当i != 0 && f(i - 1) > 0时；
ps：用一个值保存最大的f(x)；二叉树Z字型遍历?
按层遍历，设置个flag，然后按层遍历，需要的层reverse一下。
按层遍历思想：
（1）设置3个指针current，last和nLast和一个队列，先把root放入队列queue；
（2）循环判断queue是否为空，若不为空则出队一个元素记作current，然后判断current是否有左右孩子，将nLast置为左孩子或右孩子；
（3）如果last==nLast，存入list；
（4）全部存储完毕后，按行号奇偶决定打印顺序；两个数组A和B,怎么求解两个数组中和为S的所有组合（组合中一个元素是A的，一个元素是B的）
（1）先排序，然后头尾指针遍历；时间复杂度O(n2)，空间O(1);
（2）合并后排序；时间复杂度O(n)；两个字符串（数组？），比较是否相等，忽略顺序？
把数组转化为byte[] arr = string.getBytes(); Arrays.sort(arr);然后比较是否相等。有序链表，让奇数位升序偶数位降序，让链表变成升序的。
这道题可以分成三步：
（1）首先根据奇数位和偶数位拆分成两个链表。
（2）然后对偶数链表进行反转。
（3）最后将两个有序链表进行合并。将一个L长有序数组A放入2L长数组B（前L有序，后L为空）得到一个有序数组，三种方法。
–新建一个2L长数组，将A的元素与B第一个比较，＜A放新建第一个,看A第二个与B第一个，否则B放第一个，看A与B第二个………
–B的后L个为空，合成后的最大值不是在A的后一个要不就是在B的最后一个，由后往前填，不用添加新数组
–拼接 插入排序在一个给定数组中找到最大的两个数？
（1）排序；
（2）一趟遍历，用max,max2存较大的数。注意，每次从max和max2中较小的一个数，和数组中的元素比较。以下算法时间复杂度为O(n)。海量数据topK算法？
先拿k个数建堆，然后一次添加剩余元素，如果大于堆顶的数（k中最小的），将这个数替换堆顶，并调整结构使之仍然是一个最小堆，这样，遍历完后，堆中的k个数就是所需的最大的k个。建堆时间复杂度是O（mlogm），算法的时间复杂度为O（nmlogm）（n为总数据量，m为k）。
优化的方法：可以把所有10壹个数据分组存放，比如分别放在1000个文件中。这样处理就可以分别在每个文件的10^6个数据中找出最大的10000个数，合并到一起在再找出最终的结果。给定1/2/3/4/5五个数，已知现在有m = 12543。求用这五个数凑出大于m的最小值（数字不能重复，如：111111）。
换m第一个降序的两个数，然后把后面的逆序。已知有A、B两个增序数组，先将A、B合成一个新的增序数组C，该如何操作？
需要另外空间的话，双指针遍历。不需要另外空间的话，末尾遍历。两个人取100个小球，每次取1个或2个，最后拿不到球的人输，如果你是先手，有什么策略可以一定赢？
100/3=33余1,那么策略为甲先拿1个球，然后当乙拿了x个球，甲拿3-x即可，最后不管乙拿了多少个，甲都能保证一次性拿完。1001个球，两人拿，一次只能拿1,2,4次，甲先拿，最后一个拿球的人输，甲必胜策略？
1001-4=997，不能被3整除，所以甲先拿4个，后面不管乙拿多少个，甲可以保证和乙的和能被3整除（3或6），这样最后剩下的一个球肯定就是乙的。基本排序算法中，哪一个最快，说说原理？
平均情况下，快排较快。因为堆排序下，数据读取的开销变大。举例使用分治思想的算法。
归并排序。把递归实现的快排改成非递归，你知道非递归有什么好处吗？
递归好处：代码更简洁清晰。一般来说，一个人可能很容易的写出前中后序的二叉树遍历的递归算法，要写出相应的非递归算法就比较考验水平了，恐怕至少一半的人搞不定。所以说递归代码更简洁明了。
递归坏处：由于递归需要系统堆栈，所以空间消耗要比非递归代码要大很多。而且，如果递归深度太大，可能系统撑不住。大数据排序？
1.把一个bigdata文件拆分成N个小文件，小文件容量小于当前机器的内存;
2.对小文件进行排序处理;
3.对小文件进行并归排序;什么是哈夫曼编码？
哈夫曼（Huffman）编码算法是基于二叉树构建编码压缩结构的，它是数据压缩中经典的一种算法。算法根据文本字符出现的频率，重新对字符进行编码。因为为了缩短编码的长度，我们自然希望频率越高的词，编码越短，这样最终才能最大化压缩存储文本数据的空间。哈夫曼二叉树是一颗带权重的二叉树，权重是由队列中每个字符出现的次数所决定的。并且哈夫曼二叉树始终保证权重越大的字符出现在越高的地方。
1.根据给定的n个权值{w1 , w2 , w3 , … , wn},构造n棵只有根节点的二叉树，令其权值为wi。
2.在森林中选取两棵根节点权值最小的树作为左右子树，构造一棵新的二叉树，置新的二叉树的权值为左右子树的权值和。
3.在森林中删去这两棵已被合并的树，将新得到的二叉树加入到森林中。
4.重复以上两步，直到最后森林中只含有一棵树，那么这棵树就是哈夫曼树。
应用：有了上面带权重的二叉树之后，我们就可以进行编码了。我们把二叉树分支中左边的支路编码为0，右边分支表示为1。这样依次遍历这颗二叉树就可以获取得到所有字符的编码了。经过这个编码设置之后我们可以发现，出现频率越高的字符越会在上层，这样它的编码越短；出现频率越低的字符越会在下层，编码越短。经过这样的设计，最终整个文本存储空间才会最大化的缩减。100盏灯,编号依次为1,2,3…100,电灯全部关着。现在来了100个人,第一个人把所有的灯开关按下；第二个人隔一个灯按下（2,4,6…）；第三个人每隔两个灯按下（3,6,9…）.第100个人隔99个灯按下（100）,最后还有几盏灯，那几盏灯亮着？
用0 代表 灯灭 1 代表灯亮。用一个array[100][100]储存每个人按的状态 index 由1—100 初始值为0。array[i][j]代表第i个人按了第j盏灯。
for（i=1；i＜＝100;i++)
for（j＝1；j<=100；j++）
if(j%i==0）{
arrray[i][j]=1; }排序数组怎么在O（n）内生成一个乱序的数组？
排序数组怎么在O（n)约瑟夫问题 O(n)的算法？
n表示人数，m表示出局的编号。最终的递推关系式为：
f(1,m) = 0; (n=1)
f(n,m)=(f(n-1,m)+m)%n; （n>1）两个文件都是10G，里面存着32位整数型，给8G内存，怎么求交集？
哈希法，通过哈希值来对文件中的数据分到多个文件中，然后两个文件分解完的文件中相对应的再进行数据比较，确定是否有相同的数据，如果有就输出。一棵树，求所有路径之和？
结点数-130瓶水，其中有一瓶毒药，小白鼠喝了毒药之后一天会死，求只有一天时间，用最少的小白鼠找出毒药。输出a~z全排列。
海明码。所需小白鼠数量为大于等于以2为底n+1的对数的最小整数。给定一个文件名，如何在d盘找出来这个文件，说说思路。
递归遍历d盘所有文件夹，寻找匹配的文件。25匹马，只有一个5个赛道的跑道，最少多少次，找到top3？
5+1+1=7;一共有n乘以n匹马，有一个赛场，赛场有n个赛道，就是说最多同时可以有n匹马一起比赛。假设每匹马都跑的很稳定，不用任何其他工具，只通过马与马之间的比赛，试问最少得比多少场才能找出跑得最快的k匹马。
(1)如果k = 1, f(n,k) = n + 1；
(2)如果k>1 && k <= n, f(n,k) = n + 1 + w(n,k)
(3)如果k>n, f(n,k) = n + 1 + w(n,k) + k - n实现斐波拉契数列?
递归和非递归两种方式。F(0)=0，F(1)=1, F(n)=F(n-1)+F(n-2)排序01无序数组，最低的时间复杂度。
（1）借助一个额外的数组，去寻找原始数组中的元素1，找到从新数据的末端开始不断插入1元素；
（2）原地排序。两个指针，一个从头，一个从末尾，尾指针遇到0和头指针遇到1互换，两指针相遇结束。将一个四则表达式变为后缀波兰表达式 比如
1+5*2变为125*+
Java数据结构和算法（六）——前缀、中缀、后缀表达式
一个中缀式到其他式子的转换方法：a+b*c-(d+e)
第一步：按照运算符的优先级对所有的运算单位加括号：式子变成拉：((a+(b*c))-(d+e))第二步：转换前缀与后缀表达式
前缀：把运算符号移动到对应的括号前面 则变成拉：-( +(a *(bc)) +(de)) 把括号去掉：-+a*bc+de 前缀式子出现 后缀：把运算符号移动到对应的括号后面 则变成拉：((a(bc)* )+ (de)+ )- 把括号去掉：abc*+de+- 后缀式子出现
给定一个排序后的数组，要求移除重复的元素，返回新的数组长度。要求O(1)空间。/两个数组合并成一个升序数组，去掉重复的数？
使用双指针。使用两个下标i和j，其中i用于记录去重后所得新数组最后一个元素的位置，j用于遍历整个数组，i和j同向移动，通过j移动来带动i的移动。在处理中，当遇到j和i所指向的元素值不同时，把j所指元素的值拷贝到新数组最后一个位置（i所在位置），然后将i向后移动一位。当遇到j和i所指的元素值相同时，不对i进行处理，只移动j，这样就能保证i遍历过得元素值各不相同。快排为什么快？
Quicksort是对归并排序算法的优化，继承了归并排序的优点，同样应用了分治思想。
所谓的分治思想就是对一个问题“分而治之”，用分治思想来解决问题需要两个步骤：
1.如何“分”？（如何缩小问题的规模）
2.如何“治”？（如何解决子问题）
快排的前身是归并，而正是因为归并存在不可忽视的缺点，才产生了快排。归并的最大问题是需要额外的存储空间，并且由于合并过程不确定，致使每个元素在序列中的最终位置上不可预知的。针对这一点，快速排序提出了新的思路：把更多的时间用在“分”上，而把较少的时间用在“治”上。从而解决了额外存储空间的问题，并提升了算法效率。
快排之所以被称为“快”排，是因为它在平均时间上说最快的，主要原因是硬件方面的，每趟快排需要指定一个“支点”（也就是作为分界点的值），一趟中涉及的所有比较都是与这个“支点”来进行比较的，那么我们可以把这个“支点”放在寄存器里，如此这般，效率自然大大提高。除此之外，快排的高效率与分治思想也是分不开的。给一个数n，快速判断是否为2的N次幂。
(n-1) & n == 0 ? true:false;数组，链表，队列，栈之间的关系。
队列和栈可以用链表或者数组实现。数组是顺序存储结构，链表是链式存储结构。统计文本中出现频率最高的前五个单词。/一篇英文文献，怎么找出出现次数最多的单词？
顺序读文件中，对于每个词x，取hash(x)%5000，然后按照该值存到5000个小文件（记为x0,x1,…x4999）中。这样每个文件大概是200k左右。
如果其中的有的文件超过了1M大小，还可以按照类似的方法继续往下分，直到分解得到的小文件的大小都不超过1M。
对每个小文件，统计每个文件中出现的词以及相应的频率（可以采用trie树/hash_map等），并取出出现频率最大的100个词（可以用含100个结点的最小堆），并把100个词及相应的频率存入文件，这样又得到了5000个文件。下一步就是把这5000个文件进行归并（类似与归并排序）的过程了。多个字符串求最长公共前缀。
寻找若干个字符串的最长公共前缀 Longest Common Prefix查找数组中是否存在任意一个三角形。
（1）先将数组从大到小进行排序。
（2）将数组排序后，固定一个数c（从0到n-3），然后左指针b=c+1，右指针a=n-1；循环直到a<b，如果nums[a] + nums[b] > nums[c]，那么a与b之间所有的数都成立，随后左指针b++；否则，说明a不够大，a–。该算法复杂度O(n2)。（Leetcode611. Valid Triangle Number）2017的2017次方的最后一位数是什么？
7。两个有序链表a和b，合并成有序链表c？
1.链表L1的第一个结点的值小于链表L2的第一个结点的值，因此链表1的头结点是合并后链表的头结点。
2.在剩下的结点中链表L2的第一个结点的值小于链表L1的第一个结点的值，因此将链表二的第一个结点与第一步的头结点连接。
3.然后继续在剩下的结点中重复第二、三步，直到有链表为空。给一串数字，把它翻译成汉语。最大到亿。
阿拉伯数字转为中文读法B+树和二叉树的区别?
B+树一种多路搜索树，是多叉树。有两个数组，一个数组里存放的是正整数，另一个数组里存放的是负整数，都是无序的，现在从两个数组里各拿一个，使得它们的和最接近零。
先将两个数组排序，正数从小到大，负数从大到小。i，j然后两个指针从头到尾遍历两个链表。如果i+j的结果<0，i++；如果结果大于0，j++。在这过程中用个变量min记录绝对值。找出数组中和为M的两个数。
排序数组。先用M减去数组中每个数，得到一个新数组arr。设定2个指针i和j，分别指向老数组的头和新数组的尾。找到相同就返回。时间复杂度O（n），空间复杂度O（1）。链表中倒数第K个大的数。
建立一个大小为K的数组arr，用2个变量max和min标记arr的最大值和最小值。遍历链表，每次用链表中的值替换掉arr中的最小值。直到遍历结束，min即为所求。有一个无序的数据流，维护已经有的数字里的中位数。
用两个堆实现。一个最大堆，一个最小堆。保证最小堆里的数都大于最大堆里的数。如何将一个搜索二叉树，转为有序的双向链表？
中序遍历，调整打印的根节点。贪心算法是什么？
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。动态规划和贪心算法都是用来求最优化问题，且二者都必须具有最有子结构。贪心算法可以解决的问题，动态规划都能解决，可以说，贪心算法是动态规划的一个特例。有一个能够产生1-5的随机数的函数，如何利用这个函数实现产生1-7的随机函数。
更通俗一般的如果randomM()产生0~M-1之间的随机数，那么插空一次randomM()M+randomM()产生0~M^2-1之间的随机数。 ` int x = 5 (random5() - 1) + random5() - 1;`判断两个链表是否相交。
4种情况：- 先判断两个链表有没有环；
- 两个无环链表；
- 一个有环一个无环；(不可能相交)
- 两个都有环；
LRU算法？
LRU就是Least Recently Used的缩写，翻译过来就是“最近最少使用”。也就是说LRU算法会将最近最少用的缓存移除，让给最新使用的缓存。而往往最常读取的，也就是读取次数最多的，所以利用好LRU算法，我们能够提供对热点数据的缓存效率，能够提高缓存服务的内存使用率。
通过对LinkedHashMap继承实现。B+，B，红黑树，二叉搜索树，平衡搜索树?avl树怎么构建，怎么调整？
二叉搜索树，平衡树，B，b-，b+,b*,红黑树
AVL调整平衡的基本思想：旋转
当在二叉排序树中插入一个节点时，首先检查是否因插入而破坏了平衡，若破坏，则找出其中的最小不平衡二叉树，在保持二叉排序树特性的情况下，调整最小不平衡子树中节点之间的关系，以达到新的平衡。
所谓最小不平衡子树，指离插入节点最近且以平衡因子的绝对值大于1的节点作为根的子树。
RR-左旋转；LL-右旋转；LR；RL；求二维数组的盆地？
岛问题。
