万字详细面试被吊打的总结（SE-＞数据结构-＞MYSQL)-阿里云开发者社区

力扣138.随机链表的问题（经典——重要)

我是有思路，但是20分钟，确实我的头脑没有转那么快，没有做出来，我就想到拆分，把它依次连接

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;
 
    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
 
class Solution {
   public static Node copyRandomList(Node head) {
       if (head==null)
        return null;
        Node cur=head;
        while(cur!=null){
            Node a=new Node(cur.val);
            a.next=cur.next;
            cur.next=a;
            cur=cur.next.next;
        }
        Node newhead=head.next;
        cur=newhead;
        Node prev=head;
        while(cur!=null&&cur.next!=null){
            if(prev.random!=null){
                cur.random=prev.random.next;
            }
            prev=prev.next.next;
            cur=cur.next.next;
        }
        if(prev.random!=null){
        cur.random=prev.random.next;}
        cur=newhead;
        prev=head;
 
        while(cur!=null&&cur.next!=null){
            prev.next=prev.next.next;
            cur.next=cur.next.next;
            prev=prev.next;
            cur=cur.next;
        }
            prev.next=null;
     
        return newhead;
    }
}

面试题1:java创建对象有几种方式

1.new 对象这个就不用说了，简单

2.反射 Class对象调用newInstance()接口

 String m = "Node";
 Class clas=Class.forName(m);
 Node t=(Node) clas.newInstance();

3.使用Constructor类的newInstance方法

 Constructor<Node> constructor =Node.class.getConstructor();
        Node t2=constructor.newInstance();
        System.out.println(t2);

这两种都叫反射，事实上Class对象的newInstance在内部也是调用的Constructor这个类

4.Object类实现的clone接口

public class Node implements  Cloneable{
        int val;
        Node next;
        Node random;
 
        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
//需要重写这个方法
    @Override
    protected Object clone() throws CloneNotSupportedException {
        return super.clone();
    }
 
    public Node() {
    }
}

 public static void main(String[] args) throws ClassNotFoundException, InstantiationException, IllegalAccessException, CloneNotSupportedException {
//       String m = "Node";
//       Class clas=Class.forName(m);
//       Node t=(Node) clas.newInstance();
        Node t1=new Node(5);
        Node t2=(Node)t1.clone();
        System.out.println(t1==t2);
 
    }

5.通过序列化来创建对象

面试题2:hashmap的底层数据结构？hashcode重写为什么必须要重写equals？

hashmap（JDK1.7的时候，是使用的拉链法，只有数组和链表

但是JDK1.8的时候，有了数组，链表，红黑树，扩容的时候resize()，红黑树拆分树的节点，小于6个退化成链表）我准备挺多的，但是hashcode这块确实没有看（只能说知道啥意思，但是具体的忘记了）

拿到一个hash值之后，利用key的hashcode重新hash计算在数据中下标。

equals是比较两个对象是否相等，

hashcode用于获取对象的哈希码。

如果equal()方法判断为相等，则他们的hashcode必须返回相同的值，这是因为使用哈希表等数据结构时，会先根据对象的哈希码确定存储位置，然后再使用 equals() 方法进行比较来确保唯一性。

1.如果重写了equals，但是没有重写hashcode()方法，可能会导致对象放入哈希表中，hashcode返回的不是相同的值，从而无法正常操作这个对象

2.当使用哈希集合的时候，由于HashCode返回的不是相同的值，哈希集合也无法判断这两个对象是否相等，从而又可能会导致set 有重复元素.

面试题3:ArrayList和LinkedList的区别

ArrayList基于数组,LinkedList基于双向链表

对于随机访问，ArrayList优于LinkedList

对于插入和删除操作，LinkedList优于ArrayList(详细：LinkedList优于ArrayList头插，因为LinkedList只需要移动指针，但是ArrayList需要搬运元素)

LinkedList中间的插入数据慢，ArrayList中间插入数据较快）LinkedList尾插慢，ArrayList尾插速度快，不需要移动位置

ArrayList的内部

 
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    private static final long serialVersionUID = 8683452581122892189L;
 
    /**
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;
 
    /**
     * Shared empty array instance used for empty instances.
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};
 
    /**
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
 
    /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */
    transient Object[] elementData; // non-private to simplify nested class access
 
    /**
     * The size of the ArrayList (the number of elements it contains).
     *
     * @serial
     */
    private int size;
 
    /**
     * Constructs an empty list with the specified initial capacity.
     *
     * @param  initialCapacity  the initial capacity of the list
     * @throws IllegalArgumentException if the specified initial capacity
     *         is negative
     */
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

DEFAULT_CAPACITY默认容量为10.

size:当前ArrayList元素个数

elementData:用于存储实际元素的数组

MAX_ARRAY_SIZE：数组的最大容量，一般为Integer.MAX_VALUE - 8。

扩容的触发条件:

1.添加元素:size>elementData的长度

2.使用带有指定初始容量的构造方法，并且该初始容量大于默认容量，也会触发扩容

新容量一般为原先容量的1.5倍

为什么说快排的空间复杂度最优情况下是O(N)*（logN），最坏情况下是O（N^2）？（知识点：堆排序，快排，归并）

第一次Partiation应该是需要对整个数组扫描一遍，做n次比较,他是递归的过程，一层一层的去遍历，那么也就是说我们需要求他的层数，总结点，是一个等比数列求和，每一层是2的等比数列，累加在一起，然后我们使用log ，来求出他的层数，最后就是N*log,但是不好的情况就是N^2,因为他这个时候，就不是一个树，更像是类似于链表，都是连起来的，那么层高就是N,所以复杂度就是O(N^2)

这里首先要全面的写一下堆和快排和归并排序

堆最好是一颗完全二叉树（用数组存储),假如不是，会造成空间浪费)

小根堆/大根堆

根节点都比左右孩子小。（小根堆特性中序遍历，全部顺序。）

建立的是一个大根堆

import java.util.Arrays;
 
public class TestHeap {
    //自己去写一个堆
    public int[] elem;
 
    public int usedSize;
 
    public TestHeap() {
        this.elem = new int[10];
    }
 
    //创建一个大根堆
    public void createHeap(int[] array) {
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            usedSize++;
        }
        for (int parent = (usedSize - 1 - 1) / 2; parent >= 0; parent--) {
            //向下调整，需要给的数字，当前父亲位置，结束位置
            shiftDown(parent, usedSize);
        }
    }
 
 
 
    /**
     * @param parent 每颗子树根节点
     * @param len    每个子树的结束位置
     */
    //向下调整,已知孩子下标len-1拿到,父亲节点(len-1-1)/2
    public void shiftDown(int parent, int len) {
        int child = parent * 2 + 1;
        //看他是否有左孩子
        while (child < len) {
            if(child+1<len){
            if(elem[child]<elem[child+1]){
                child=child+1;
            }
            }
            if (elem[child] > elem[parent]) {
                int tmp = elem[parent];
                elem[parent] =elem[ child];
                elem[child] = tmp;
                parent = child;
                child = parent * 2 + 1;
            }else{
                break;
            }
        }
    }
 
 
    //保证仍然原先是大根堆，还是小根堆(当插入一个元素的时候，先插入到最后一个位置),插入后，直接和根比较
    //向上调整
    public void push(int val){
        //检查是否满了
        //2.存数据
        if(isFull()){
            elem=Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize]=val;
        usedSize++;
 
        shiftUp(usedSize-1);
    }
 
 
 
    public  boolean isFull(){
        return usedSize==elem.length;
    }
 
 
 
    public void shiftUp(int child){
        int parent=(child-1)*2;
        while(child>0){
            if(elem[child]>elem[parent]){
                int tmp=elem[child];
                elem[child]=elem[parent];
                elem[parent]=tmp;
                child=parent;
                parent=(child-1)/2;
            }else{
                break;
            }
        }
    }
    //假如只能删除堆顶，还要保持他是一个大根堆的形态（那么就要头和最下面的换，然后去，向下调整)
public void  poll(){
        int tmp =elem[0];
        elem[0]=elem[usedSize-1];
        //让0下标元素和最下面的元素交换，然后再去向下调整（把size--即可）
        elem[usedSize-1]=tmp;
        usedSize--;
        shiftDown(0,usedSize);
 
}
//堆排序
    public void headSort(){
        int end=usedSize-1;
        while(end>0){
            //本身已经是一个大根堆
            int tmp=elem[0];
            elem[0]=elem[end];
            elem[end]=tmp;
            shiftDown(0,end);
            end--;
        }
    }
 
 
 
}

建立堆的时间复杂度约等于O(N)，向下调整

关于PriorityQueue的问题(类似于堆，所以，他内部会有一个比较的操作):

1.PriorityQueue放置的元素必须能够比较大小，不能插入无法比较的对象，否则就会抛出ClassCastException(类型转换异常)

倘若非要添加一个自定义类型，你要实现Comparable，这个方法

2.不能插入NULL,不然会抛空指针

3.没有容量限制，内部会自动扩容

4.底层是使用了堆堆数据结构

5.默认是小堆

equal:所有的类继承自Object,所以直接覆写，但是只能比较是否相等

Comparable.compareTo:手动实现接口，对类的侵入性强，要在类的里面，一旦实现，每次用这个类，都有顺序，属于其内部顺序

Comparator.compare:实现一个比较器对象，对类的侵入性弱，可以仅仅写一个类的属性的比较，这样易扩展。

TOP-K问题(找到十个数字中，最小的5个数)

1.排序后取5个数字，就是最小的

2.堆，建立一个小根堆(建立一个堆O(N),弹一个元素要去调整->k*log(N)+O(N)

  static class Imp implements  Comparator<Integer>{
 
          @Override
          public int compare(Integer o1, Integer o2) {
               return o2-o1;
          }
     }
     public  static  int[] smallestK2(int []array,int k){
          
          int []ret=new int[k];
          if(k==0){
               return ret;
          }
          //PriorityQueue必须大于0
          PriorityQueue <Integer>maxHeap=new PriorityQueue<>(new Imp());
          for(int i=0;i<k;i++){
               maxHeap.offer(array[i]);
          }
          for(int i=k;i< array.length;i++){
               int top=maxHeap.peek();
               if(top>array[i]){
                    maxHeap.poll();
                    maxHeap.offer(array[i]);
               }
          }
         
          for(int i=0;i<k;i++){
               ret[i]=maxHeap.poll();
          }
          return ret;
     }

怎么从小到大排序:要求数组本身有序

（堆很多都是反的情况）建立大根堆。

不断调整堆，然后堆顶和堆尾换（最后一个未排序的结果end)

1.交换

2.调整(0下标)

  /**
     * @param parent 每颗子树根节点
     * @param len    每个子树的结束位置
     */
    //向下调整,已知孩子下标len-1拿到,父亲节点(len-1-1)/2
    public void shiftDown(int parent, int len) {
        int child = parent * 2 + 1;
        //看他是否有左孩子
        while (child < len) {
            if(child+1<len){
            if(elem[child]<elem[child+1]){
                child=child+1;
            }
            }
            if (elem[child] > elem[parent]) {
                int tmp = elem[parent];
                elem[parent] =elem[ child];
                elem[child] = tmp;
                parent = child;
                child = parent * 2 + 1;
            }else{
                break;
            }
        }
    }
 
 
//堆排序
    public void headSort(){
        int end=usedSize-1;
        while(end>0){
            //本身已经是一个大根堆
            int tmp=elem[0];
            elem[0]=elem[end];
            elem[end]=tmp;
            shiftDown(0,end);
            end--;
        }
    }

快速排序（N*log(N)，好的情况（完全二叉树，正好均匀分割，不稳定的排序）

面试题的回答:

不断去找基准，然后去排序。

public class Sort {
 
    public void  quickSort(int []array){
        quick(array,0, array.length-1);
    }
    private static int parttion(int []array,int left,int right){
        int i=left;
        int key=array[left];
        while(left<right){
            //这里一定要有等于符号
            //测试用例:6,1,2,7,5,3,4,5,10,6    这个情况，left和right是一直不会动动
           //左边的key，要从右边开始先移动
//为什么先移动右边
//答案：为了避免平移交换过程中, pivot自己被交换掉。
            while(left<right&&array[right]>=key){
                right--;
            }
            while(left<right&&array[left]<=key){
                left++;
            }
            swap(array,left,right);
        }
        swap(array,left,i);
        return left;
    }
 
    private static void swap(int[] array, int i, int left) {
        int tmp=array[i];
        array[i]=array[left];
        array[left]=tmp;
    }
 
    private static  void quick(int[]array,int start,int end){
        if(start>=end){
            return ;
        }
        int pivot=parttion(array,start,end);
 
        quick(array,0,pivot-1);//左树
        quick(array,pivot+1,end);//右树
    }
//挖坑法
 private  int pattion1(int []array,int left,int right){
        int tmp=array[left];
        while(left<right){
            while (left<right&&array[right]>=tmp){
                right--;
            }
            array[left]=array[right];
            while(left<right&&array[left]<=tmp){
                left++;
            }
            array[right]=array[left];
        }
        array[left]=tmp;
        return left;
    }
 
//快排非递归
   public   void  quickSort1(int[]array){
        //  使用栈
        Stack<Integer> stack=new Stack<>();
        int start=0;
        int end=array.length-1;
        int pivot=parttion(array,start,end);
        //至少有两个元素才可以入栈
        //保证左边
        if(pivot>start+1){
            stack.push(start);
            stack.push(pivot-1);
        }
        //保证右边
        if(pivot<end-1){
            stack.push(pivot+1);
            stack.push(end);
        }
        while(!stack.isEmpty()){
            end= stack.pop();
            start=stack.pop();
            //弹出后，再去找基准
            pivot=parttion(array,start,end);
            if(pivot>start+1){
                stack.push(start);
                stack.push(pivot-1);
            }
            //保证右边
            if(pivot<end-1){
                stack.push(pivot+1);
                stack.push(end);
            }
        }
    }
 
 
 
}

归并排序(N*log(N),空间复杂度O(N),稳定的排序）

ublic void mergeSort(int []array){
        mergeSortFunc(array,0,array.length-1);
}
private   void  mergeSortFunc(int[]array,int left,int right){
        if(left>=right){
            return;
        }
        int mid=(left+right)/2;
    //这两个相当于遍历到二叉树的最下面了
        mergeSortFunc(array,left,mid);
        mergeSortFunc(array,mid+1,right);
        
        merge(array,left,mid,right);
}
public void merge(int[]array,int left,int mid,int right){
        int s1=left;
        int e1=mid;
        int s2=mid+1;
        int e2=right;
        int []tmpArr=new int[right-left+1];
        int k=0; //tmpArr数组的下标
    while(s1<=e1&&s2<=e2){
        if(array[s1]<=array[s2]){
            tmpArr[k++]=array[s1];
            s1++;
        }else{
            tmpArr[k++]=array[s2];
            s2++;
        }
        k++;
    }
    while(s1<=e1){
        tmpArr[k]=array[s1];
        s1++;
        k++;
    }
    while(s2<=e2){
        tmpArr[k]=array[s2];
        s2++;
        k++;
    }
    //tmpArr放入所有有序的数据
    for(int i= 0;i<k;i++){
        array[i+left]=tmpArr[i];
    }
}
//归并非递归
    public void mergerSort(int[]array){
        int gap=1;
        while (gap<array.length){
            for(int i=0;i<array.length;i=i+gap*2){
                int left=i;
                int mid=left+gap-1;
                int right=mid+gap;
                //这个是进行合并的操作
                if(mid>array.length){
                    mid=array.length-1;
                }
                if(right>array.length){
                    right=array.length-1;
                }
                merge(array,left,mid,right);
            }
            gap=gap*2;
        }
    }

万字详细面试被吊打的总结（SE-＞数据结构-＞MYSQL)

力扣138.随机链表的问题（经典——重要)

面试题1:java创建对象有几种方式

1.new 对象这个就不用说了，简单

2.反射 Class对象调用newInstance()接口

3.使用Constructor类的newInstance方法

这两种都叫反射，事实上Class对象的newInstance在内部也是调用的Constructor这个类

4.Object类实现的clone接口

5.通过序列化来创建对象

面试题2:hashmap的底层数据结构？hashcode重写为什么必须要重写equals？

面试题3:ArrayList和LinkedList的区别

扩容的触发条件:

为什么说快排的空间复杂度最优情况下是O(N)*（logN），最坏情况下是O（N^2）？（知识点：堆排序，快排，归并）

快速排序（N*log(N)，好的情况（完全二叉树，正好均匀分割，不稳定的排序）

归并排序(N*log(N),空间复杂度O(N),稳定的排序）

热门文章

最新文章

相关课程

相关电子书

相关实验场景

推荐镜像

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

万字详细面试被吊打的总结（SE-＞数据结构-＞MYSQL)

力扣138.随机链表的问题（经典——重要)

面试题1:java创建对象有几种方式

1.new 对象这个就不用说了，简单

2.反射 Class对象调用newInstance()接口

3.使用Constructor类的newInstance方法

这两种都叫反射，事实上Class对象的newInstance在内部也是调用的Constructor这个类

4.Object类实现的clone接口

5.通过序列化来创建对象

面试题2:hashmap的底层数据结构？hashcode重写为什么必须要重写equals？

面试题3:ArrayList和LinkedList的区别

扩容的触发条件:

为什么说快排的空间复杂度最优情况下是O(N)*（logN），最坏情况下是O（N^2）？（知识点：堆排序，快排，归并）

快速排序（N*log(N)，好的情况（完全二叉树，正好均匀分割，不稳定的排序）

归并排序(N*log(N),空间复杂度O(N),稳定的排序）

热门文章

最新文章

相关课程

相关电子书

相关实验场景

推荐镜像