目录
1.初识
2.时间复杂度
常见时间复杂度举例：
3.空间复杂度
4.包装类&简单认识泛型
4.1装箱和拆箱
5.泛型
6.泛型的上界
7.泛型方法
8.List接口
1.初识
1.多画图
2.多思考
3.多写代码
4.多做题
牛客网-题库/在线编程/剑指offer 算法篇：面试必刷TOP101(学哪个刷哪个)
5.看书籍：《大话数据结构》 查漏补缺
数据结构 是一门逻辑非常严谨的学科 学习的时候，学习的时候要多调试 因为代码量非常多！！！
前置知识：
1.泛型
2.包装类
Java当中集合类背后就是数据结构，集合类有很多，所以把这些集合类有些书上会叫作：集合框架
集合框架 里面有很多的集合类，每个集合类背后又是一个数据结构
学习的角度：
1.背后的数据结构
2.对应的集合类
3.集合框架
学习目标：
1.认识Java当中的集合类
2.学习复杂度
本质：数据结构的种类有很多！
为什么会有这么多数据结构？-》描述或者组织数据的方式不同
每一个集合类描述和组织数据的方式是不一样的
概念：什么是数据结构？
数据结构=》数据+结构--》描述或者组织一些数据
2.时间复杂度
衡量算法效率~~~
算法中基本操作的执行次数，为算法的时间复杂度
e.g. 3N^2+2N+10
三条规定：
1.用常数1取代运行时间中的所有加法常数 3N^2+2N+1
2.再修改后的运行次数函数中，只保留最高阶项 3N^2
3.如果最高阶项存在且不是1，则去除与这个项相乘的常数 所以 O（N^2）
常见时间复杂度举例：
// 计算bubbleSort的时间复杂度？（冒泡排序）
//相邻元素两两交换void bubbleSort(int[] array) {for (int end = array.length; end > 0; end--) {boolean sorted = true;for (int i = 1; i < end; i++) {if (array[i - 1] > array[i]) {Swap(array, i - 1, i);sorted = false;}}if (sorted == true) {break;}}
}
最好： (n -1)+(n -2)+...+1+0 = 1/2*n^2 O(N^2)
最坏：O（N）
//二分查找
int binarySearch(int[] array, int value) {int begin = 0;int end = array.length - 1;while (begin <= end) {int mid = begin + ((end-begin) / 2);if (array[mid] < value)begin = mid + 1;else if (array[mid] > value)end = mid - 1;elsereturn mid;}return -1;
}
时间复杂度的计算 不能光看代码 还要结合思想
// 计算阶乘递归factorial的时间复杂度？
long factorial(int N) {return N < 2 ? N : factorial(N-1) * N;
}
递归的复杂度 = 递归的次数*每次递归执行的次数
时间复杂度为O（N)
// 计算斐波那契递归fibonacci的时间复杂度？
int fibonacci(int N) {return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);
}
时间复杂度为O(2^n)
常见的复杂度：结合代码的思想来看
O（1） O(logN) O(N) O(N*logN) O(N*2)
3.空间复杂度
临时占用存储空间大小的量度
冒泡排序 O(1)
斐波那契 O(N)
递归 O(N)
4.包装类&简单认识泛型
除了 Integer 和 Character， 其余基本类型的包装类都是首字母大写
4.1装箱和拆箱
public class Main{public static void main(String[] args) {Integer a = new Integer(10);int b = a;//自动拆箱System.out.println(b);//显示拆箱 拆箱为自己指定的元素int c = a.intValue();System.out.println(c);double d = a.doubleValue();System.out.println(d);}public static void main1(String[] args) {//装箱：把一个基本数据类型转化为包装类型的过程//自动装箱 & 显示装箱int a = 10;Integer b = a;//自动装箱System.out.println(b);Integer c = Integer.valueOf(a);//显示装箱System.out.println(c);}
}面试题： 为什么一个True，一个False呢？
原因：
装箱的源代码：
5.泛型
/*
实现一个类，类中包含一个数组成员，使得数组中可以存放任何类型的数据，也可以根据成员方法返回数组中某个下标的值*/
import java.util.Arrays;//<T>:代表当前类是一个泛型类
//<T extends Number> T是Number或者Number的子类
class MyArray<T>{public Object[] array = new Object[10];//public T[] array = new T[10];不允许实例化一个泛型数组//public T[] array = (T[])new Object[10]; 这样写也不好！！！public void set(int pos,T val){array[pos] = val;}public T get(int pos){return (T)array[pos];//强转成T类型的元素}public Object[] getArray(){return array;}}
public class Main{public static void main(String[] args) {MyArray<String> myArray = new MyArray<>();//指定String类型的数据myArray.set(0,"hello");//myArray.set(1,90);这里不能放整型了String str = myArray.get(0);System.out.println(str);Object[] ret = myArray.getArray();System.out.println(Arrays.toString(ret));//相当于将类型作为参数传给TMyArray<Integer> myArray2 = new MyArray<>();myArray2.set(0,1);Integer a = myArray2.get(0);System.out.println(a);}
}
底层原理：
6.泛型的上界
class 泛型类名称 < 类型形参 extends 类型边界 > {}
小试牛刀：（复杂实例）
/*
写一个泛型类 实现一个方法，这个方法是求指定类型数组的最大值的T extends Comparable<T> T一定是实现Comparable接口的
* */class Alg<T extends Comparable<T>> {public T findMax(T[] array) {T max = array[0];for (int i = 1; i < array.length; i++) {if(array[i].compareTo(max) >0){max = array[i];}}return max;}
}
class A implements Comparable<A>{@Overridepublic int compareTo(A o) {return 0;}
}
public class Main{public static void main(String[] args) {Alg<String> alg = new Alg<>();Alg<Integer> alg2 = new Alg<>();Alg<Integer> alg3 = new Alg<>();Integer[] array = {1,13,51,71,19};Integer ret = alg2.findMax(array);System.out.println(ret);}
}extends在泛型中：上界 （拓展）
7.泛型方法
接下来我们实现一个泛型方法
class Alg2 {//泛型方法public<T extends Comparable<T>> T findMax(T[] array) {T max = array[0];for (int i = 1; i < array.length; i++) {if(array[i].compareTo(max) >0){max = array[i];}}return max;}
}
public class Main{public static void main(String[] args) {Alg2 alg2 = new Alg2();Integer[] array = {1,13,51,71,19};Integer ret = alg2.findMax(array);System.out.println(ret);}
} 变成静态的话，不用实例化对象
8.List接口
import java.util.*;public class Main{ArrayList<String> arrayList = new ArrayList<>();List<String> list = new ArrayList<>();//推荐写法List<String> list1 = new Stack<>();List<String> list2 = new Vector<>();List<String> list3 = new LinkedList<>();}
