目录
力扣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),稳定的排序
面试题4:简单描述一下事务的四大特性，追问隔离级别有哪些
力扣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 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
implements List
{
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 if(elem[child] 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 @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 for(int i=0;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 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 if(elem[child] 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 //这里一定要有等于符号 //测试用例:6,1,2,7,5,3,4,5,10,6 这个情况，left和right是一直不会动动 //左边的key，要从右边开始先移动 //为什么先移动右边 //答案：为了避免平移交换过程中, pivot自己被交换掉。 while(left right--; } while(left 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 while (left right--; } array[left]=array[right]; while(left left++; } array[right]=array[left]; } array[left]=tmp; return left; } //快排非递归 public void quickSort1(int[]array){ // 使用栈 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 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 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 array[i+left]=tmpArr[i]; } } //归并非递归 public void mergerSort(int[]array){ int gap=1; while (gap for(int i=0;i 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; } } 面试题4:简单描述一下事务的四大特性，追问隔离级别有哪些 四大特性: 原子性：原子性是指一个不可分割的工作单位，事务中的操作，要么全部成功，要么全部失败，（我的回答比较口语，要么全部成功，要么全部失败) 一致性：事务必须使数据库从一致性，变换到另一个一致性的状态，（换一种思考，就是你事务操作的按照预期执行，就是一致性） 隔离型：多个用户并发访问数据库时，数据库为每个用户开启的事务，不能被其他事物的操作数据所干扰。 持久性(这个没答出来):对数据的改变时永久的 隔离级别: 读未提交：它允许另外一个事务可以看到这个事务未提交的数据。 读提交：保证一个事物提交后才能被另外一个事务读取。另外一个事务不能读取该事物未提交的数据。 读重复：这种事务隔离级别可以防止脏读，不可重复读。但是可能会出现幻象读。它除了保证一个事务不能被另外一个事务读取未提交的数据之外还避免了以下情况产生(不可重复读)。 序列化：这是花费最高代价但最可靠的事务隔离级别。事务被处理为顺序执行。除了防止脏读，不可重复读之外，还避免了幻象读。 脏读（读取未提交数据） A事务读取B事务尚未提交的数据，此时如果B事务发生错误并执行回滚操作，那么A事务读取到的数据就是脏数据 不可重复读（前后多次读取，数据内容不一致） 事务A在执行读取操作，由整个事务A比较大，前后读取同一条数据需要经历很长的时间 ，B此时修改了一下你读的数据，这时候前后读的数据不一样 幻读（前后多次读取，数据总量不一致） 事务A在执行读取操作，需要两次统计数据的总量，前一次查询数据总量后，此时事务B执行了新增数据的操作并提交后，这个时候事务A读取的数据总量和之前统计的不一样 推荐文章
您阅读本篇文章共花了：
发表评论