Algorithm

题目

题目描述

98.验证二叉搜索树，给定一个二叉树，判断其是否是一个有效的二叉搜索树。假设一个二叉搜索树具有如下特征：

  • 节点的左子树只包含小于当前节点的树
  • 节点的右子树只包含大于当前节点的树
  • 所有左子树及右子树自身也必须是二叉搜索树

题目解答

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

import java.util.Stack;

public class ValidBST {

    public boolean isValidBST (TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        double inorder = -Double.MAX_VALUE;

        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (inorder >= root.val) {
                return false;
            }
            inorder = root.val;
            root = root.right;
        }
        return true;
    }
}

使用中序遍历(即左->根->右)来实现，从左至右进行比对，每次与上次保存的值进行对比，如果当前节点值比上次保存的值小，则可以判定此树不是二叉搜索树。时间复杂度为O(n)，空间复杂度为O(n)

Review

缓存更新的套路一篇关于缓存更新策略选择的文章，主要是讨论 并发情况下写缓存更新代码时，先删除缓存，再更新数据库，导致程序一直取老缓存内容 的错误行为，文章里面提供了四种缓存更新的Design Pattern:

Cache Aside

最常用的Design Pattern，具体的操作逻辑为：

缓存失效

应用程序先从Cache取数据，没有得到，则从数据库中获取，成功后，放到缓存中

缓存命中

应用程序从Cache中取数据，取到后返回

缓存更新

先所数据更新到数据库中，再使缓存失效

解决的问题

这种模式可以解决两个并发的写操作导致的脏数据

可能存在缓存的并发问题

两个并发操作，一个读，一个写，读操作时Cache未命中，去DB查询，此时写操作更新数据库，使Cache失效，然后读操作读到老数据写回缓存。此种情况发生概率非常小，主要是因为数据库的读操作比写操作快很多。

Read/Write Through Pattern

与Cache Aside中应用程序要维护两个存储不一样，Read/Write Through只关心一个存储存在，更新数据库的操作由缓存服务代理了。

Read Through

在查询操作中更新缓存，当缓存失效时，数据由缓存服务来加载，不需要应用来操作了，这样就对应用是透明的了。

Write Through

与Read Through相似，不过操作在更新数据时发生。当有数据更新时，如果没有命中缓存，直接更新数据库，然后返回。如果命中了缓存，则更新缓存，然后由缓存服务自己更新数据库（此为同步操作）。

Write Behind Caching Pattern

Write Behind又叫Write Back，类似于Linux操作系统的Page Cache算法。Write Back的操作就是更新数据时只更新缓存，不更新数据库，缓存会异步批量的更新数据库。

设计好处

直接操作内存，速度飞快。由于是异步操作，可以合并对同一数据的多次操作，性能提升可观。

带来的问题

数据不是强一致性，而且可能会丢失，关于强一致性可以参考最终一致性XA实现。其实软件设计就是在取舍之间平衡的。Write Back实现逻辑较复杂，它要追踪哪些数据被更新了，需要进行持久化操作。

更多的建议

  • 为缓存设置过期时间
  • 使用已经经历过考验的实现方式，也就是最佳实践
  • 要做好架构，要把老的技术给吃透了
  • 参考已有的经验，再决定是否要重新发明轮子

Tip

Maven Archetype一个Maven项目模板插件，可以根据指定项目的结构来生成模板工程。如果IDE中提供的Archetype不能满足需求，则可以进行自行编写，官方给的示例很全面，主要实现是不区分平台的，安装了maven即可操作。

Share

Bash教程 阮一峰大佬写的Bash教程，强烈推荐。学好Shell可以极大的提高生产率，教程覆盖了所有Shell的基础知识。学这东西实操最重要。