Nicksxs's Blog

What hurts more, the pain of hard work or the pain of regret?

又 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.
就是给了两个链表,用来表示两个非负的整数,在链表中倒序放着,每个节点包含一位的数字,把他们加起来以后也按照原来的链表结构输出

样例

example 1

1
2
3
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

example 2

1
2
Input: l1 = [0], l2 = [0]
Output: [0]

example 3

1
2
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

题解

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
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode root = new ListNode();
if (l1 == null && l2 == null) {
return root;
}
ListNode tail = root;
int entered = 0;
// 这个条件加了 entered,就是还有进位的数
while (l1 != null || l2 != null || entered != 0) {
int temp = entered;
if (l1 != null) {
temp += l1.val;
l1 = l1.next;
}
if (l2 != null) {
temp += l2.val;
l2 = l2.next;
}
entered = (temp - temp % 10) / 10;
tail.val = temp % 10;
// 循环内部的控制是为了排除最后的空节点
if (l1 != null || l2 != null || entered != 0) {
tail.next = new ListNode();
tail = tail.next;
}
}
// tail = null;
return root;
}

这里唯二需要注意的就是两个点,一个是循环条件需要包含进位值还存在的情况,还有一个是最后一个节点,如果是空的了,就不要在 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
65
public 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
9
protected 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
11
public 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 转换,具体不纠结,就是提高特异性,然后回来就是继续调用 query

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
@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
4
public 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
3
public class TransactionalCacheManager {

private final Map<Cache, TransactionalCache> transactionalCaches = new HashMap<>();

MappedStatement是被全局使用的,所以其实二级缓存是跟着 mapper 的 namespace 走的,可以被多个 CachingExecutor 获取到,就会出现线程安全问题,线程安全问题可以用SynchronizedCache来解决,就是加锁,但是对于事务中的脏读,使用了TransactionalCache来解决这个问题,

1
2
3
4
5
6
7
8
public 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
7
public void commit() {
if (clearOnCommit) {
delegate.clear();
}
flushPendingEntries();
reset();
}

小工记四

第四周去的时候让我们去了现在在住的房子里,去三楼整理东西了,蛮多的东西需要收拾整理,有些需要丢一下,以前往往是把不太要用的东西就放三楼了,但是后面就不会再去收拾整理,LD 跟丈母娘负责收拾,我不太知道哪些还要的,哪些不要了,而且本来也不擅长这种收拾🤦‍♂️,然后就变成她们收拾出来废纸箱,我负责拆掉,压平,这时候终于觉得体重还算是有点作用,总体来说这个事情我其实也不擅长,不擅长的主要是捆起来,可能我总是小题大做,因为纸箱大小不一,如果不做一下分类,然后把大的折小一些的话,直接绑起来,容易拎起来就散掉了,而且一些鞋盒子这种小件的纸盒会比较薄,冰箱这种大件的比较厚,厚的比较不容易变形,需要大力踩踏,而且扎的时候需要用体重压住捆实了之后那样子才是真的捆实的,不然待会又是松松垮垮容易滑出来散架,因为压住了捆好后,下来了之后箱子就会弹开了把绳子崩紧实,感觉又是掌握到生活小技巧了😃,我这里其实比较单调无聊,然后 LD 那可以说非常厉害了,一共理出来 11 把旧电扇,还有好多没用过全新的不锈钢脸盆大大小小的,感觉比店里在卖的还多,还有是有比较多小时候的东西,特别多小时候的衣服,其实这种对我来说最难了,可能需要读一下断舍离,蛮多东西都舍不得扔,但是其实是没啥用了,然后还占地方,这天应该算是比较轻松的一天了,上午主要是把收拾出来要的和不要的搬下楼,然后下午要去把纸板给卖掉。中午还是去小快餐店吃的,在住的家里理东西还有个好处就是中午吃完饭可以小憩一下,因为我个人是非常依赖午休的,不然下午完全没精神,而且心态也会比较烦躁,一方面是客观的的确比较疲惫,另一方面应该主观心理作用也有点影响,就像上班的时候也是觉得不午睡就会很难受,心理作用也有一点,不过总之能睡还是睡一会,真的没办法就心态好点,吃完午饭之后我们就推着小平板车去收废品的地方卖掉了上午我收拾捆起来的纸板,好像卖了一百多,都是直接过地磅了,不用一捆一捆地称,不过有个小插曲,那里另外一个大爷在倒他的三轮车的时候撞了我一下,还好车速慢,屁股上肉垫后,接下来就比较麻烦了,是LD 她们两姐妹从小到大的书,也要去卖掉,小平板车就载不下了,而且着实也不太好推,轮子不太平,导致推着很累,书有好多箱,本来是想去亲戚家借电动三轮车,因为不会开摩托的那种,摩托的那种 LD 邻居家就有,可是到了那发现那个也是很大,而且刹车是用脚踩的那种,俺爹不太放心,就说第二天周日他有空会帮忙去载了卖掉的,然后比较搞笑的来了,丈母娘看错了时间,以为已经快五点了,就让我们顺便在车里带点东西去在修的房子,放到那边三楼去,到了那还跟老丈人说已经这么迟了要赶紧去菜场买菜了,结果我们回来以后才发现看错了一个小时🤦‍♂️。
前面可以没提,前三周去的我们一般就周六去一天,然后周日因为要早点回杭州,而且可能想让我们周日能休息下,但是这周就因为周日的时候我爸要去帮忙载书,然后 LD 姐姐也会过来收拾东西,我们周日就又去整理收拾了,周日由于俺爹去的很早,我过去的时候书已经木有了,主要是去收拾东西了,把一些有用没用的继续整理,基本上三楼的就处理完毕了,舒了一大口气,毕竟让丈母娘一个人收拾实在是太累了,但是要扔掉的衣服比较棘手,附近知道的青蛙回收桶被推倒了,其他地方也不知道哪里有,我们就先载了一些东西去在修的房子那,然后去找青蛙桶,结果一个小区可以进,但是已经满了,另一个不让进,后来只能让 LD 姐姐带去她们小区扔了,塞了满满一车。因为要赶回杭州的车就没有等我爸一起回来,他还在那帮忙搞卫生间的墙缝。
虽然这两天不太热,活也不算很吃力,不过我这个体重和易出汗的体质,还是让短袖不知道湿透了多少次,灌了好多水和冰红茶(下午能提提神),回来周一早上称体重也比较喜人,差一点就达到阶段目标,可以想想去哪里吃之前想好的烤肉跟火锅了(估计吃完立马回到解放前)。

又做了个题,看记录是以前用 C++写过的,现在捋一捋思路,用 Java 再写了一下,思路还是比较清晰的,但是边界细节处理得比较差

简要介绍

Given a string s, find the length of the longest substring without repeating characters.

样例

Example 1:

1
2
3
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

1
2
3
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

1
2
3
4
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Example 4:

1
2
Input: s = ""
Output: 0

就是一个最长不重复的字符串长度,因为也是中等难度的题,不太需要特别复杂的思考,最基本的就是O(N*N)两重循环,不过显然不太好,万一超时间,还有一种就是线性复杂度的了,这个就是需要搞定一个思路,比如字符串时 abcdefgaqwrty,比如遍历到第二个a的时候其实不用再从头去遍历了,只要把前面那个a给排除掉,继续往下算就好了

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
class Solution {
Map<String, Integer> counter = new HashMap<>();
public int lengthOfLongestSubstring(String s) {
int length = s.length();
// 当前的长度
int subStringLength = 0;
// 最长的长度
int maxSubStringLength = 0;
// 考虑到重复的位置已经被跳过的情况,即已经在当前长度的字符串范围之前的重复字符不需要回溯
int lastDuplicatePos = -1;
for (int i = 0; i < length; i++) {
// 使用 map 存储字符和上一次出现的位置,如果存在并且大于上一次重复位置
if (counter.get(String.valueOf(s.charAt(i))) != null && counter.get(String.valueOf(s.charAt(i))) > lastDuplicatePos) {
// 记录重复位置
lastDuplicatePos = counter.get(String.valueOf(s.charAt(i)));
// 重置不重复子串的长度,减去重复起点
subStringLength = i - counter.get(String.valueOf(s.charAt(i))) - 1;
// 替换当前位置
counter.replace(String.valueOf(s.charAt(i)), i);
} else {
// 如果不存在就直接 put
counter.put(String.valueOf(s.charAt(i)), i);
}
// 长度累加
subStringLength++;
if (subStringLength > maxSubStringLength) {
// 简单替换
maxSubStringLength = subStringLength;
}
}
return maxSubStringLength;
}
}

注释应该写的比较清楚了。

小工记三

前面这两周周末也都去老丈人家帮忙了,上上周周六先是去了那个在装修的旧房子那,把三楼收拾了下,因为要搬进来住,来不及等二楼装修好,就要把三楼里的东西都整理干净,这个活感觉是比较 easy,原来是就准备把三楼当放东西仓储的地方了,我们乡下大部分三层楼都是这么用的,这次也是没办法,之前搬进来的木头什么的都搬出去,主要是这上面灰尘太多,后面清理鼻孔的时候都是黑色的了,把东西都搬出去以后主要是地还是很脏,就扫了地拖了地,因为是水泥地,灰尘又太多了,拖起来都是会灰尘扬起来,整个脱完了的确干净很多,然而这会就出了个大乌龙,我们清理的是三楼的西边一间,结果老丈人上来说要住东边那间的🤦‍♂️,不过其实西边的也得清理,因为还是要放被子什么的,不算是白费功夫,接着清理东边那间,之前这个房子做过群租房,里面有个高低铺的床,当时觉得可以用在放被子什么的就没扔,只是拆掉了放旁边,我们就把它擦干净了又装好,发现螺丝🔩少了几个,亘古不变的真理,拆了以后装要不就多几个要不就少几个,不是很牢靠,不过用来放放被子省得放地上总还是可以的,对了前面还做了个事情就是铺地毯,其实也不是地毯,就是类似于墙布雨篷布那种,别人不用了送给我们的,三楼水泥地也不会铺瓷砖地板了就放一下,干净好看点,不过大小不合适要裁一下,那把剪刀是真的太难用了,我手都要抽筋了,它就是刀口只有一小个点是能剪下来的,其他都是钝的,后来还是用刀片直接裁,铺好以后,真的感觉也不太一样了,焕然一新的感觉
差不多中午了就去吃饭了,之前两次是去了一家小饭店,还是还比较干净,但是店里菜不好吃,还死贵,这次去了一家小快餐店,口味好,便宜,味道是真的不错,带鱼跟黄鱼都好吃,一点都不腥,我对这类比较腥的鱼真的是很挑剔的,基本上除了家里做的很少吃外面的,那天抱着试试的态度吃了下,真的还不错,后来丈母娘说好像这家老板是给别人结婚喜事酒席当厨师的,怪不得做的好吃,其实本来是有一点小抗拒,怕不干净什么的,后来发现菜很好吃,而且可能是老丈人跟干活的师傅去吃的比较多,老板很客气,我们吃完饭,还给我们买了葡萄吃,不过这家店有一个槽点,就是饭比较不好吃,有时候会夹生,不过后面聊起来其实是这种小菜馆饭点的通病,烧的太早太多容易多出来浪费,烧的迟了不够吃,而且大的电饭锅比较不容易烧好。
下午前面还是在处理三楼的,窗户上各种钉子,实在是太多了,我后面在走廊上排了一排🤦‍♂️,有些是直接断了,有些是就撬了出来,感觉我在杭州租房也没有这样子各种钉钉子,挂下衣服什么的也不用这么多吧,比较不能理解,搞得到处都是钉子。那天我爸也去帮忙了,主要是在卫生间里做白缝,其实也是个技术活,印象中好像我小时候自己家里也做过这个事情,但是比较模糊了,后面我们三楼搞完了就去帮我爸了,前面是我老婆二爹在那先刷上白缝,这里叫白缝,有些考究的也叫美缝,就是瓷砖铺完之后的缝,如果不去弄的话,里面水泥的颜色就露出来了,而且容易渗水,所以就要用白水泥加胶水搅拌之后糊在缝上,但是也不是直接糊,先要把缝抠一抠,因为铺瓷砖的还不会仔细到每个缝里的水泥都是一样满,而且也需要一些空间糊上去,不然就太表面的一层很容易被水直接冲掉了,然后这次其实也不是用的白水泥,而是直接现成买来就已经配好的用来填缝的,兑水搅拌均匀就好了,后面就主要是我跟我爸在搞,那个时候真的觉得我实在是太胖了,蹲下去真的没一会就受不了了,膝盖什么的太难受了,后面我跪着刷,然后膝盖又疼,也是比较不容易,不过我爸动作很快,我中间跪累了休息一会,我爸就能搞一大片,后面其实我也没做多少(谦虚一下),总体来讲这次不是很累,就是蹲着跪着腿有点受不了,是应该好好减肥了。

0%