共计 6463 个字符，预计需要花费 17 分钟才能阅读完成。
本文已被 Github 仓库收录 https://github.com/silently9527/JavaCore
微信公众号：贝塔学 Java
前言
在上一次《面试篇》Http 协定中，面试官本来想的是 http 问的差不多了，想要持续问我 JAVA 相干的一些问题，后果我忽然感觉嗓子不难受咳嗽了几声，（在这个敏感的时候）吓退了面试官，面试官带起口罩后就说面试先临时到这里，下次再聊；两周之后我又收到了 HR 的电话；
HR：感冒好了吗？上次面试的后果不错，你什么时候有工夫来咱们公司二面呢？
我：随时筹备着
到公司后，我仍然被带到了那个小黑屋，期待着面试官的到来。没想等来的是一位美女小姐姐。
我：人美声甜的小姐姐，你是本次的面试官？（我窃喜中）
美女面试官：是的，上次面试你的面试官散会去了，这次面试我来和你聊聊
面试官：看你这么会谈话，让我先来帮你开个胃，说说二分查找吧
我：（果然是开胃啊，这位小姐姐居然如此凶恶）
我：二分查找法是在一个有序的数组中查到一个值，如果存在就返回在数组中的索引，否则就返回 -1；算法保护了两个变量 lo(最小)和 hi(最大)，每次查找都与两头值 (mid) 进行比拟，如果等于就返回 mid，大于就查问右半边的数组，小于就查问左半边数组。二分查找法之所以快是因为每次一次查问都会排除掉一半的值。
No BB, show you the code（不废话，间接看代码）
public class BinarySearch {
/**
* 二分查找
* @param key
* @param arr
* @return 存在返回对应的下标，不存在返回 -1
*/
public static int search(int key, int[] arr) {
int lo = 0, hi = arr.length - 1;
while (lo <= hi) {int mid = lo + (hi - lo) / 2;
if (key > arr[mid]) {lo = mid + 1;} else if (key < arr[mid]) {hi = mid - 1;} else {return mid;}
}
return -1;
}
}
对于一个蕴含 n 个元素的列表，用二分查找法最多须要 log2n（后面的 2 是底数）次就能够判断出元素是否存在；所以二分查找法的工夫复杂度是O(log n)
面试官：说说应用数组如何实现栈？
我：小姐姐，栈的特点就是后进先出，应用数组和链表都能够实现栈的性能，首先看下栈的定义：
public interface Stack<T> extends Iterable {void push(T item); // 向栈增加元素
T pop(); // 从栈中弹出
boolean isEmpty();
int size(); // 返回元素的个数}
栈在应用的时候有可能也会遍历全副的元素，所以继承了Iterable，应用数组实现栈的残缺代码：
public class FixCapacityArrayStack<T> implements Stack<T> {private T[] arr;
private int size;
public FixCapacityArrayStack(int capacity) {this.arr = (T[]) new Object[capacity]; // 初始化数组大小
}
@Override
public void push(T item) {this.arr[size++] = item;
}
@Override
public T pop() {return this.arr[--size];
}
@Override
public boolean isEmpty() {return size == 0;}
@Override
public int size() {return this.size;}
@Override
public Iterator<T> iterator() {return new Iterator<T>() {
int index;
@Override
public boolean hasNext() {return index < size;}
@Override
public T next() {return arr[index++];
}
};
}
}
面试官：你方才实现的栈是定容的，那如何实现动静调整栈的大小
我：（已猜到你会问这个问题了，方才成心没说动静调整大小；通过多年的面试经验总结，最谐和的面试过程就是与面试官 你推我挡，一上来就说出了最优解，如何体现面试官的自卑感？）
我：要实现动静的调整大小，首先须要在提供一个 resize 的办法，把数组扩容到指定的大小并拷贝原来的数据到新的数组中；
private void resize(int newCapacity) {Object[] tmp = new Object[newCapacity];
for (int index = 0; index < size; index++) {tmp[index] = arr[index];
}
this.arr = (T[]) tmp;
}
须要 push 办法中查看以后的 size 是否曾经达到了数组的最大容量，如果是，就把数组扩容 2 倍
@Override
public void push(T item) {if (this.arr.length == size) {this.resize(2 * this.arr.length);
}
this.arr[size++] = item;
}
在 pop 办法中须要查看以后占用的空间是否是数组的四分之一，如果是，就须要把数据的容量放大到原来的一半
@Override
public T pop() {T item = this.arr[--size];
this.arr[size] = null; // 防止游离对象，让垃圾回收器回收无用对象
if (size > 0 && size == this.arr.length / 4) {this.resize(this.arr.length / 2);
}
return item;
}
面试官：方才你提到了链表，那么应用链表如何实现栈
我：（这就是 你推我挡 的后果，和小姐姐的互动很谐和）
我：应用链表，首先须要先定义个 Node，单向的链表蕴含了值和下一个节点的援用
public class Node<T> {
private T item;
private Node next;
}
采纳链表实现的栈绝对于数组实现还较为简单一些，不须要思考扩容的问题。
public class LinkedListStack<T> implements Stack<T> {
private Node<T> first;
private int size;
@Override
public void push(T item) {// 先栈顶增加元素
this.first = new Node<>(item, first);
size++;
}
@Override
public T pop() { // 从栈顶删除元素
T item = first.getItem();
size--;
first = first.getNext();
return item;
}
@Override
public boolean isEmpty() {return first == null;}
@Override
public int size() {return this.size;}
@Override
public Iterator<T> iterator() {return new Iterator<T>() {
private Node<T> current = first;
@Override
public boolean hasNext() {return current != null;}
@Override
public T next() {T item = current.getItem();
current = current.getNext();
return item;
}
};
}
}
面试官：应用链表如何实现先进先出队列
我：与栈的实现过程相似，首先须要定义出队列
public interface Queue<T> extends Iterable {void enqueue(T item); // 入队列
T dequeue(); // 出队列
int size();
boolean isEmpty();}
应用链表实现队列须要保护两个变量 first、last；first 示意的是队列的头结点，last 示意队列的尾结点；当入队列时 enqueue 向尾部结点增加元素，当出队列时 dequeue 从头结点删除元素。
public class LinkedListQueue<T> implements Queue<T> {
private Node<T> first;
private Node<T> last;
private int size;
@Override
public void enqueue(T item) {Node<T> node = new Node<>(item, null);
if (isEmpty()) {first = node; // 当队列为空，first 和 last 指向同一个元素} else {last.setNext(node);
}
last = node;
size++;
}
@Override
public T dequeue() {T item = first.getItem();
first = first.getNext();
if (isEmpty()) { // 当队列为空时，须要把 last 设置为 null
last = null;
}
size--;
return item;
}
@Override
public int size() {return this.size;}
@Override
public boolean isEmpty() {return first == null; // 首节点为空}
@Override
public Iterator<T> iterator() {return new Iterator<T>() {
private Node<T> current = first;
@Override
public boolean hasNext() {return current != null;}
@Override
public T next() {T item = current.getItem();
current = current.getNext();
return item;
}
};
}
}
面试官：胃开的差不多了，来聊一点算法吧；你来设计一个算法对算术示意式求值，比方：(1 + ( ( 2 + 3) * (4 * 5) ) )
我：（昨天晚上熬夜看算法没白辛苦啊，刚好看到了这个解法。）
我：（挠挠头），这个问题有点麻烦，我须要思考一会。(这样显得我是没有提前准备的，属于临场发挥)
我：定义两个栈，一个用于保留运算符，一个用户保留操作数；具体的操作过程如下：
- 疏忽右边括号
- 遇到数字就压入操作数栈
- 遇到符号就压入符号栈
- 遇到右括号，弹出一个运算符，弹出所须要的操作数，将计算的后果再次压入到操作数栈
public static int calculate(String expression) {Stack<String> operate = new LinkedListStack<>();
Stack<Integer> numbers = new LinkedListStack<>();
String[] split = expression.split(" ");
for (String str : split) {if ("(".equals(str)) {} else if ("+".equals(str) || "-".equals(str) || "*".equals(str) || "/".equals(str)) {operate.push(str);
} else if (")".equals(str)) {String op = operate.pop();
int resut = 0;
if ("+".equals(op)) {resut = numbers.pop() + numbers.pop();} else if ("-".equals(op)) {resut = numbers.pop() - numbers.pop();} else if ("*".equals(op)) {resut = numbers.pop() * numbers.pop();} else if ("/".equals(op)) {resut = numbers.pop() / numbers.pop();}
numbers.push(resut);
} else {numbers.push(Integer.valueOf(str));
}
}
return numbers.pop();}
面试官：一个 int 类型的数组，其中存在三个数字相加等于 0，你来设计个算法帮我统计出有多少组这样的数字
我：这个简略，请看代码：
public static int count1(int[] arr) {
int length = arr.length;
int count = 0;
for (int i = 0; i < length; i++) {for (int j = i + 1; j < length; j++) {for (int k = j + 1; k < length; k++) {if (arr[i] + arr[j] + arr[k] == 0) {count++;}
}
}
}
return count;
}
面试官：如果这个数组有 100 万的 int 值，你这个算法得运行到什么时候
我：（对的哦，这个算法的工夫复杂度是 O(n³)，在遇到数据量较大时效率极低）
（通过大脑疾速思考后）
我：这个算法的确有问题，我粗心了，没有思考到大量数据的状况；用这个算法会节约小姐姐的大好青春，所以方才我思考了下，对这个算法进行改良一下；
首先把 3-sum 简化成2-sum。
在 2-sum 中，一个数 a[i]要与另一个数相加等于 0；有两种办法：
第一种：与 3 -sum 实现相似应用两层循环，工夫复杂度是 O(n²)
第二种：只须要找出数组中是否有 -a[i]，查找的算法应用二分查找法
public static int count2(int[] arr) {Arrays.sort(arr); // 首先排序
int length = arr.length;
int count = 0;
for (int i = 0; i < length; i++) {if (BinarySearch.search(-arr[i], arr) > i) {count++;}
}
return count;
}
二分查找法的工夫复杂度是 O(log n), 实现
2-sum的算法多了一层循环，所以工夫复杂度 O(nlog n)
看待 3-sum 也是用相似的办法，间接上机撸代码：
public static int count3(int[] arr) {Arrays.sort(arr);
int length = arr.length;
int count = 0;
for (int i = 0; i < length; i++) {for (int j = i + 1; j < length; j++) {if (BinarySearch.search(-arr[i]-arr[j], arr) > j) {count++;}
}
}
return count;
}
我：小姐姐，这个算法改良之后的工夫复杂度是 O(n²log n)，我曾经尽力了，只能这么快了。（面试官露出迷人的微笑）
面试官：如果你是微信的开发人员，轻易给你两个用户，如何判断这两个用户是否连通的。何为连通？A 是 B 的好友，B 是 C 的好友，那么 A 与 C 就是连通的
我：（这小姐姐的问题是越来越难了）
我：漂亮的面试官，明天烧脑重大，我能够趴下劳动一会吗？（其实是没想到好的解法，拖延时间战术）
面试官：能够，那你先劳动 10 分钟。
面试未完，待续
最初（点关注，不迷路）
文中或者会存在或多或少的有余、谬误之处，有倡议或者意见也十分欢送大家在评论交换。
最初，写作不易，请不要白嫖我哟 ，心愿敌人们能够 点赞评论关注 三连，因为这些就是我分享的全副能源起源????
文中所有源码已放入到了 github 仓库 https://github.com/silently9527/JavaCore
参考书籍：算法第四版
程序员罕用的 IDEA 插件：https://github.com/silently9527/ToolsetIdeaPlugin
齐全开源的淘客我的项目：https://github.com/silently9527/mall-coupons-server
