数据结构预备知识

news/2024/12/23 7:56:54/

目录

1. 什么是集合框架

2. 什么是数据结构

3. 容器背后对应的数据结构

4. 相关java知识

5. 时间复杂度

6. 空间复杂度

7. 包装类

7.1 装箱和拆箱

7.2 阿里面试题：

8. 泛型

8.1 泛型的语法

8.2 泛型怎样编译

9. 泛型的上界

9.1 语法

9.2 泛型方法

1. 什么是集合框架

Java集合框架又被称为container，是定义在java.util包下的一组接口interfaces和其实现类classes.

主要表现为将多个元素element置于一个单元中，用于对这些元素进行快速、便捷的存储store、检索retrieve、管理manipulate，即我们俗称的增删改查CEUD

2. 什么是数据结构

数据结构是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合

3. 容器背后对应的数据结构

每个容器都是对某种特定数据结构的封装

Collection:是一个接口，包含大部分容器常用的一些方法

List:是一个接口，规范了ArrayList和LinkedList中要实现的方法

  • ArrayList:实现了List接口，底层为动态类型顺序表
  • LinkedList:实现了List接口，底层为双向链表

Stack:底层是栈，栈是一种特殊的顺序表

Queue:底层是队列，队列是一种特殊的顺序表

Deque:是一个接口

Set:集合，是一个接口，里面放置的是K模型

  • HashSet:底层为哈希桶
  • TreeSet:底层为红黑树

Map:映射，里面存储的是K-V模型的键值对

  • HashMap:底层为哈希桶
  • TreeMap:底层为红黑树

4. 相关java知识

  1. 泛型Generic
  2. 自动装箱autobox和自动拆箱autounbox
  3. Object的equals方法
  4. Comparable和Comparator接口

5. 时间复杂度

大O符号：是用于描述函数渐进行为的数学符号

推导大O阶方法：

  1. 用常数1取代运行时间中的所有加法常数
  2. 在修改后的运行次数函数中，只保留最高阶项
  3. 如果最高阶项存在且不是1，则去除与这个项目相乘的常数

平常所说的时间复杂度和空间复杂度都是指最坏情况下

注意：结合算法思想，不能只看代码

冒泡排序的时间复杂度：O (n^2)（一开始就是倒序的），最好是O(n)（一开始就是有序的）

二分查找的时间复杂度：O(logn)

阶乘递归的时间复杂度：O(n)

斐波那契递归的时间复杂度：O(2^n)

6. 空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。空间复杂度不是程序占用了多少bytes的空间，而是变量的个数。与时间复杂度一样，也使用大O渐进表示法

冒泡排序的空间复杂度：O(1)

阶乘递归的空间复杂度：O(n)

常遇到的复杂度：

O(1)<O(logN)<O(N)<O(N*logN)<O(N^2)

7. 包装类

在Java中，由于基本类型不是继承自Object,为了在泛型代码中可以支持基本类型，Java给每个基本类型都对应了一个包装类型

7.1 装箱和拆箱

装箱：把基本数据类型变为包装类类型的过程

public class Test {public static void main(String[] args) {int a = 10;Integer i = Integer.valueOf(a);//显式装箱Integer i2 = 10;//自动装箱（隐式装箱，底层调用了Integer.valueOf方法）Double d = Double.valueOf(a);}
}

拆箱：把包装类类型变为基本数据类型的过程

public class Test {public static void main(String[] args) {Integer a = 10;int b = a;//自动拆箱int c = a.intValue();//显式、手动double d = a.doubleValue();}
}

使用javap -c在cmd中（找到该段代码的文件位置然后输入cmd）可以查看底层代码实现

7.2 阿里面试题：
public class Test {public static void main(String[] args) {Integer a = 100;Integer b = 100;System.out.println(a == b);//trueInteger c = 200;Integer d = 200;System.out.println(c == d);//false}
}

分析：

装箱的操作：

    @IntrinsicCandidatepublic static Integer valueOf(int i) {if (i >= IntegerCache.low && i <= IntegerCache.high)return IntegerCache.cache[i + (-IntegerCache.low)];return new Integer(i);}

上述代码中的 i 应该在一个范围的时候直接返回数组中的值，否则返回新的对象

用等号比较，必然不一样。

i 的范围：-128~127(共256个数字，在cache缓存中)

8. 泛型

一般的类和方法，只能使用具体的类型：基本类型或自定义的类。如果要编写可以应用于多种类型的代码，这种刻板的限制对代码的束缚就会很大。——《Java编程思想》

泛型，通俗讲：就是适用于许多许多类型；从代码上将：对类型实现了参数化

class MyArray{public Object[] array=new Object[10];public void setValue(int index,Object value){array[index]=value;}public Object getValue(int index){return array[index];}
}
public class Test {public static void main(String[] args) {MyArray myArray=new MyArray();myArray.setValue(0,10);myArray.setValue(1,"hello");String str=(String)myArray.getValue(1);System.out.println(str);//hello}
}

以上代码存在一些问题：

  1. 存放数据太乱，什么类型都能放
  2. 每次获取数据时，都要进行强转

泛型可以解决，泛型的主要目的：指定当前的容器，要持有什么类型的对象，让编译器去检查。此时，要把类型作为参数传递，需要什么类型，就传入什么类型。

8.1 泛型的语法
class 泛型类名称<类型形参列表>{//这里可以使用类型参数
}
class MyArray<E>{//<E>占位符表示一个泛型public Object[] array=new Object[10];public void setValue(int index,E value){array[index]=value;}public E getValue(int index){return (E)array[index];}
}
public class Test {public static void main(String[] args) {MyArray<Integer> myArray=new MyArray<Integer>();myArray.setValue(0,10);
//        myArray.setValue(1,"hello");//自动类型检查Integer value=myArray.getValue(0);//自动类的转换System.out.println(value);//10MyArray<String> myarray=new MyArray<>();//可以省略类型实参的填写myarray.setValue(0,"hello");String value1=myarray.getValue(0);System.out.println(value1);//hello}
}

了解：【规范】类型形参一般使用一个大写字母表示，常用名称有：

E表示Element,K表示Key,V表示Value,N表示Number,T表示Type

<>中只能写类类型，不能写简单类型（编译不能通过）

裸类型是一个泛型类但没有带着类型实参，例如：

MyArray list=new MyArray();

注意：我们不要自己去使用裸类型，裸类型是为了兼容老版本的API保留的机制

8.2 泛型怎样编译

泛型是编译时期的一种机制，在运行的时候没有泛型的概念【JVM中没有泛型的概念】

在编译的过程中，将所有的E替换为Object这种机制，称之为：擦除机制

class MyArray<E> {//<E>占位符表示一个泛型public Object[] array = new Object[10];public void setValue(int index, E value) {array[index] = value;}public E getValue(int index) {return (E) array[index];}
}public class Test {public static void main(String[] args) {MyArray<Integer> myArray = new MyArray<>();MyArray<Integer> myArray2 = new MyArray<>();Test test = new Test();System.out.println(myArray);//MyArray@3b07d329System.out.println(myArray2);//MyArray@41629346System.out.println(test);//Test@404b9385}
}

9. 泛型的上界

在定义泛型类时，有时需要对传入的类型变量做一定的约束，可以通过类型边界来约束

9.1 语法
class 泛型类名称<类型形参 extends 类型边界>{...
}

例如：

public class MyArray<E extends Number>{...
}

没有指定类型边界的E,可以视为E extends Object

复杂实例：

public class MyArray<E extends Comparable<E>>{...
}

E必须是实现了Comparable接口的

class Alg<E extends Comparable<E>> {public E findMax(E[] arr) {E max = arr[0];for (int i = 1; i < arr.length; i++) {if (arr[i].compareTo(max) > 0) {max = arr[i];}}return max;}
}class Person implements Comparable<Person> {@Overridepublic int compareTo(Person o) {return 0;}
}public class Test {public static void main(String[] args) {Alg<Integer> alg = new Alg<>();System.out.println(alg.findMax(new Integer[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}));//10Alg<Person> alg1 = new Alg<>();System.out.println(alg1.findMax(new Person[]{new Person()}));//Person@41629346}
}
9.2 泛型方法
class Alg {public<E extends Comparable<E>> E findMax(E[] arr) {E max = arr[0];for (int i = 1; i < arr.length; i++) {if (arr[i].compareTo(max) > 0) {max = arr[i];}}return max;}
}public class Test {public static void main(String[] args) {Alg alg = new Alg();Integer[] arr = {1,2,3,4,5,6};int ret=alg.findMax(arr);System.out.println(ret);//6}
}

静态泛型方法：

class Alg {public static <E extends Comparable<E>> E findMax(E[] arr) {E max = arr[0];for (int i = 1; i < arr.length; i++) {if (arr[i].compareTo(max) > 0) {max = arr[i];}}return max;}
}public class Test {public static void main(String[] args) {Integer[] arr = {1, 2, 3, 4, 5, 6};System.out.println(Alg.findMax(arr));//6}
}


http://www.ppmy.cn/news/1512680.html

相关文章

2024年“研究生科研素养提升”系列公益讲座在线测试

2024年“研究生科研素养提升”系列公益讲座在线测试

一、单选题 1、SCI是指&#xff08; &#xff09; A 、中国科学引文索引 ✓ B 、科学引文索引Science Citation Index C 、社会科学引文索引 D 、国际科学引文索引 参考答案&#xff1a; B 答案解析&#xff1a;SCI是指科学引文索引 Science Citation Index 2、下列哪个数…
阅读更多...
使用 lateral view explode(col1)后行数变少了，bug排查

使用 lateral view explode(col1)后行数变少了，bug排查

问题复现 查询该表结果为100行 select count(1) as cnt from ( select distinct a,b,c from pageAds ) 查询下表条数为90行 select count(1) as cnt from ( select distinct a,b,c from pageAds ) lateral view explode(split(a,,)) adTable as d 思考&#xff1a;第二条语…
阅读更多...
学习使用pymodbus模块实现Modbus通讯

学习使用pymodbus模块实现Modbus通讯

Modbus是一种工业领域广泛使用的通信协议&#xff0c;而PyModbus是一个在Python中实现Modbus通信的库。它支持多种Modbus模式&#xff0c;包括RTU&#xff08;通过串行线路&#xff09;&#xff0c;ASCII和TCP/IP。 1. 建立通讯 from pymodbus.client import ModbusTcpClient…
阅读更多...
synchronized锁状态和底层实现

synchronized锁状态和底层实现

锁的状态 无锁状态&#xff0c;偏向锁状态&#xff0c;轻量级锁状态&#xff0c;重量级锁状态。锁的状态是通过对象监视器在对象头中的字段来表明的&#xff0c;四种状态会随着竞争的情况逐渐升级。偏向锁、轻量级锁、重量级锁是针对synchronized的状态。 这四种状态都不是 Jav…
阅读更多...
开始尝试从0写一个项目--后端（四）

开始尝试从0写一个项目--后端（四）

借出&#xff0c;归还&#xff0c;管理 学生和管理员登录分离 学生登录到用户界面 管理员到后台 后台和用户分离 添加代码 sems-server/src/main/java/com/ljc/controller/user/UserStudentController.java package com.ljc.controller.user;import com.ljc.constant.Jwt…
阅读更多...
怎么对前端的一些按钮做一个权限校验

怎么对前端的一些按钮做一个权限校验

在一般情况下,我们需要对一些按钮做一个权限校验,来保证只有有权限的用户才能看到 1.创建一个js文件,来写我们的全局方法 我的方法是这样的 import Vue from vue;Vue.mixin({methods:{hasAuth(perm) {var authority this.$store.state.menu.permList;if (authority.indexOf(…
阅读更多...
AI科学家学问世，学术圈会有大动荡吗？

AI科学家学问世，学术圈会有大动荡吗？

导读&#xff1a; 继ChatGPT等大型语言模型的突破之后&#xff0c;The AI Scientist的诞生更是令人震撼。这个全面自动化的科学研究系统能独立完成从生成研究想法到撰写论文的全过程&#xff0c;或许&#xff1a; 科学家要不存在了。©️【深蓝AI】编译 1. 摘要 通用人工智…
阅读更多...
Qt-认识Qt(1)

Qt-认识Qt(1)

目录 QT是做什么的&#xff1f; 什么是QT GUI开发的各种技术方案 QT支持的平台 Qt的版本和优点 开发工具概述 Qt是做什么的&#xff1f; Qt是用来干嘛的&#xff1f; 什么是Qt Qt是⼀个跨平台的C图形用户界⾯应用程序框架。它为应用程序开发者提供了建立艺术级图形界⾯所…
阅读更多...
最新文章

Copyright @ 2022~2023