集合框架（1）

集合框架&＃xff08;1&＃xff09;

数据结构是了解数据存储在内存中的顺序和位置关系&＃xff1b;算法是为求解一个问题所需要遵循的、被清楚指定的简单指令的集合。数据结构是为算法服务的&＃xff0c;算法是要作用在特定的数据结构上的。

常见的数据结构与算法&＃xff1a;

数据结构&＃xff1a;数组、链表、栈和队列、散列表hash、二叉树、堆、跳表、图

算法&＃xff1a;递归、排序&＃xff08;学习七种和三种扩展&＃xff0c;冒泡和快排必须掌握&＃xff09;、搜索、哈希、贪心、分治、回溯、动态规划、字符串匹配

学习方法

记忆接口中的方法&＃xff0c;记忆对应接口的实现类&＃xff08;区别和如何选择&＃xff0c;选择的原因是学习的重点&＃xff09;

集合框架

1. 如何持有一组数据最合理
2. 程序 &＃61; 数据结构 &＃xff08;如何持有数据&＃xff09;&＃43; 算法&＃xff08;如何解决问题&＃xff09;
3. https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

衡量算法&＃xff1a;时间和空间的选择

复杂度分析&＃xff0c;快和省的问题&＃xff0c;引入O复杂度表示法&＃xff0c;表示代码的执行时间苏浙数据规模的变化趋势

​ O(1) 常量级 O(logN)(估算&＃xff0c;并不是精确计算)对数阶 O(n^m)指数阶

递归

1. 待求解问题可分解成几个子问题&＃xff1b;
2. 待求解问题与分解和的子问题只有数据规模不同&＃xff0c;求解思路一致
3. 存在递归终止条件

练习&＃xff1a;假设有n级台阶&＃xff0c;人可以每步跨1级或者2级台阶&＃xff0c;上这n级台阶有多少种方法

思路&＃xff1a;f(n) &＃61; f(n-1) &＃43; f(n-2) 终止条件 f(1) &＃61; 2 f(2) &＃61; 2

编程实现&＃xff1a;找到将大的问题分解为小问题的规律&＃xff0c;并且基于此规律写出递推公式&＃xff0c;然后推导出终止条件&＃xff0c;最后将递推公式和终止条件编译成代码

public static int up(int num) {if (num &＃61;&＃61; 1) {return 1;}if (num &＃61;&＃61; 2) {return 2;}if (num > 3) {return up(num - 1) &＃43; up(num - 2);}return 0;}public static void main(String[] args) {int a &＃61; up(10);System.out.println(a);}


问题

1. 堆栈溢出。由于函数调用会使用函数调用栈来保存当前的运行现场&＃xff0c;但是系统栈或者虚拟机栈一般不会太大&＃xff0c;所以如果递归求解的数据规模很大&＃xff0c;调用层次很深&＃xff0c;可能导致栈溢出 StackOverflowError
2. 重复计算问题。可以引入备忘录保存已经求解的结果&＃xff0c;典型的以浪费内存为代价换取高执行效率

数组

数组(本身是一种引用类型)&＃xff1a;一组相关类型的变量集合&＃xff0c;这些变量可以按照统一下标的方式进行操作&＃xff0c;是一种典型的线性结构

特性&＃xff1a;

• 随机访问。支持在O(1)内按照下标进行快速访问元素
• 插入和删除数据可能会有数据移动问题。时间复杂度是O(n)
• 警惕数据访问越界问题ArrayIndexOutOfBoundsException

数组的基本使用

• 声明。int[] arr 或者 int arr[]
• 分配空间。数组空间是连续的&＃xff0c;arr &＃61; new int[10]&＃xff0c;java不支持变长数组&＃xff0c;如果需要变长则需要自行编程实现
• 赋值。元素都有默认值。
• 处理。可以通过下标对数组元素进行操作

排序算法1

排序算法的衡量标准&＃xff1a;

• 时间复杂度
• 空间复杂度
• 稳定性

Java中的排序算法&＃xff1a;冒泡、插入、选择、快速、哈希、归并、堆…

冒泡排序

核心思想&＃xff1a;相邻比较&＃xff0c;交换位置

空间复杂度O(1)、时间复杂度O(n^2(两级for循环嵌套))、稳定

public static void main(String[] args) {int[] arr &＃61; { 2, 21, 49, 17, 50, 1 };for (int i &＃61; 0; i < arr.length - 1; i&＃43;&＃43;) {for (int j &＃61; 0; j < arr.length - 1 - i; j&＃43;&＃43;) {if (arr[j] > arr[j &＃43; 1]) {int tmp &＃61; arr[j];arr[j] &＃61; arr[j &＃43; 1];arr[j &＃43; 1] &＃61; tmp;}}}System.out.println(Arrays.toString(arr));}


快速排序

核心思想&＃xff1a;通过一次排序将数据序列分成左右两个部分&＃xff0c;其中左半部分的值都比右半部分的值小&＃xff0c;然后再分别对左右部分的数据进行排序&＃xff0c;直到整个数据序列有序

空间复杂度O(1)、时间复杂度O(nlongn)、不稳定

数据结构概述

基本数据结构3种&＃xff1a;线性表、树、图

线性表

线性表是一种线性结构&＃xff0c;是由零个或者多个数据元素构成的有序序列。

特征&＃xff1a;除了头尾元素&＃xff0c;每个元素有且只有一个直接前驱和一个直接后继&＃xff1b;而头元素&＃xff0c;没有直接前驱&＃xff0c;尾元素没有直接后继

常见的线性结构有数组和链表结构

数组

存储区域是连续的&＃xff0c;占用内存比较严重&＃xff0c;所以空间复杂度较大&＃xff0c;但是&＃xff08;必须先进行排序&＃xff09;可以使用二分法查找元素&＃xff0c;时间复杂度较小

特点&＃xff1a;

• 地址方便&＃xff0c;时间复杂度O(1)
• 插入和删除比较困难&＃xff0c;可能会引发元素移动&＃xff0c;时间复杂度O(n)
• java中的数组是定长的&＃xff0c;如果需要变长则需要自行编程实现&＃xff08;可使用System.arrayCopy方法&＃xff09;

链表

数组需要一块连续的内存空间存储数据&＃xff0c;对内存要求较高。而链表通过指针可以将一组零散的内存块串联起来使用。

数组擅长按照下标进行随机访问&＃xff0c;链表擅长删除、插入操作

具体实现&＃xff1a;在链表中使用节点存储数据&＃xff0c;并使用引用串联各个元素。每个节点除了存储数据本身之外还需要额外存储下一个节点的地址

单向链表

public class Node{private int date;//存储集体数据private Node next;//记录下一个节点的作用&＃xff0c;尾节点指向null}


创建2个节点的流程

Node node1 &＃61; new Node();
node1.setDate(123);//具体存储数据&＃xff0c;next此时为null&＃xff1b;所以node1是一个尾节点Node node2 &＃61; new Node();
node2.setDate(456);
node1.setNext(node2);//使node1的下一个元素指针指向到node2对象


Link的实现

public class linkList{private Node head &＃61; null;//整个链表的头指针public static class Node{private int date;private Node next;}
}


新增数据

public void insert(Node a,Node b){//在节点a后面插入新节点bif(a &＃61;&＃61; null){//在链表的头部添加数据bb.next &＃61; head;head &＃61; b;}else {b.next &＃61; a.next;a.next &＃61; b;}
}


删除数据

// 删除已知前驱节点为a的节点b&＃xff0c;b的前驱节点为apublic void remove(Node a, Node b) {// 如果a为null则表示删除头节点bif (a &＃61;&＃61; null) {head &＃61; head.next;} elsea.next &＃61; b.next;}// 删除存储的数据值为value的节点public void remove(int value) {Node q &＃61; head;Node p &＃61; null;// 遍历整个单向链表&＃xff0c;查询具体存放数据为value的节点while (q !&＃61; null && q.data !&＃61; value) {p &＃61; q;q &＃61; q.next;}if (q !&＃61; null) {if (p &＃61;&＃61; null)head &＃61; q.next;elsep.next &＃61; q.next;}}


查找节点

// 查找存储数据为 value的节点public Node find(int value) {Node p &＃61; head;while (p !&＃61; null && p.data !&＃61; value) {p &＃61; p.next;}return p;}


获取指定下标的节点

// 获取指定下标的节点public Node get(int index) {Node p &＃61; head;int res &＃61; 0;while (p !&＃61; null && res !&＃61; index) {res&＃43;&＃43;;p &＃61; p.next;}return p;}


Java集合

Java集合类存放于java.util包中&＃xff0c;是用于存放对象的容器

• 集合中只能存放对象&＃xff0c;如果存入一个简单类型&＃xff0c;实际上进行了自动转换【装箱】
• 集合中存放的是多个对象的引用&＃xff0c;对象本身还是存放在堆内存
• 集合中可以存放不同类型、不限数量的数据

Collection接口

一般来说 Collection 接口是集合框架的顶级接口&＃xff0c;但是事实上不是

特征&＃xff1a; 集合中的数据无序&＃xff0c;允许重复

接口中定义的方法&＃xff1a;

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-rXNimSUO-1649138014449)(C:\Users\阿白\AppData\Roaming\Typora\typora-user-images\image-20220215220311721.png)]

size():int 获取集合中的元素个数

• 数组中实际上是不能直接获取其中存储的元素个数&＃xff0c;集合中可以分为两个概念&＃xff1a;容器是表示可以存放的元素个数&＃xff0c;类似于集合的 length&＃xff1b;size 表示实际存储的元素个数

add(Object obj):boolean 向集合中添加元素 obj

isEmpty():boolean 判断集合中的元素个数是否为 0

​ 注意&＃xff1a;只判断集合中是否没有元素&＃xff0c;并不会判断集合是否为 null

• cc.size()<1

contains(Object obj):boolean 判断当前集合中是否包含对象 obj

• 使用&＃61;&＃61;还是 equals 进行判定&＃xff1f; equals

Object 类中的 equals 方法定义

public boolean equals(Object obj){return (this &＃61;&＃61; obj);
}


如果自定义类中没有定义 equals 方法时&＃xff0c;其中的 equals 方法是从 Object 类中继承得到的&＃xff0c;这个方法是采用&＃61;&＃61;进行判断&＃xff0c;如果需要按照某个业务规则进行判断&＃xff0c;则必须自定义覆盖 equals 方法

toArray():Object[]将集合转换为数组

add(Object obj):boolean 向集合中添加元素 obj

addAll(Collection) 将另外一个集合中的所有元素添加到当前集合中

remove(Object obj):boolean 从集合中删除指定的元素 obj

clear():void 清空集合中的所有元素

List子接口

Collection 接口的子接口&＃xff0c;特征&＃xff1a;数据有序【索引编号】允许重复。在 Collection 接口的基础上添加了每个元素的索引编号&＃xff0c;编号从 0 开始到 size-1 结束

public interface List<E> extends Collection<E>{}


add(Object):boolean 向集合末尾追加元素

add(int index, E element):void 向指定索引位置 index 上添加元素 element&＃xff0c;原始数据自动后移

remove(Object):boolean 删除第一个和 object 参数相等的元素&＃xff0c;实际上是 Collection 接口中的方法

remove(int index):Object 删除指定索引值对应的元素&＃xff0c;并返回被删除的元素。

get(int index):E 获取指定索引号对应的元素&＃xff0c;要求 index 应该在[0,size-1]范围内&＃xff0c;否则异常

set(int index, E element):E 用于给指定索引位置上进行赋值操作&＃xff0c;这个位置上必须有对应的数据&＃xff0c;已经赋过值了&＃xff0c;这里实际上就是修改操作&＃xff0c;否则越界异常

indexOf(Object obj):int 从前向后查询第一个元素和 obj 相等的元素的对应索引值。如果不存在相等的时候返回-1

lastIndexOf(Object obj):int 从后向前查询最后一个元素和 obj 相等的元素的对应索引值。如果不存在相等的时候返回-1

Set子接口

没有新的方法&＃xff0c;特征&＃xff1a;无序、不允许重复

public interface Set<E> extends Collection<E>{}


基础用法

int index, E element):E 用于给指定索引位置上进行赋值操作&＃xff0c;这个位置上必须有对应的数据&＃xff0c;已经赋过值了&＃xff0c;这里实际上就是修改操作&＃xff0c;否则越界异常

indexOf(Object obj):int 从前向后查询第一个元素和 obj 相等的元素的对应索引值。如果不存在相等的时候返回-1

lastIndexOf(Object obj):int 从后向前查询最后一个元素和 obj 相等的元素的对应索引值。如果不存在相等的时候返回-1

Set子接口

没有新的方法&＃xff0c;特征&＃xff1a;无序、不允许重复

public interface Set<E> extends Collection<E>{}


基础用法