写点什么

面试的季节到了,老哥确定不来复习下数据结构吗

用户头像
Silently9527
关注
发布于: 2021 年 02 月 18 日
面试的季节到了,老哥确定不来复习下数据结构吗

本文已被 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


发布于: 2021 年 02 月 18 日阅读数: 7
用户头像

Silently9527

关注

公众号:贝塔学JAVA 2018.05.09 加入

Simple Programmer, Make the complex simple

评论

发布
暂无评论
面试的季节到了,老哥确定不来复习下数据结构吗