本文已被 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 倍
@Overridepublic void push(T item) { if (this.arr.length == size) { this.resize(2 * this.arr.length); } this.arr[size++] = item;}
复制代码
在pop方法中需要检查当前占用的空间是否是数组的四分之一，如果是，就需要把数据的容量缩小到原来的一半
@Overridepublic 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
评论