1.数据结构 1.二叉查找树java面试题:
String str="i"与 String str=new String(“i”)一样吗?String str="i"会将起分配到常量池中,常量池中没有重复的元素,如果常量池中存中i,就将i的地址赋给变量,如果没有就创建一个再赋给变量。
String str=new String(“i”)会将对象分配到堆中,即使内存一样,还是会重新创建一个新的对象。
又称二叉排序树或者二叉搜索树
特点:
- 1,每个节点上最多有两个子节点
- 2,左子树上所有节点的值都小于根节点的值
- 3,右子树上所有节点的值都大于根节点的值
目的:提高检索数据的性能
2.平衡二叉树- 满足查找二叉树的大小规则下,让树尽可能矮小,以此提高数据的性能
要求
- 任意节点的左右两个子树的高度差不超过1,任意节点的左右两个子树都是一颗平衡二叉树
解决方法:
- 进行左旋或者右旋,保证平衡
旋转的四种情况
- 左左
- 左右
- 右右
- 右左
左左:
当根节点左子树的左子树有节点插入,导致二叉树不平衡
右旋
左右:
当根节点左子树的右子树有节点插入,导致二叉树不平衡
先左旋,再右旋
右右:
当根节点右子树的右子树有节点插入,导致二叉树不平衡
左旋
右左:
当根节点右子树的左子树有节点插入,导致二叉树不平衡
先右旋,在左旋
2.红黑树每一个节点可以是红或者黑,红黑树不是通过高度平衡的,它的平衡是通过“红黑规则”进行实现的
规则:
- 每一个节点或是红色,或是黑色,根节点必须是黑色
- 每一个节点没有子节点或者父节点,则该节点相应的指针属性值为Nil,这些Nil视为叶节点,叶节点是黑色的
- 如果某一个节点是红色,那么它的子节点必须是黑色(不能出现两个红色节点相连的情况)
添加节点
- 添加的节点颜色,可以是红色的也可以是黑色的
- 默认用红色效率高
list集合的基础用法
public static void main(String[] args) {
List list = new ArrayList<>();
list.add("java");
list.add("java");
list.add("mysql");
list.add("mysql");
//在某个索引位置插入元素
list.add(2,"html");
System.out.println(list);
//根据索引删除元素,返回被删除的元素
list.remove(2);
System.out.println(list);
//根据索引获取元素
System.out.println(list.get(2));
//修改索引位置的元素
//返回修改前的数据
System.out.println(list.set(1, "redis"));
System.out.println(list);
//清空list
list.clear();
}
list遍历的四种方式
- 迭代器
- foreach
- lambda表达式
- for循环
- 底层是基于数组实现的:根据索引定位元素快,增删需要做元素的位移 *** 作
- 第一次创建集合并添加第一个元素的时候,在底层创建一个默认长度为10的数组
每次当元素加满时,数组会扩容1.5倍
查询速度快,增删较慢
数组查询方便,添加元素在指定位置时,需要先偏移该位置以及后面的元素,然后将该元素插入到指定位置,删除元素时,需要偏移该位置后面的元素。
LinkedList的特点底层数据结构是双链表,查询慢,收尾 *** 作的速度极快
LinkedList集合的特有功能
添加和删除
public static void main(String[] args) {
//模拟栈
LinkedList stack = new LinkedList<>();
stack.addFirst("第1颗子d");
stack.addFirst("第2颗子d");
stack.addFirst("第3颗子d");
stack.addFirst("第4颗子d");
System.out.println(stack);
//出栈 d栈
System.out.println(stack.removeFirst());
System.out.println(stack.removeFirst());
System.out.println(stack);
//模拟队列
LinkedList queue = new LinkedList<>();
//入队
queue.addLast("1号");
queue.addLast("2号");
queue.addLast("3号");
queue.addLast("4号");
queue.addLast("5号");
//出队
System.out.println(queue.removeFirst());
System.out.println(queue.removeFirst());
System.out.println(queue);
}
集合的并发修改异常
- 迭代器遍历集合且直接用集合删除元素的时候可能出现问题
- 增强for循环遍历集合且直接用集合删除元素的时候可能会出现
以下代码都存在漏删的风险,java会抛出异常
//使用迭代器删除所有python信息
Iterator it = list.iterator();
while (it.hasNext()){
String next = it.next();
if(next.equals("python")){
list.remove(next);
}
}
System.out.println(list);
//foreach遍历删除(会出现bug)
for (String s : list) {
if (s.equals("python")){
list.remove(s);
}
}
System.out.println(list);
//lambda表达式
list.forEach(s -> {
if (s.equals("python")){
list.remove(s);
}
});
迭代器解决方法,使用迭代器的remove方法
Iterator it = list.iterator();
while (it.hasNext()){
if(it.next().equals("python")){
//删除当前元素,且不会后移
it.remove();
}
}
for循环不会出现bug,但是会漏删
//for循环不会出现bug,但是会漏删
for(int i = 0 ;i < list.size()-1;i++){
String s = list.get(i);
if (s.equals("python")){
list.remove(s);
}
}
for循环的解决方法
1.从后面向前删
2.删除是,变量回退
for(int i = list.size()-1 ;i >=0;i--){
String s = list.get(i);
if (s.equals("python")){
list.remove(s);
}
}
System.out.println(list);
for(int i = 0 ;i < list.size()-1;i++){
String s = list.get(i);
if (s.equals("python")){
list.remove(s);
i--;
}
}
System.out.println(list);
3.泛型深入
泛型的好处:
- 统一数据类型
- 把运行时期的问题提前到编译期间,避免了强制类型转换可能出现的异常,因为编译阶段类型就能确定下来
- 泛型类的格式:修饰符 class 类名<泛型变量>{ }
- 例如: public class Test
{} - 此处泛型变量T可以随便写为任意标识符,比如常见的E、T、K、V等。
- 作用:编译阶段可以指定数据类型,类似于集合作用
泛型类的原理:
- 把出现泛型变量的地方全部替换成传输的真实数据类型
泛型方法:
- 泛型方法的格式:修饰符<泛型变量> 方法返回值 方法名称(形参列表){}
- 例如:public
void show(T t) - 作用:方法中可以使用泛型接收一切实际参数类型,方法更具备通用性
传入一个任何类型的数组,实现它的Arrays.toString方法
public static void ArrayToString(T[] arr){
if(arr != null){
StringBuilder s = new StringBuilder("[");
for (int i = 0; i < arr.length; i++) {
s.append(arr[i]).append(i == arr.length-1?"":", ");
}
s.append("]");
System.out.println(s.toString());
}else {
System.out.println(arr);
}
}
泛型方法的原理:
- 把出现泛型变量的地方全部替换成传输的真实数据类型
泛型接口:
- 使用了泛型定义的接口就是泛型接口
- 泛型接口的格式:修饰符 interface 接口名称<泛型变量>{}
- 例如:public interface Data
- 作用:泛型接口可以让实现类选择当前功能需要 *** 作的数据类型
例子:
public interface Data {
E add(E e);
int delete(int id);
E update(E e);
E findById(int id);
}
public class StudentData implements Data{
@Override
public Student add(Student student) {
return null;
}
@Override
public int delete(int id) {
return 0;
}
@Override
public Student update(Student student) {
return null;
}
@Override
public Student findById(int id) {
return null;
}
}
泛型接口的原理:
- 实现类可以在实现接口的时候传入自己 *** 作的数据类型,这样重写的方法都将是针对于该类型的 *** 作
泛型接口的作用:
- 泛型接口可以约束实现类,实现类可以在实现接口的时候传入自己 *** 作的数据类型,这样重写的方法都是针对于该类型的 *** 作
泛型通配符:?
- ?可以在“使用泛型”的时候代表一切类型
- E T K V是在定义的时候使用
泛型通配符应用:
注意:虽然Cat和Dog都继承自Animal,但是ArrayList
泛型上下限:
- ?extends Animal:?必须是Animal或者其子类 泛型上限
- ?super Animal: ?必须是Animal或者其父类 泛型下限
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)