ARTS-第32周

发表于

ARTS （第32周）

Algorithm 算法

验证二叉搜索树

leetcode.98

https://leetcode-cn.com/problems/validate-binary-search-tree/

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:

输入:
    2
   / \
  1   3
输出: true

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/validate-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法：从跟节点验证到具体的每一个子节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
	 执行用时 :1 ms, 在所有 java 提交中击败了98.89%的用户
	 内存消耗 :36.2 MB, 在所有 java 提交中击败了95.66%的用户
	 */
	public boolean validBST(TreeNode root, Integer min, Integer max) {
		if (root == null) {
			return true;
		}
		// 先验证从跟到当前节点的大小关系
        //这里验证用max和min属性即可 不需要验证具体的父级属性
      	//因为合法情况下的max或者min就是父级的属性
		if (min != null && root.val <= min) {
			return false;
		}
		if (max != null && root.val >= max) {
			return false;
		}
		//验证左右节点
		if (!validBST(root.left, min, root.val)) {
			return false;
		}
		if (!validBST(root.right, root.val, max)) {
			return false;
		}
		//验证通过
		return true;
	}

在品论里看到的用户HaominYuan的一个答案

HaominYuan(https://leetcode-cn.com/u/kqysnjc/)

非常精巧的做法。有点像中序遍历，又有点像后序遍历。

在验证左节点的时候，只要判断左节点的值比当前节点小即可。

而验证右节点的时候，只要判断当前节点比右节点小即可。

这里利用的思路是last的值是在左节点验证成功后才改变值。

所以验证右节点的时候，last的值就是父节点的值。

（至于这里的last使用的是double类型，是因为这题的边界值的问题，这题的值里会出现INT_MIN(-2^31)，用double保证正确性）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
    double last = -Double.MAX_VALUE;
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (isValidBST(root.left)) {
            if (last < root.val) {
                last = root.val;
                return isValidBST(root.right);
            }
        }
        return false;
    }
}
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/validate-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

Review 英文文章

spring整合redis

https://spring.io/guides/gs/messaging-redis/

Tip 技巧

注解

1
2
3
4
5
6
7
8
9
10
11
12
//自带的编译期的注解

@Override//表示继承
@Deprecated//表示已过时
@SuppressWarnings//压制警告

//JAVA 中有以下几个『元注解』：

@Target：注解的作用目标
@Retention：注解的生命周期
@Documented：注解是否应当被包含在 JavaDoc 文档中
@Inherited：是否允许子类继承该注解

类加载器

1
2
3
4
5
6
7
8
9
10

JVM中提供了三种的ClassLoader：

1、Bootstrap classLoader:主要负责加载核心的类库(java.lang.*等)

2、ExtClassLoader：主要负责加载jre/lib/ext目录下的一些扩展的jar。

3、AppClassLoader：主要负责加载应用程序的主函数类

除此之外我们还可以自定义一些类加载器

JVM的双亲委派

在加载一个类的时候，首先会在ClassLoader中检查是否加载，如果有那就无需再加载了。如果没有，那么会拿到父加载器，然后调用父加载器的loadClass方法，直到找到，但如果父加载器找不到就会交给子级去加载，如果一直到最底层的子级都找不到，就会触发ClassNotFoundException。

Share 分享

https://blog.csdn.net/yapengliu/article/details/80191699
Bootstrap Table API 中文版 说明文档