给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，1
2
3
4
5 3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
1 | // 主体是个递归的应用 |
其实对于树这类题，一般是以递归形式比较方便，只是要注意退出条件
终于回忆起来了，年纪大了写这种东西真的要立马写，不然很容易想不起来，那天应该是 9 月 12 日，也就是上周六，因为我爸也去了，而且娘亲（丈母娘，LD 这么叫，我也就随了她这么叫，当然是背后，当面就叫妈）也在那，早上一到那二爹就给我爸指挥了活，要挖一条院子的出水道，自己想出来的词，因为觉得下水道是竖的，在那稍稍帮了一会会忙，然后我还是比较惯例的跟着 LD 还有娘亲去住的家里，主要是老丈人可能也不太想让我干太累的活，因为上次已经差不多把三楼都整理干净了，然后就是二楼了，二楼说实话我也帮不上什么忙，主要是衣服被子什么的，正好是有张以前小孩子睡过的那种摇篮床，看上去虽然有一些破损，整体还是不错的，所以打算拿过去，我就负责把它拆掉了，比较简单的是只要拧螺丝就行了，但是其实是用了好多好多工具才搞定的，一开始只要螺丝刀就行了，但是因为年代久了，后面的螺帽也有点锈住或者本身就会串着会一起动，所以拿来了个扳手，大部分的其实都被这两个工具给搞定了，但是后期大概还剩下四分之一的时候，有一颗完全锈住，并且螺纹跟之前那些都不一样，但是这个已经是最大的螺丝刀了，也没办法换个大的了，所以又去找来个一字的，因为十字的不是也可以用一字的拧嘛，结果可能是我买的工具箱里的一字螺丝刀太新了，口子那很锋利，直接把螺丝花纹给划掉了，大的小的都划掉，然后真的变成凹进去一个圆柱体了，然后就想能不能隔一层布去拧，然而因为的确是已经变成圆柱体了，布也不太给力，不放弃的我又去找来了个老虎钳，妄图把划掉的螺丝用老虎钳钳住，另一端用扳手拧开螺帽，但是这个螺丝跟螺帽真的是生锈的太严重了，外加上钳不太牢，完全是两边一起转，实在是没办法了，在征得同意之后，直接掰断了，火死了，一颗螺丝折腾得比我拆一张床还久，那天因为早上去的也比较晚了，然后就快吃午饭了，正好想着带一点东西过去，就把一些脸盆，泡脚桶啥的拿过去了，先是去吃了饭，还是在那家快餐店，菜的口味还是依然不错，就是人比较多，我爸旁边都是素菜，都没怎么吃远一点的荤菜，下次要早点去，把荤菜放我爸旁边😄（PS：他们家饭还是依然尴尬，需要等），吃完就开到在修的房子那把东西拿了出来，我爸已经动作很快的打了一小半的地沟了，说实话那玩意真的是很重，我之前把它从三楼拿下来，就觉得这个太重了，这次还要用起来，感觉我的手会分分钟废掉，不过一开始我还是跟着LD去了住的家里，惯例睡了午觉，那天睡得比较踏实，竟然睡了一个小时，醒了想了下，其实LD她们收拾也用不上我（没啥力气活），我还是去帮我爸他们，跟LD说了下就去了在修的老房子那，两位老爹在一起钻地，看着就很累，我连忙上去想换一会他们，因为刚好是钻到混凝土地线，特别难，力道不够就会滑开，用蛮力就是钻进去拔不出来，原理是因为本身浇的时候就是很紧实的，需要边钻边动，那家伙实在是太重了，真的是汗如雨下，基本是三个人轮流来，我是个添乱的，经常卡住，然后把地线，其实就是一条混凝土横梁，里面还有14跟18的钢筋，需要割断，这个割断也是很有技巧，钢筋本身在里面是受到挤压的，直接用切割的，到快断掉的时候就会崩一下，非常危险，还是老丈人比较有经验，要留一点点，然后直接用榔头敲断就好了，本来以为这个是最难的了，结果下面是一块非常大的青基石，而且也是石头跟石头挤一块，边上一点点打钻有点杯水车薪，后来是用那种螺旋的钻，钻四个洞，相对位置大概是个长方形，这样子把中间这个长方形钻出来就比较容易地能拿出来了，后面的也容易搞出来了，后面的其实难度不是特别大了，主要是地沟打好之后得看看高低是不是符合要求的，不能本来是往外排水的反而外面高，这个怎么看就又很有技巧了，一般在地上的只要侧着看一下就好了，考究点就用下水平尺，但是在地下的，不用水平尺，其实可以借助于地沟里正要放进去的水管，放点水进去，看水往哪流就行了，铺好水管后，就剩填埋的活了，不是太麻烦了，那天真的是累到了，打那个混凝土的时候我真的是把我整个人压上去了，不过也挺爽的，有点把平时无处发泄的蛮力发泄出去了。
又 roll 到了一个以前做过的题，不过现在用 Java 也来写一下，是 easy 级别的，所以就简单说下
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
就是给了两个链表，用来表示两个非负的整数，在链表中倒序放着，每个节点包含一位的数字，把他们加起来以后也按照原来的链表结构输出
1 | Input: l1 = [2,4,3], l2 = [5,6,4] |
1 | Input: l1 = [0], l2 = [0] |
1 | Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] |
1 | public ListNode addTwoNumbers(ListNode l1, ListNode l2) { |
这里唯二需要注意的就是两个点，一个是循环条件需要包含进位值还存在的情况，还有一个是最后一个节点，如果是空的了，就不要在 new 一个出来了，写的比较挫
Java 真的是任何一个中间件，比较常用的那种，都有很多内容值得深挖，比如这个缓存，慢慢有过一些感悟，比如如何提升性能，缓存无疑是一大重要手段，最底层开始 CPU 就有缓存，而且又小又贵，再往上一点内存一般作为硬盘存储在运行时的存储，一般在代码里也会用内存作为一些本地缓存，譬如数据库，像 mysql 这种也是有innodb_buffer_pool来提升查询效率，本质上理解就是用更快的存储作为相对慢存储的缓存，减少查询直接访问较慢的存储，并且这个都是相对的，比起 cpu 的缓存，那内存也是渣，但是与普通机械硬盘相比，那也是两个次元的水平。
闲扯这么多来说说 mybatis 的缓存，mybatis 一般作为一个轻量级的 orm 使用，相对应的就是比较重量级的 hibernate，不过不在这次讨论范围，上一次是主要讲了 mybatis 在解析 sql 过程中，对于两种占位符的不同替换实现策略，这次主要聊下 mybatis 的缓存，前面其实得了解下前置的东西，比如 sqlsession，先当做我们知道 sqlsession 是个什么玩意，可能或多或少的知道 mybatis 是有两级缓存，
第一级的缓存是在 BaseExecutor 中的 PerpetualCache，它是个最基本的缓存实现类，使用了 HashMap 实现缓存功能，代码其实没几十行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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65public class PerpetualCache implements Cache {
private final String id;
private final Map<Object, Object> cache = new HashMap<>();
public PerpetualCache(String id) {
this.id = id;
}
@Override
public String getId() {
return id;
}
@Override
public int getSize() {
return cache.size();
}
@Override
public void putObject(Object key, Object value) {
cache.put(key, value);
}
@Override
public Object getObject(Object key) {
return cache.get(key);
}
@Override
public Object removeObject(Object key) {
return cache.remove(key);
}
@Override
public void clear() {
cache.clear();
}
@Override
public boolean equals(Object o) {
if (getId() == null) {
throw new CacheException("Cache instances require an ID.");
}
if (this == o) {
return true;
}
if (!(o instanceof Cache)) {
return false;
}
Cache otherCache = (Cache) o;
return getId().equals(otherCache.getId());
}
@Override
public int hashCode() {
if (getId() == null) {
throw new CacheException("Cache instances require an ID.");
}
return getId().hashCode();
}
}
可以看一下BaseExecutor 的构造函数1
2
3
4
5
6
7
8
9protected BaseExecutor(Configuration configuration, Transaction transaction) {
this.transaction = transaction;
this.deferredLoads = new ConcurrentLinkedQueue<>();
this.localCache = new PerpetualCache("LocalCache");
this.localOutputParameterCache = new PerpetualCache("LocalOutputParameterCache");
this.closed = false;
this.configuration = configuration;
this.wrapper = this;
}
就是把 PerpetualCache 作为 localCache，然后怎么使用我看简单看一下，BaseExecutor 的查询首先是调用这个函数1
2
3
4
5
6@Override
public <E> List<E> query(MappedStatement ms, Object parameter, RowBounds rowBounds, ResultHandler resultHandler) throws SQLException {
BoundSql boundSql = ms.getBoundSql(parameter);
CacheKey key = createCacheKey(ms, parameter, rowBounds, boundSql);
return query(ms, parameter, rowBounds, resultHandler, key, boundSql);
}
可以看到首先是调用了 createCacheKey 方法，这个方法呢，先不看怎么写的，如果我们自己要实现这么个缓存，首先这个缓存 key 的设计也是个问题，如果是以表名加主键作为 key，那么分页查询，或者没有主键的时候就不行，来看看 mybatis 是怎么设计的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
28
29
30
31
32
33
34
35
36
37@Override
public CacheKey createCacheKey(MappedStatement ms, Object parameterObject, RowBounds rowBounds, BoundSql boundSql) {
if (closed) {
throw new ExecutorException("Executor was closed.");
}
CacheKey cacheKey = new CacheKey();
cacheKey.update(ms.getId());
cacheKey.update(rowBounds.getOffset());
cacheKey.update(rowBounds.getLimit());
cacheKey.update(boundSql.getSql());
List<ParameterMapping> parameterMappings = boundSql.getParameterMappings();
TypeHandlerRegistry typeHandlerRegistry = ms.getConfiguration().getTypeHandlerRegistry();
// mimic DefaultParameterHandler logic
for (ParameterMapping parameterMapping : parameterMappings) {
if (parameterMapping.getMode() != ParameterMode.OUT) {
Object value;
String propertyName = parameterMapping.getProperty();
if (boundSql.hasAdditionalParameter(propertyName)) {
value = boundSql.getAdditionalParameter(propertyName);
} else if (parameterObject == null) {
value = null;
} else if (typeHandlerRegistry.hasTypeHandler(parameterObject.getClass())) {
value = parameterObject;
} else {
MetaObject metaObject = configuration.newMetaObject(parameterObject);
value = metaObject.getValue(propertyName);
}
cacheKey.update(value);
}
}
if (configuration.getEnvironment() != null) {
// issue #176
cacheKey.update(configuration.getEnvironment().getId());
}
return cacheKey;
}
首先需要 id，这个 id 是 mapper 里方法的 id， 然后是偏移量跟返回行数，再就是 sql，然后是参数，基本上是会有影响的都加进去了，在这个 update 里面1
2
3
4
5
6
7
8
9
10
11public void update(Object object) {
int baseHashCode = object == null ? 1 : ArrayUtil.hashCode(object);
count++;
checksum += baseHashCode;
baseHashCode *= count;
hashcode = multiplier * hashcode + baseHashCode;
updateList.add(object);
}
其实是一个 hash 转换，具体不纠结，就是提高特异性，然后回来就是继续调用 query1
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
28
29
30
31
32
33
34@Override
public <E> List<E> query(MappedStatement ms, Object parameter, RowBounds rowBounds, ResultHandler resultHandler, CacheKey key, BoundSql boundSql) throws SQLException {
ErrorContext.instance().resource(ms.getResource()).activity("executing a query").object(ms.getId());
if (closed) {
throw new ExecutorException("Executor was closed.");
}
if (queryStack == 0 && ms.isFlushCacheRequired()) {
clearLocalCache();
}
List<E> list;
try {
queryStack++;
list = resultHandler == null ? (List<E>) localCache.getObject(key) : null;
if (list != null) {
handleLocallyCachedOutputParameters(ms, key, parameter, boundSql);
} else {
list = queryFromDatabase(ms, parameter, rowBounds, resultHandler, key, boundSql);
}
} finally {
queryStack--;
}
if (queryStack == 0) {
for (DeferredLoad deferredLoad : deferredLoads) {
deferredLoad.load();
}
// issue #601
deferredLoads.clear();
if (configuration.getLocalCacheScope() == LocalCacheScope.STATEMENT) {
// issue #482
clearLocalCache();
}
}
return list;
}
可以看到是先从 localCache 里取，取不到再 queryFromDatabase，其实比较简单，这是一级缓存，考虑到 sqlsession 跟 BaseExecutor 的关系，其实是随着 sqlsession 来保证这个缓存不会出现脏数据幻读的情况，当然事务相关的后面可能再单独聊。
其实这个一级二级顺序有点反过来，其实查询的是先走的二级缓存，当然二级的需要配置开启，默认不开，
需要通过1
<setting name="cacheEnabled" value="true"/>
来开启，然后我们的查询就会走到1
2
3
4public class CachingExecutor implements Executor {
private final Executor delegate;
private final TransactionalCacheManager tcm = new TransactionalCacheManager();
这个 Executor 中，这里我放了类里面的元素，发现没有一个 Cache 类，这就是一个特点了，往下看查询过程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@Override
public <E> List<E> query(MappedStatement ms, Object parameterObject, RowBounds rowBounds, ResultHandler resultHandler) throws SQLException {
BoundSql boundSql = ms.getBoundSql(parameterObject);
CacheKey key = createCacheKey(ms, parameterObject, rowBounds, boundSql);
return query(ms, parameterObject, rowBounds, resultHandler, key, boundSql);
}
@Override
public <E> List<E> query(MappedStatement ms, Object parameterObject, RowBounds rowBounds, ResultHandler resultHandler, CacheKey key, BoundSql boundSql)
throws SQLException {
Cache cache = ms.getCache();
if (cache != null) {
flushCacheIfRequired(ms);
if (ms.isUseCache() && resultHandler == null) {
ensureNoOutParams(ms, boundSql);
@SuppressWarnings("unchecked")
List<E> list = (List<E>) tcm.getObject(cache, key);
if (list == null) {
list = delegate.query(ms, parameterObject, rowBounds, resultHandler, key, boundSql);
tcm.putObject(cache, key, list); // issue #578 and #116
}
return list;
}
}
return delegate.query(ms, parameterObject, rowBounds, resultHandler, key, boundSql);
}
看到没，其实缓存是从 tcm 这个成员变量里取，而这个是什么呢，事务性缓存(直译下)，因为这个其实是用 MappedStatement 里的 Cache 作为key 从 tcm 的 map 取出来的1
2
3public class TransactionalCacheManager {
private final Map<Cache, TransactionalCache> transactionalCaches = new HashMap<>();
MappedStatement是被全局使用的，所以其实二级缓存是跟着 mapper 的 namespace 走的，可以被多个 CachingExecutor 获取到，就会出现线程安全问题，线程安全问题可以用SynchronizedCache来解决，就是加锁，但是对于事务中的脏读，使用了TransactionalCache来解决这个问题，1
2
3
4
5
6
7
8public class TransactionalCache implements Cache {
private static final Log log = LogFactory.getLog(TransactionalCache.class);
private final Cache delegate;
private boolean clearOnCommit;
private final Map<Object, Object> entriesToAddOnCommit;
private final Set<Object> entriesMissedInCache;
在事务还没提交的时候，会把中间状态的数据放在 entriesToAddOnCommit 中，只有在提交后会放进共享缓存中，1
2
3
4
5
6
7public void commit() {
if (clearOnCommit) {
delegate.clear();
}
flushPendingEntries();
reset();
}
第四周去的时候让我们去了现在在住的房子里，去三楼整理东西了，蛮多的东西需要收拾整理，有些需要丢一下，以前往往是把不太要用的东西就放三楼了，但是后面就不会再去收拾整理，LD 跟丈母娘负责收拾，我不太知道哪些还要的，哪些不要了，而且本来也不擅长这种收拾🤦♂️，然后就变成她们收拾出来废纸箱，我负责拆掉，压平，这时候终于觉得体重还算是有点作用，总体来说这个事情我其实也不擅长，不擅长的主要是捆起来，可能我总是小题大做，因为纸箱大小不一，如果不做一下分类，然后把大的折小一些的话，直接绑起来，容易拎起来就散掉了，而且一些鞋盒子这种小件的纸盒会比较薄，冰箱这种大件的比较厚，厚的比较不容易变形，需要大力踩踏，而且扎的时候需要用体重压住捆实了之后那样子才是真的捆实的，不然待会又是松松垮垮容易滑出来散架，因为压住了捆好后，下来了之后箱子就会弹开了把绳子崩紧实，感觉又是掌握到生活小技巧了😃，我这里其实比较单调无聊，然后 LD 那可以说非常厉害了，一共理出来 11 把旧电扇，还有好多没用过全新的不锈钢脸盆大大小小的，感觉比店里在卖的还多，还有是有比较多小时候的东西，特别多小时候的衣服，其实这种对我来说最难了，可能需要读一下断舍离，蛮多东西都舍不得扔，但是其实是没啥用了，然后还占地方，这天应该算是比较轻松的一天了，上午主要是把收拾出来要的和不要的搬下楼，然后下午要去把纸板给卖掉。中午还是去小快餐店吃的，在住的家里理东西还有个好处就是中午吃完饭可以小憩一下，因为我个人是非常依赖午休的，不然下午完全没精神，而且心态也会比较烦躁，一方面是客观的的确比较疲惫，另一方面应该主观心理作用也有点影响，就像上班的时候也是觉得不午睡就会很难受，心理作用也有一点，不过总之能睡还是睡一会，真的没办法就心态好点，吃完午饭之后我们就推着小平板车去收废品的地方卖掉了上午我收拾捆起来的纸板，好像卖了一百多，都是直接过地磅了，不用一捆一捆地称，不过有个小插曲，那里另外一个大爷在倒他的三轮车的时候撞了我一下，还好车速慢，屁股上肉垫后，接下来就比较麻烦了，是LD 她们两姐妹从小到大的书，也要去卖掉，小平板车就载不下了，而且着实也不太好推，轮子不太平，导致推着很累，书有好多箱，本来是想去亲戚家借电动三轮车，因为不会开摩托的那种，摩托的那种 LD 邻居家就有，可是到了那发现那个也是很大，而且刹车是用脚踩的那种，俺爹不太放心，就说第二天周日他有空会帮忙去载了卖掉的，然后比较搞笑的来了，丈母娘看错了时间，以为已经快五点了，就让我们顺便在车里带点东西去在修的房子，放到那边三楼去，到了那还跟老丈人说已经这么迟了要赶紧去菜场买菜了，结果我们回来以后才发现看错了一个小时🤦♂️。
前面可以没提，前三周去的我们一般就周六去一天，然后周日因为要早点回杭州，而且可能想让我们周日能休息下，但是这周就因为周日的时候我爸要去帮忙载书，然后 LD 姐姐也会过来收拾东西，我们周日就又去整理收拾了，周日由于俺爹去的很早，我过去的时候书已经木有了，主要是去收拾东西了，把一些有用没用的继续整理，基本上三楼的就处理完毕了，舒了一大口气，毕竟让丈母娘一个人收拾实在是太累了，但是要扔掉的衣服比较棘手，附近知道的青蛙回收桶被推倒了，其他地方也不知道哪里有，我们就先载了一些东西去在修的房子那，然后去找青蛙桶，结果一个小区可以进，但是已经满了，另一个不让进，后来只能让 LD 姐姐带去她们小区扔了，塞了满满一车。因为要赶回杭州的车就没有等我爸一起回来，他还在那帮忙搞卫生间的墙缝。
虽然这两天不太热，活也不算很吃力，不过我这个体重和易出汗的体质，还是让短袖不知道湿透了多少次，灌了好多水和冰红茶（下午能提提神），回来周一早上称体重也比较喜人，差一点就达到阶段目标，可以想想去哪里吃之前想好的烤肉跟火锅了（估计吃完立马回到解放前）。