这里写目录标题
*
– 冒泡排序
– 选择排序
– 插入排序
– 快速排序
– 双边循环
– 什么是面向对象
–
+ 它的三个基本特征:封装、继承、多态
– 重载和重写的区别
– 接口和抽象类的区别
– String StringBuffer StringBuilder的区别
– JAVA 中的异常体系
– Final 修饰符、
–
+ 为什么局部内部类和匿名内部类只能访问局部final变量?
– JDK JRE JVM三者的区别和联系
– hashCode与equals
– 深拷贝和浅拷贝的区别
– List和Set的区别
– ArrayList
– LinkedList
– CopyonWriteArrayList
– HashMap
– 单例模式
–
+ 1.饿汉式(类一加载就创建了单例对象)
+ 2.懒汉式(调用生成实例方法才会生成实例 )
+
* DCL( 双检索) 懒汉式(可以认为是对懒汉式的优化)
* 内部类懒汉式 (不需要考虑线程安全问题)
– 线程有哪些状态
– 线程池的核心参数
– sleep 和 wait的 异同点
– lock 和 synchronized的对比
1.掌握手写二分查找的代码
步骤
1)数组排序
2 取中间值和目标值比较
3)再取中间值比较。。。。。。
规范描述
1.前提:有已排序数组A
2.定义左边界L,右边界R 确定搜索范围,循环执行二分查找
3.获取中间索引M=Floor((L+R)/2)
4.中间索引A[M]与带搜索到值T进行比较
1)A[M]==T 找到 返回中间索引
2)A[M]>T 中间值右侧的其他元素都大于T无需比较。中间索引左边去找,M-1为右边界.重新查找 。
3)A[M]
int l=0;
int r=arr.length-1;
where(lr)
{
n=(l+r)/2;
if(arr[n]==t)
{
return n;
}else if( a[n]>t)
{
r=n-1;
}else {
l=n+1;
}
}
return -1;
问题:如何避免获取中间索引时整数溢出?(当元素特别多左右边界相加时整数溢出)
解决方法:
1.(l+r)/2 => l/2 +r/2=>l+(-l/2+r/2)=>l+(r-l)/2
2.(l+r)>>>1
小练习
1.共有13个元素 中间是第7个 为31 48>31 在31右侧找
2 右侧6个元素 取中间靠左元素 45 45
一直/2 一直到1 看除了几次 或 2的几次方是128
冒泡排序
相邻两个元素比较,如果前一个元素大于后一个元素交换位置
描述:、
1.依次比较数组中相邻两个元素大小,若a[j]> a[j+1],则交换两个元素,两两都比较一遍称为一轮冒泡,结果是让最大的元素排至最后
2.重复以.上步骤,直到整个数组有序
for(int j=0;j<arr.length-1;j++)
{
for(int i =0;i<arr.length-1;i++)
{
if(arr[i]>arr[i+1]){
int t =arr[i]
a[i] =a[i+1]
a[i+1]=t
}
}
}
优化冒泡 每次冒泡完一轮后 最后面一次可以不用比较 逐级递减
for(int j=0;j<arr.length-1;j++)
{
for(int i =0;i<arr.length-1-j;i++)
{
if(arr[i]>arr[i+1]){
int t =arr[i]
a[i] =a[i+1]
a[i+1]=t
}
}
}
优化冒泡: 减少冒泡次数 可能在冒泡过程还没结束时 数组已经有序了 那么可以不用再往下进行循环
在每次冒泡之前 判断元素是否发生交换 不发生交换则说明已经有序
for(int j=0;j<arr.length-1;j++)
{
boolean swapped =false;
for(int i =0;i<arr.length-1-j;i++)
{
if(arr[i]>arr[i+1]){
int t =arr[i];
arr[i] =arr[i+1];
arr[i+1]=t;
swapped =true;
}
}
if(!swapped){
break;
}
System.out.println(Arrays.toString(arr));
}
选择排序
刚开始所有元素均处于未排序状态中
我们要从未排序元素中的第一个元素开始和后面比较 取到最小的元素 然后和数组前面未排序的交换位置
描述:
1.将数组分为两个子集,排序的和未排序的,每一轮从未排序的子集中选出最小的元素,放入排序子集
2.重复以 上步骤,直到整个数组有序
for(int i =0 ; i<arr.length-1;i++)
{
int s= i ;代表最小元素的小标
for(int j = s+1 ;j<arr.length; j++) {
if(arr[s]>arr[j])
{
s=j;
}
}
if(s!=i)
{
int swap=0;
swap = arr[i];
arr[i]=arr[s];
arr[s]=swap;
}
}
冒泡排序 与选择排序比较
1.二者平均时间复杂度都是0(n2)
2.选择排序一般要快于冒泡,因为其交换次数少
3.但如果集合有序度高,冒泡优于选择
4.冒泡属于稳定排序算法,而选择属于不稳定排序
插入排序
从未排序的元素中一个个取出来 插入到已排序的之中
描述
1.将数组分为两个区域,排序区域和未排序区域,每一轮从未排序区域中取出第一个元素,插入到排序区域(需保证顺序)
2.重复以上步骤,直到整个数组有序
与选择排序比较
. 二者平均时间复杂度都是0(n2)
2.大部分情况下,插入都略优于选泽
3.有序集合插入的时间复杂度为0(n)
4.插入属于稳定排序算法,而选择属于不稳定排序
for(int i =1;i<arr.length;i++)
{
int t =arr[i];
int j =i-1;
while(j>=0){
if(t<arr[j]){
arr[j+1]=arr[j];
}else {
break;
}
j--;
}
arr[j+1]=t;
System.out.println(Arrays.toString(arr));
}
}
[5, 7, 6, 1, 5, 7, 4, 8]
[5, 6, 7, 1, 5, 7, 4, 8]
[1, 5, 6, 7, 5, 7, 4, 8]
[1, 5, 5, 6, 7, 7, 4, 8]
[1, 5, 5, 6, 7, 7, 4, 8]
[1, 4, 5, 5, 6, 7, 7, 8]
[1, 4, 5, 5, 6, 7, 7, 8]
快速排序
每一轮排序选择一 个基准点(pivot) 进行分区
1.让小于基准点的元素的进入-一个分区,大于基准点的元素的进入另一一个分区
2.当分区完成时,基准点元素的位置就是其最终位置在子 分区内重复以上过程,直至子分区元素个数少于等于1,这体现的分而治之的思想(divide-and-conquer)
1.平均时间复杂度是 0(n log2n),最坏时间复杂度0(n2)
2.数据量较大时, 优势非常明显
3.属于不稳定排序
单边循环
public static void main(String[] args) {
int arr[] = {5,3,7,2,9,8,1,4};
quick(arr,0,arr.length-1);
}
public static void quick(int arr[],int l,int h){
if(l>=h)
{
return;
}
int p = partition(arr, l, h);
quick(arr,l,p-1);
quick(arr,p+1,h);
}
public static int partition(int arr[],int l,int h){
int pv =arr[h];
int i =l;
for(int j = i;j<h;j++){
if(arr[j]<pv){
int swap = arr[j];
arr[j]=arr[i];
arr[i]=swap;
i++;
}
}
int swap =arr[h];
arr[h]=arr[i];
arr[i]=swap;
System.out.println(Arrays.toString(arr));
return i;
}
双边循环
public static void main(String[] args) {
int arr[] = {5,3,7,2,9,8,1,4};
quick(arr,0,arr.length-1);
}
public static void quick(int arr[],int l,int h){
if(l>=h)
{
return;
}
int p = partition(arr, l, h);
quick(arr,l,p-1);
quick(arr,p+1,h);
}
public static int partition(int arr[],int l,int h){
int pv =arr[l];
int i=l;
int j=h;
while(i<j){
while (i<j&&arr[j]>pv){
j--;
}
while(i<j&&arr[i]pv){
i++;
}
int swap =arr[j];
arr[j]=arr[i];
arr[i]=swap;
}
int swap = arr[i];
arr[i]=arr[l];
arr[l]=swap;
System.out.println(Arrays.toString(arr));
return j;
}
什么是面向对象
对象,就是对问题中的事物的抽象
面向对象:
就是把现实中的事物都抽象为”对象”。每个对象是唯一的,且都可以拥有它的属性与行为。我们就可以通过调用这些对象的方法、属性去解决问题。
它的三个基本特征:封装、继承、多态
封装:封装(encapsulation)即信息隐蔽。它是指在确定系统的某一部分内容时,应考虑到其它部分的信息及联系都在这一部分的内部进行,外部各部分之间的信息联系应尽可能的少。
四种访问控制级别
public:对外公开,访问级别最高
protected:只对同一个包中的类或者子类公开
默认:只对同一个包中的类公开
private:不对外公开,只能在对象内部访问,访问级别最低
继承:让某个类型的对象获得另一个类型的对象的属性和方法。继承就是子类继承父类的特征和行为,使得子类对象(实例)具有父类的实例域和方法,或子类从父类继承方法,使得子类具有父类相同的行为。
多态:对于同一个行为,不同的子类对象具有不同的表现形式。
重载和重写的区别
; 接口和抽象类的区别
String StringBuffer StringBuilder的区别
; JAVA 中的异常体系
Final 修饰符、
; 为什么局部内部类和匿名内部类只能访问局部final变量?
JDK JRE JVM三者的区别和联系
; hashCode与equals
深拷贝和浅拷贝的区别
; List和Set的区别
ArrayList
1.ArrayList的扩容机制
无参构造默认生成一个长度为零的数组 ,若使用add进行数组元素添加 第一次长度会扩容为10 之后每一次会在这个基础上扩容1.5倍
调用adaAll进行元素添加时,若数组中没有元素则会扩容为10或者元素的实际个数的长度的较大值,若数组中已经存在元素,则会扩容为原容量的1.5倍或者元素实际个数的较大值
每次扩容是生成一个新的数组 把原有元素放进扩容后的数组 然后原有的会被删除
2.掌握Iterator 的 fail-fast fail-safe 机制
fail-fast:一旦发现遍历的同时其他人来修改,则立刻抛异常
整个过程中,iterator的指针只进行过一次定义,所以它的指针会保持为第一时的状态,然而在循环执行过程中,list集合发生了长度上的变动,所以对应的iterator指针也应该做相应的调整,因为物理位置发生了改变,但可惜的是,iterator还是保持第一次声明时的状态,所以这个时候iterator.next()指针所保持的物理地址已经不符合当前要求了,故会抛出java.util.ConcurrentModificationException该异常。02
fail-safe :发现遍历的同时其他人来修改,应当有应对策略,例如牺牲一致性来让整个遍历运行完成
CopyOnWriteArrayList替换ArrayList,就不会抛出异常。
fail-safe 集合中的所有对集合的修改都是先复制一个副本。然后在副本上进行。并不会在原来的集合中进行修改。并且这些修改方法都是加锁进行控制的
; LinkedList
ArrayList 与 LinkedList 的比较
CopyonWriteArrayList
; HashMap
HashMap底层数据结构是什么 1.7 与1.8有什么不同?
HashMap何时会扩容?
当元素个数达到数组长度的四分之三时会进行扩容
数组的容量都是2的n次幂
1.7 底层是数组+链表 1.8底层是数组 +(链表或红黑树) 元素比较多的时候使用红黑树 当元素少的时候使用链表
另一个答案
单例模式
单例模式 :一个类控制只有一个实例
1.饿汉式(类一加载就创建了单例对象)
1)构造方法私有
2) 提供一个静态的成员变量 成员变量的类型就是单例类的类型 值是用私有构造器创建都唯一实例
3)提供一个方法返回实例 供外部调用
public class Singleton1 implements Serializable {
private Singleton1(){
}
private static final Singleton1 INSTANCE = new Singleton1();
public static Singleton1 getInstance(){
return INSTANCE;
}
}
防止反射破坏单例可以在构造器加一个判断
public class Singleton1 implements Serializable {
private Singleton1(){
if(INSTANCE !=null){
throw new RuntimeException("单例对象不能重复创建");
}
}
private static final Singleton1 INSTANCE = new Singleton1();
public static Singleton1 getInstance(){
return INSTANCE;
}
}
防止序列化破坏单例可以 在类中写一个特殊的方法 readResolve
pulic Object readResolve (){
return INSTANCE;
}
2.懒汉式(调用生成实例方法才会生成实例 )
private Singleton1(){
}
private static Singleton1 INSTANCE = null;
public static Singleton1 getInstance(){
if(INSTANCE==null){
INSTANCE = new Singleton1();
}
return INSTANCE;
}
这样多线程环境下不安全 需要加锁
public static synchronized Singleton1 getInstance(){
if(INSTANCE==null){
INSTANCE = new Singleton1();
}
return INSTANCE;
}
DCL( 双检索) 懒汉式(可以认为是对懒汉式的优化)
因为 上面的懒汉式加了锁 是每次调用时都会判断当前锁有没有被占用,但其实只有初始化实例时需要调用,所以这样会影响性能
需要加上volatile 修饰 //解决共享变量的 可见性,有序性 在这里是解决 有序性
private static volatile Singleton1 INSTANCE = null;
public static Singleton1 getInstance() {
if (INSTANCE == null) {
synchronized (Singleton1.class) {
if (INSTANCE == null) {
INSTANCE = new Singleton1();
}
}
}
return INSTANCE;
}
内部类懒汉式 (不需要考虑线程安全问题)
public class Singleton1 implements Serializable {
private Singleton1() {
}
private static class Holder{
static Singleton1 INSTANCE = new Singleton1();
}
public static Singleton1 getInstance(){
return Holder.INSTANCE;
}
}
线程有哪些状态
JAVA线程分为六种状态
1)NEW 新建
2)RUNNABLE 可运行
3)TERMINATED 终结
4)BLOCKED 阻塞
5)WAITING 等待
6)TIMED_WAITING 等待(有时限)
操作系统层面共有五种状态
1.新建
2.就绪
3.运行
4.阻塞
5.终结
; 线程池的核心参数
sleep 和 wait的 异同点
; lock 和 synchronized的对比
Original: https://blog.csdn.net/weixin_46427348/article/details/127699737
Author: 小屁孩不努力
Title: 简单的小复习(一)
原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/652728/
转载文章受原作者版权保护。转载请注明原作者出处!