java面试经典题目二(数据结构与算法)
2017-12-26 本文已影响50人
chansonpro
数据结构与算法
【1】常见的几大排序及查找算法及其时间复杂度？
答：
1.冒泡算法--O(n2)核心代码如下：（百度）
BubbleSort
2.快速排序--O（nlogn）,核心代码如下：（京东）
找到中间元素
快速排序
3.二分查找--O(log2n),核心算法如下:
二分查找
返回aim的位置，不是索引
【2】求数组中最长连续序列长度。(美团)
答：使用哈希表实现，复杂度为O(n)。
【3】在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序， 请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
【4】两个栈实现一个队列。(美团、小米)
答：其实这道题目很简单，就是两个栈来回的倒，这个题，本人遇到过不下2次了，每次都写的不好，现在整理下。【详细参考】
两个栈实现一个队列
扩展：两个队列如何实现一个栈？
队列实现栈1
队列实现栈2
// poll使用方法,获取并删除列表的第一个元素
// peek使用方法,获取并不删除列表的第一个元素
// pop取堆栈中取出元素，并出栈
【5】链表反转（单项链表的反转和双向链表的反转）
答：先说单向链表。
基本思路是：
将当前节点cur的下一个节点 cur.getNext()缓存到temp后，然后更改当前节点指针指向上一结点pre。也就是说在反转当前结点指针指向前，先把当前结点的指针域用temp临时保存，以便下一次使用，其过程可表示如下：
pre：上一结点
cur: 当前结点
temp: 临时结点，用于保存当前结点的指针域（即下一结点）
单链表反转
双向链表反转：[详细参考]
【6】给Map排序---按照key的字母后按照格式[k1=v1:k2=v2]输出（阿里旅行）
答：
【7】输入一个整数，，输出该整数二进制表示中1的个数，其中负数用补码表示。
答：
