蒙娜丽莎法师

be better

AVL,红黑树学习

二叉树

定义

  • 二叉树由节点的有限集合构成
  • 这个有限集合或者为空集
  • 或者为由一个根节点(root)及两棵互不相交、分别称为这个根的左子树和右子树的二叉树组成的集合

在 java 中用代码定义为:

1
2
3
4
5
6
7
8
class TreeNode {
Object val;
TreeNode leftNode;
TreeNode rightNode;

...

}

性质

  1. 在二叉树中,第 i 层上最多有2^i^ 个节点(i>=0)
  2. 深度为 k 的二叉树至多有2^k+1^-1个节点(k>=0)
  3. 有 n 个节点的完全二叉树的高度为 log2(n+1)

它主要有五种基本形态:

二叉树的五种基本形态

满二叉树

定义:除最后一层无任何子节点外,每一层上的所有节点都有两个子节点的二叉树。

大体的意思就是:一颗二叉树的节点要么是叶子节点(也就是最后一层),要么它就要有两个子节点。如果这个二叉树的层数为 k,且节点总数是(2^k^-1),则它就是满二叉树。

满二叉树

完全二叉树

定义:设二叉树的深度为 k,除第 k 层外,其他各层(1~(k-1)层)的节点都都达到最大值,其第 k 层所有的节点都连续集中在最左边,这样的树就是完全二叉树

完全二叉树

这些是二叉树的一些基本定义以及变形,它对于数据的存储并没有要求,只是要求了结构。所以对于实际应用中还存在很多的不足,比如对于一个 n 个节点的树,判断一个节点是不是在树里面,它的复杂度还是 o(n)。所以我们下面介绍几种对于存储有要求的树。

Java注解

注解,这个经常在开发中使用到的东西,它的使用语法是怎么样的?如何去自定义一个注解呢?

什么是注解

我们在日常开发中,比如 java 中的@Override,在 springboot 中用到的@SpringBootApplication等一系列标注在类或者方法上的注解。我们添加上注解后会有对应的事件处理,比如我们的@Override注解标明这个方法是重写了父类或者接口的方法,当参数不一致、返回类型不一致等不符合重写的要求时,编译器会报错。类似的@SpringBootApplication也是标明这个项目的一个 springboot 项目,默认会启动一个 tomcat 容器等。

注解是从 jdk5 开始引入的新特性。

注解的语法

1
public @interface FirstAnnotation {}

通过@interface即可声明一个注解。

K个一组翻转链表

题目描述

给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。
k 是一个正整数,它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。
示例 :
给定这个链表:1->2->3->4->5
当 k = 2 时,应当返回: 2->1->4->3->5
当 k = 3 时,应当返回: 3->2->1->4->5
说明 :
你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换

解题思路

首先根据 k,分隔每一组。将这一组反转,将下面的一组递归调用函数,然后将这一组的最后一个节点(就是参数中的头结点)与下一组反转后的头结点相连接。

SpringBoot使用@ControllerAdvice处理异常

背景

我们知道,当前端请求的后端程序抛出异常时,此时的 http 状态码变成了 500,并有一大串错误信息。今天要做的是整合后台返回信息,不管后台程序有异常,都能返回一个统一格式的信息,前端根据里面的信息来判断是否请求失败。

定义一下正常返回的信息如下:

1
2
3
4
5
6
7
{
code:1,
msg:"请求成功", //或其他自定义信息
data:{
//这里存储这个接口的返回信息
}
}

错误的信息如下:

1
2
3
4
5
{
code:-1, //可以根据不同的情况返回不同的状态码
msg:"请求失败", //或其他自定义信息
data:{}
}

反转一个单链表-LeetCode206

题目描述

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题?

解题思路

将单链表进行反转,也就是将顺序进行调换,每次操作上一个元素与当前元素,对于头元素,上一个元素则为 null。

先将当前元素的下一个元素临时保存,然后将当前元素的下一个元素设置为上一个元素。

下一个循环中,当前元素作为上一个元素,下一个元素作为当前元素。

当当前元素为空,也就是到头了,结束。

用队列实现栈-LeetCode225

题目描述

使用队列实现栈的下列操作:
push(x) – 元素 x 入栈
pop() – 移除栈顶元素
top() – 获取栈顶元素
empty() – 返回栈是否为空
注意:

你只能使用队列的基本操作– 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
你所使用的语言也许不支持队列。 你可以使用 list 或者 deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。
你可以假设所有操作都是有效的(例如, 对一个空的栈不会调用 pop 或者 top 操作)。

解题思路

  1. 使用两个队列

    将元素添加到第一个队列中。

    在获取元素时,将第一个队列中除了最后一个元素都添加到第二个队列中,剩下的这个就是要返回的元素。

    将两个队列进行交换,这样在添加元素时都能放到第一个队列中。

    使用一个变量来存储最后一个元素,这样在调用 top 方法时直接返回这个变量即可。

    用双队列实现栈

  2. 使用一个队列

    添加元素时添加到队列中,然后将队列中的元素除了最后一个再重新放入一遍

    在获取元素和查看元素时都拿第一个即可

    用一个队列实现栈

用栈实现队列-LeetCode232

题目描述

使用栈实现队列的下列操作:

push(x) – 将一个元素放入队列的尾部。
pop() – 从队列首部移除元素。
peek() – 返回队列首部的元素。
empty() – 返回队列是否为空。
示例:

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false
说明:

你只能使用标准的栈操作 – 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端队列)来模拟一个栈,只要是标准的栈操作即可。
假设所有操作都是有效的 (例如,一个空的队列不会调用 pop 或者 peek 操作)

解题思路

栈(先进后出)来实现队列(先进先出)。

可以用两个栈来实现,第一个栈存储,当进行 peek 或 pop 操作时,将第一个栈内元素按照先进后出的原则拿出来放到第二个栈里面。这时第二个栈里面在取就是我们总的第一个元素。

用栈实现队列

StringBuilder为什么线程不安全?

在脉脉上看到一篇文章,StringBulider 为什么线程不安全,然后想了一下,确实不知道。

之前问string 相关问题,只了解了 string 不可变,stringbuffer 线程安全,stringbuilder 线程不安全。但却没有搞清楚为什么是不安全的,今天就去看了一下 stringbuilder 的源码,来了解一下原因。

首先来测试一下多线程下的不安全问题:

1
2
3
4
5
6
7
8
9
10
public static void main(String[] args) {
StringBuilder stringBuilder = new StringBuilder();

for (int i = 0; i < 100000; i++) {
new Thread(() -> stringBuilder.append("a")).start();
}

System.out.println(stringBuilder.length());

}

这个方法最终的理想结果应该是 100000,但是当我们多运行几次,发现他的结果出错了!结果变成了99999或者更小的数值。有时候甚至还抛出了数组越界异常(概率极小)。

TreeMap源码学习

之前看过了HashMap,LinkedHashMap的源码,这次来看一下TreeMap的源码。

从这个名字就能看出,TreeMap底层使用的是树来进行存储的。

变量

1
2
3
4
5
6
7
8
9
//比较器,用于左右子树的判断。
//正常情况下,左子树为 1,父节点为 2,右子树为 3。如果比较器设置 3<1<2。则左子树为3,父节点为 1,右子树为 2。
private final Comparator<? super K> comparator;
//根节点
private transient Entry<K,V> root;
//容量
private transient int size = 0;
//修改的次数,在迭代和序列化时用到
private transient int modCount = 0;

看一下 root 节点的数据结构:

1
2
3
4
5
6
7
8
9
10
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;
boolean color = BLACK;

...
}

由于有一个color=BLACK属性,所以底层数据结构应该是红黑树

链表

链表

与数组一样也是一种线性数据结构

查找的速度:O(n),要查找一个元素需要从头结点进行遍历

链表

插入的速度:O(1),删除的速度:O(1)

删除和插入的情况多,或者不知道元素的数量时应该要考虑使用链表的数据结构。

  1. 单向链表

    每个结点有一个next属性,指向下一个节点

  2. 双向链表

    每个结点除了有next属性指向下一个节点外,还有一个pre属性指向上一个节点

  3. 当最后一个元素的 next 结点指向第一个结点,就构成了一个环。

习题

Proudly powered by Hexo and Theme by Hacker
© 2020 Liu NaiJie