力扣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; } }
