[片段] 方法参数收集
发表更新Java框架 / Spring2 分钟读完 (大约330个字)

[片段] 方法参数收集

以前的代码，用于收集当前方法的所有参数，放在map中方便调取

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
66
67
68
69
70
import com.google.common.collect.ImmutableMap;
import lombok.Data;
import org.aspectj.lang.JoinPoint;
import org.aspectj.lang.annotation.After;
import org.aspectj.lang.annotation.Aspect;
import org.aspectj.lang.annotation.Before;
import org.aspectj.lang.annotation.Pointcut;
import org.aspectj.lang.reflect.MethodSignature;
import org.springframework.stereotype.Component;

import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.stream.IntStream;

@Aspect
@Component
public class ArgumentsCollector {

    private static final ThreadLocal<Map<String, Object>> ARGUMENTS = ThreadLocal.withInitial(ImmutableMap::of);

    static Map<String, Object> getArgs() {
        return ARGUMENTS.get();
    }

    private Object[] args(Object[] args, int exceptLength) {
        if (exceptLength == args.length) {
            return args;
        }

        return Arrays.copyOf(args, exceptLength);
    }

    @Pointcut("@annotation(CollectArguments)")
    void collectArgumentsAnnotationPointCut() {
    }

    @Before("collectArgumentsAnnotationPointCut()")
    public void doAccessCheck(JoinPoint joinPoint) {
        final String[] parameterNames = ((MethodSignature) joinPoint.getSignature()).getParameterNames();
        final Object[] args = args(joinPoint.getArgs(), parameterNames.length);

        ARGUMENTS.set(Collections.unmodifiableMap((IntStream.range(0, parameterNames.length)
                .mapToObj(idx -> Tuple2.of(parameterNames[idx], args[idx]))
                .collect(HashMap::new, (m, t) -> m.put(t.getT1(), t.getT2()), HashMap::putAll))));
    }

    @After("collectArgumentsAnnotationPointCut()")
    public void remove() {
        ARGUMENTS.remove();
    }

    @Data
    private static class Tuple2<T1, T2> {

        private T1 t1;
        private T2 t2;

        Tuple2(T1 t1, T2 t2) {
            this.t1 = t1;
            this.t2 = t2;
        }

        public static <T1, T2> Tuple2<T1, T2> of(T1 t1, T2 t2) {
            return new Tuple2<>(t1, t2);
        }
    }
}

附送一段代码，用于将方法中收集的参数转换成Bean

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import org.springframework.beans.BeanUtils;
import org.springframework.beans.MutablePropertyValues;
import org.springframework.validation.DataBinder;

public class BinderUtil {

    BinderUtil() {
    }

    @SuppressWarnings("unchecked")
    public static <T> T getTarget(Class<T> beanClazz) {
        final DataBinder binder = new DataBinder(BeanUtils.instantiate(beanClazz));
        binder.bind(new MutablePropertyValues(ArgumentsCollector.getArgs()));
        return (T) binder.getTarget();
    }
}

使用实例：

1
2
3
4
5
6
7
8
9
10
@Override
@CollectArguments
public List<PsJobSequenceVO> findJobSequence(
        String jobSeqGroupId,
        String jobSeqId,
        Integer state,
        Date endDate
) {
    return jobSequenceHandler.findJobSequence(BinderUtil.getTarget(PsJobSequenceFindRO.class)).getData();
}
高性能MySql 4至6章读书笔记
发表更新中间件 / mysql22 分钟读完 (大约3225个字)

高性能MySql 4至6章读书笔记

第四章 Schema设计

选择优化的数据类型

更小的通常更好，但是要确保没有低估需要存储的值的范围，因为在schema中的多个地方增加数据类型范围是一个十分耗时的操作。

简单就好

简单的数据类型的操作通常需要更少的cpu时间。

尽量避免NULL

可为NULL的列使得索引、索引比统计和值比较都更为复杂。

当然也有例外，InnoDB使用单独的位存储NULL值， 所以对于稀疏数据有很好的空间效率。

选择标识符

一旦选定一种类型，要确保在所有的关联表中都使用同样的类型。类型之间需要精确匹配，包括像UNSIGNED这样的属性。尽量只用整型定义标识符。

注意可变长字符串

其在临时表和排序时可能导致悲观的按最大长度分配内存

范式与反范式

范式是好的，但是反范式有时也是必须的，并且能带来好处。

第五章 创建高性能索引

B-Tree 索引的查询类型
  • 全值匹配： 指的是和索引的所有列进行匹配
  • 匹配最左前缀： 查找索引前几列进行匹配
  • 匹配列前缀: 只匹配某一列的值的开头部分
  • 匹配范围值： 查找索引某一范围的值
  • 精确匹配某一列并范围匹配另外一列
  • 只访问索引的查询：覆盖索引
B-Tree 索引的限制

  • 如果不是按照索引的最左列开始查找，则无法使用索引

  • 不能跳过索引中的列

  • 如果查询中有某个列的范围查询，则其右边的所有列都无法使用索引：

    例如查询 索引为key(last_name, fisrt_name, dob)

    1
    where last_name = 'a' and first_name like 'J%' and dob = '1877-12-23'
索引的优点
  1. 大大减少服务器需要扫描的数据量
  2. 帮助服务器避免排序和临时表
  3. 将随机I/O变为顺序I/O
高性能索引-独立的列

如果查询中列不是独立的，则mysql不会使用索引

1
2
select actor_id from sakila.actor where actor_id + 1 = 5;

高性能索引-前缀索引和索引选择性

有时候需要索引很长的字符列，通常可以索引开始部分的字符，同时也会降低索引的选择性。

索引的选择性指的是，不重复的索引值和数据表的记录总数的比值。索引的选择性越高表示查询效率越高，因为选择性高的索引可以过滤掉更多的行。

前缀索引是一种能使索引更小，更快的有效方法，但是也有其缺点：前缀索引无法做order by 和 group by，也无法使用前缀索引做覆盖索引。

高性能索引-多列索引

最容易遇到的困惑是多列索引的顺序，正确的顺序依赖于使用索引的查询，同时需要考虑如何更好的满足排序和分组需要。对于如何选择索引的列顺序有一个经验法则：将选择性最高的列放在索引的最前列。只有不需要考虑排序和分组时，将选择性跟高的列放在最前面通常是最好的，但是考虑问题需要更全面，避免随机I/O和排序更加重要。

高性能索引-覆盖索引

如果一个索引包含所需要查询的字段的值，我们就可以称之为“覆盖索引”

覆盖索引的好处：

  • 索引条目通常远小于数据行大小，所以如果只需要读取索引，那mysql就会极大的减少数据访问量。
  • 因为索引是按照列值顺序存储的，所以对于I/O密集型范围查询回避随机从磁盘读取每一行数据的I/O要小的多
  • 由于Innodb的聚簇索引，覆盖索引对Innodb表特别有用，可以避免对主键索引的二次查询。

覆盖索引的陷阱：

1
select * from products where actor = 'SEAN CARREY' and title like '%APOLLO%';

  • 没有索引能够覆盖这个查询，因为查询从表中选择了所有的列
  • mysql不能再索引中执行like操作，只能做最左前缀匹配

高性能索引-使用索引扫描来做排序

mysql有两种方式可以生成有序的结果：通过排序操作；或者使用索引顺序扫描。mysql可以使用同一个索引既满足排序，有用于查找行。

只有当索引的列顺序和ORDER BY子句的顺序完全一致，并且所有列的排序方向都一样时，mysql才能使用索引来对结果做排序。如果查询需要关联多张表，则只有当ORDER BY子句引用的字段全部为第一个表时，才能用索引做排序。ORDER BY子句和查询的限制是一样的：需要满足索引的最左前缀的要求。

有一种情况下ORDER BY子句可以不满足索引的最左前缀要求：

1
2
select rental_id, staff_id from sakila.rental where rental_date = '2005-05-25'
order by inventory_id, customer_id;

索引为key(rental_date, inventory_id, customer_id)，前导列为常量的时候，如果where子句或者join子句中对这些列指定了常量，就可以弥补ORDER BY的不足。

1
2
where rental_date > '2005-12-25' order by inventory_id, customer_id;
where rental_date = '2005-12-25' and inventory_id in (1, 2) order by cusomter_id;

对于索引上是范围查询，mysql无法使用之后的索引列

高性能索引-使用索引扫描减少锁

索引可以让查询锁定更少的行，如果你的查询从不访问那些不需要的行，那么就会锁定更少的行。但这只有当innoDB在存储引擎层能够过滤掉所有不需要的行是才有效。如果索引无法过滤掉无效的行，那么innoDB检索到数据并返回给服务器层后，innoDB已经锁定这些行了（mysql 5.6后没有这个问题）。

高性能索引-避免多个范围条件

下面的查询：

1
where last_online > date_sub(now(), interval 7 day) and age bwtween 18 and 25

这个查询有一个问题：它有两个范围条件,last_online和age列，mysql可以使用last_online的索引或者是age列的索引，但是无法同时使用它们。

高性能索引-延迟关联优化分页

如果一个查询匹配结果有上百万行的话会怎样？

1
select * from profiles where sex = 'm' order by rating limit 10;

即使有索引，如果用户界面需要翻页，并且翻页到比较靠后的地方也会非常慢，如：

1
select * from profiles where sex = 'm' order by rating limit 1000000, 10;

无论如何创建索引，这种查询都是个严重的问题，mysql需要花费大量时间来扫描需要丢弃的数据。其中一个解决的办法是限制能够翻页的数量。

优化这类索引的另一个比较好的策略是使用延迟关联，通过使用覆盖索引返回需要的主建，再根据这些主建回主表获得需要的行，这样可以减少mysql扫描需要丢弃的行数。

1
2
3
4
5
6
select * from profiles innner join 
(
    select id fomr profiles p where p.sex = 'm' order by rating limit 1000000, 10

) as t using (id);

第六章 慢查询优化

优化数据访问

查询性能低下最基本的原因是访问数据太多。某些查询可能不可避免的需要筛选大量数据，单这并不常见。大部分性能低下的查询都可以通过减少访问的数据量的方式进行优化。对于低效的查询，我们发现通过下面几个步骤来分析总是很有效：

  1. 确认应用程序时候检索大量超过需要的数据。
  2. 确认mysql服务层是否在分许大量超过需要的数据行。

第一种情况可以使用limit和选择需要的列来解决。在确定查询只返回需要的数据之后，接下来应该看看查询为了返回结果是否扫描了过多的数据，对于mysql有三个衡量查询开销的指标：

  • 响应时间
  • 扫描的行数
  • 返回的行数

没有那个指标能完美地衡量查询的开销，但它们大致反映了mysql内部查询时需要访问多少数据，并可以大概推算出查询运行的时间。

在评估查询开销的时候，需要考虑一下从表中找到某一行数据的成本。mysql有好几种访问方式可以查找并返回一行结果。有些访问方式可能需要扫描很多行才能返回一行结果，也有些访问方式可能无需扫描就能返回结果。

在explain语句中的type列反应了访问类型。访问类型有很多种，从全表扫描到索引扫描、范围扫描、唯一索引查询、常数引用等。这里列的这些，速度是从慢到快，扫描行数也是从大到小。如果查询没有办法找到合适是访问类型，那么解决的最好办法通常是增加一个合适的索引。

一般mysql能够使用如下三种方式应用where条件，从好到坏依次为：

  • 从索引中使用where条件吗来过滤不匹配的记录，这是在存储引擎层完成的。
  • 使用索引覆盖扫描来返回记录（extra出现using index），直接从索引中过滤不需要的数据并返回命中结果。这是在mysql服务层完成的，但无需再回表查询记录。
  • 从数据表中返回数据，然后过滤不满足条件的记录（extra出现using where）。这是在mysql服务器层完成，mysql需要从数据表中读出记录然后过滤。

如果发现查询需要扫描大量的数据但只返回少数的行，那么可以使用下面的技巧去优化它：

  • 使用覆盖索引，把需要用的列都放到索引中
  • 改变库表结构。例如使用单独的汇总表
  • 重写复杂的查询， 让mysql优化器能够以更加高效的方式执行这个查询

重构查询方式-切分查询

有时候对于一个大查询我们需要分而治之，将大查询分成小查询。删除旧数据是一个很好的例子，如果用一个大的语句一次性完成，则可能一次需要锁住很多数据、占满整个事务日志、耗尽系统资源、阻塞恨到重要的查询。

重构查询方式-分解关联查询

例如下面这个查询：

1
2
3
4
select * from tag
join tag_post on tag_post.tag_id = tag.id
join post on tag_post.post_id = post.id
where tag.tag = 'mysql';

可以分解成下面这个查询来代替：

1
2
3
4
5
select * from tag where tag = 'mysql';

select * from tag_post where tag_id = 1234;

select * from post where post.id in (123,456,567);

用分解关联查询的方式重构查询有如下的优势：

  • 让缓存效率更高。许多应用程序可以方便地缓存单表查询对应的结果对象。
  • 将查询分解后，执行单个查询可以减少锁的竞争。
  • 在应用层做关联，可以更容易对数据库进行拆分，更容易做到高性能和高扩展。
  • 查询本身效率可能提升，使用in代替关联查询，可能比随机关联更高效。
  • 减少冗余记录的查询
  • 相当于在应用层实现了哈希关联

重构查询方式-优化关联查询

  • 确保on或者using子句上的列上有索引。
  • 确保任何group by和 order by 的表达式中只涉及到一个表中的列，这样mysql才有可能使用索引来优化这个过程
Boyer–Moore 字符搜索算法
发表更新算法 / 字符串4 分钟读完 (大约570个字)

Boyer–Moore 字符搜索算法

因为字符比较是从右往左比较的，所以第一层循环 needle.length + 1 <= i < haystack.length。

1
2
3
4
5
6
7
8
9
10
11
12
13
                  start=needle.length - 1                                             end=haystack.length - 1
                          +                                                                   +
                          |                                                                   |
                          |                                                                   |
                          v-------------------------------------------------------------------v->
  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21  22  23
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| t | h | i | s |   | i | s |   | a |   | s | i | m | p | l | e |   | e | x | a | m | p | l | e |
+-------------------------------+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
+---------------------------+
| e | x | a | m | p | l | e |
+---+---+---+---+---+---+---+

第二层循环中i变量表示坏字符的位置、j表示搜索坏字符开始位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
                          i
                          +
                          |
                          v
  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21  22  23
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| t | h | i | s |   | i | s |   | a |   | s | i | m | p | l | e |   | e | x | a | m | p | l | e |
+-------------------------------+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
+---------------------------+
| e | x | a | m | p | l | e |
+---+---+---+---+---+---+-+-+
                          ^
                          |
                          +
                          j

i,j指针向左搜索,如果完全匹配直接返回i即可

1
2
3
4
5
for (j = needle.length - 1; needle[j] == haystack[i]; --i, --j) {
    if (j == 0) {
        return i;
    }
}

坏字符规则和好字符规则

坏字符:从右向左第一个不匹配的字符
好字符:从坏字符下一个字符直到最后的字符

可以认为字符移动有两种策略：坏字符对齐和好字符对齐，然后选择字符移动距离大的策略即可

wiki实现

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
/**
 * Returns the index within this string of the first occurrence of the
 * specified substring. If it is not a substring, return -1.
 *
 * There is no Galil because it only generates one match.
 *
 * @param haystack The string to be scanned
 * @param needle The target string to search
 * @return The start index of the substring
 */
public static int indexOf(char[] haystack, char[] needle) {
    if (needle.length == 0) {
        return 0;
    }
    int charTable[] = makeCharTable(needle);
    int offsetTable[] = makeOffsetTable(needle);
    for (int i = needle.length - 1, j; i < haystack.length;) {
        for (j = needle.length - 1; needle[j] == haystack[i]; --i, --j) {
            if (j == 0) {
                return i;
            }
        }
        // i += needle.length - j; // For naive method
        i += Math.max(offsetTable[needle.length - 1 - j], charTable[haystack[i]]);
    }
    return -1;
}

/**
 * Makes the jump table based on the mismatched character information.
 */
private static int[] makeCharTable(char[] needle) {
    final int ALPHABET_SIZE = Character.MAX_VALUE + 1; // 65536
    int[] table = new int[ALPHABET_SIZE];
    for (int i = 0; i < table.length; ++i) {
        table[i] = needle.length;
    }
    for (int i = 0; i < needle.length - 2; ++i) {
        table[needle[i]] = needle.length - 1 - i;
    }
    return table;
}

/**
 * Makes the jump table based on the scan offset which mismatch occurs.
 * (bad character rule).
 */
private static int[] makeOffsetTable(char[] needle) {
    int[] table = new int[needle.length];
    int lastPrefixPosition = needle.length;
    for (int i = needle.length; i > 0; --i) {
        if (isPrefix(needle, i)) {
            lastPrefixPosition = i;
        }
        table[needle.length - i] = lastPrefixPosition - i + needle.length;
    }
    for (int i = 0; i < needle.length - 1; ++i) {
        int slen = suffixLength(needle, i);
        table[slen] = needle.length - 1 - i + slen;
    }
    return table;
}

/**
 * Is needle[p:end] a prefix of needle?
 */
private static boolean isPrefix(char[] needle, int p) {
    for (int i = p, j = 0; i < needle.length; ++i, ++j) {
        if (needle[i] != needle[j]) {
            return false;
        }
    }
    return true;
}

/**
 * Returns the maximum length of the substring ends at p and is a suffix.
 * (good suffix rule)
 */
private static int suffixLength(char[] needle, int p) {
    int len = 0;
    for (int i = p, j = needle.length - 1;
             i >= 0 && needle[i] == needle[j]; --i, --j) {
        len += 1;
    }
    return len;
}
[片段] Mybatis ParameterHandler实践
发表更新Java框架 / Mybatis5 分钟读完 (大约744个字)

[片段] Mybatis ParameterHandler实践

用来批量加密用@Decrypted注解的String字段，可能还有一些坑。

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229

import com.google.common.cache.CacheBuilder;
import com.google.common.cache.CacheLoader;
import com.google.common.cache.LoadingCache;
import com.ke.zhaopin.manage.server.config.mybatis.interceptor.anno.Decrypted;
import com.lianjia.ctt.kinko.spi.CipherSpi;
import com.sun.istack.internal.NotNull;
import lombok.Getter;
import lombok.extern.slf4j.Slf4j;
import org.apache.commons.lang3.StringUtils;
import org.apache.ibatis.binding.MapperMethod;
import org.apache.ibatis.executor.parameter.ParameterHandler;
import org.apache.ibatis.plugin.*;
import org.apache.ibatis.reflection.MetaObject;
import org.apache.ibatis.scripting.defaults.DefaultParameterHandler;
import org.apache.ibatis.session.Configuration;
import org.apache.ibatis.session.defaults.DefaultSqlSession;
import org.joor.Reflect;
import reactor.core.publisher.Flux;

import java.lang.reflect.Array;
import java.lang.reflect.Field;
import java.sql.PreparedStatement;
import java.util.*;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.TimeUnit;
import java.util.function.Function;
import java.util.stream.Collectors;


@Intercepts({
        @Signature(type = ParameterHandler.class, method = "setParameters", args = {PreparedStatement.class}),
})
@Slf4j
public class EncryptInterceptor implements Interceptor {

    private static final String COLLECTION_KEY = "collection";
    private static final String ARRAY_KEY = "array";

    private final LoadingCache<Class, List<String>> decryptFieldCaches = CacheBuilder.newBuilder()
            .maximumSize(200)
            .expireAfterAccess(10L, TimeUnit.MINUTES)
            .build(new CacheLoader<Class, List<String>>() {
                       @Override
                       public List<String> load(Class key) {
                           return Arrays.stream(key.getDeclaredFields())
                                   .filter(f -> f.getAnnotation(Decrypted.class) != null)
                                   .filter(f -> {
                                       boolean isString = f.getType() == String.class;
                                       if (!isString) {
                                           log.warn(f.getName() + "is not String, actual type is " + f.getType().getSimpleName() + " ignored");
                                       }
                                       return isString;
                                   })
                                   .map(Field::getName)
                                   .collect(Collectors.toList());
                       }
                   }
            );

    private CipherSpi cipherSpi;

    public EncryptInterceptor(CipherSpi cipherSpi) {
        this.cipherSpi = cipherSpi;
    }

    @Override
    public Object intercept(Invocation invocation) throws Throwable {

        Flux<CryptContext> contextFlux = Flux.empty();

        do {
            if (!(invocation.getTarget() instanceof DefaultParameterHandler)) break;

            final Reflect parameterHandler = Reflect.on(invocation.getTarget());
            final Object parameterObject = parameterHandler.get("parameterObject");
            final Configuration configuration = parameterHandler.get("configuration");

            if (parameterObject instanceof DefaultSqlSession.StrictMap) {
                // 单个Collection/Map/Array参数
                DefaultSqlSession.StrictMap<?> paramMap = (DefaultSqlSession.StrictMap<?>) parameterObject;

                Collection<?> collection = null;
                Class<?> componentType = null;
                if (paramMap.containsKey(COLLECTION_KEY)) {
                    collection = (Collection<?>) paramMap.get(COLLECTION_KEY);
                    componentType = collection.iterator().next().getClass();
                } else if (paramMap.containsKey(ARRAY_KEY)) {
                    Object[] array = (Object[]) paramMap.get(ARRAY_KEY);
                    componentType = array.getClass().getComponentType();
                    collection = Arrays.asList(array);
                }

                if (!isUserDefinedClass(componentType)) break;

                contextFlux = collection(configuration, collection, componentType);

            } else if (parameterObject instanceof MapperMethod.ParamMap) {
                // 多个参数
                MapperMethod.ParamMap<?> paramMap = (MapperMethod.ParamMap<?>) parameterObject;

                final List<?> params = paramMap.values().stream().filter(Objects::nonNull).distinct().collect(Collectors.toList());

                for (Object parameter : params) {
                    if (parameter instanceof Collection) {
                        Collection<?> collection = (Collection<?>) parameter;
                        if (collection.isEmpty()) {
                            continue;
                        }

                        Class<?> componentType = collection.iterator().next().getClass();
                        if (!isUserDefinedClass(componentType)) {
                            continue;
                        }
                        final Flux<CryptContext> collectionFlux = collection(configuration, collection, componentType);
                        contextFlux = contextFlux.concatWith(collectionFlux);

                    } else if (parameter.getClass().isArray()) {
                        if (Array.getLength(parameter) == 0) continue;
                        final Class<?> componentType = parameter.getClass().getComponentType();
                        if (!isUserDefinedClass(componentType)) {
                            continue;
                        }
                        Collection<?> collection = Arrays.asList((Object[]) parameter);

                        final Flux<CryptContext> collectionFlux = collection(configuration, collection, componentType);
                        contextFlux = contextFlux.concatWith(collectionFlux);

                    } else if (isUserDefinedClass(parameter.getClass())) {
                        final Flux<CryptContext> singleFlux = collection(configuration, Collections.singletonList(parameter), parameter.getClass());
                        contextFlux = contextFlux.concatWith(singleFlux);
                    }
                }

            } else if (isUserDefinedClass(parameterObject.getClass())) {
                // 单个非Collection/Map/Array参数
                contextFlux = collection(configuration, Collections.singletonList(parameterObject), parameterObject.getClass());
            } else {
                // 不是用interface的情况
            }


        } while (false);

        final List<CryptContext> cryptContexts = encrypt(contextFlux);

        invocation.proceed();

        restore(cryptContexts);

        return null;
    }

    private void restore(List<CryptContext> cryptContexts) {
        for (CryptContext cryptContext : cryptContexts) {
            cryptContext.metaObject.setValue(cryptContext.fieldName, cryptContext.value);
        }
    }

    private Flux<CryptContext> collection(Configuration configuration, Collection<?> collection, Class<?> componentType) throws ExecutionException {
        final List<String> fieldNames = this.getDecryptFields(componentType);

        return Flux.fromIterable(collection)
                .map(configuration::newMetaObject)
                .flatMapIterable(metaObject -> fieldNames.stream().map(fieldName -> new CryptContext(metaObject, fieldName)).collect(Collectors.toList()));
    }

    private List<CryptContext> encrypt(Flux<CryptContext> contextFlux) {
        return contextFlux
                .filter(context -> StringUtils.isNotBlank(context.value))
                .buffer(1000)
                .doOnNext(contexts -> {
                    Map<String, String> secretMap = Collections.emptyMap();
                    try {
                        secretMap = cipherSpi.batchEncrypt(contexts.stream().map(CryptContext::getValue).distinct().collect(Collectors.toList()));
                    } catch (Exception e) {

                    }
                    for (CryptContext context : contexts) {
                        context.secret = secretMap.get(context.value);
                    }
                })
                .flatMapIterable(Function.identity())
                .doOnNext(context -> context.metaObject.setValue(context.fieldName, context.secret))
                .collectList()
                .block();
    }

    @NotNull
    private List<String> getDecryptFields(Class<?> modelClazz) throws ExecutionException {
        return this.decryptFieldCaches.get(modelClazz);
    }

    private boolean isUserDefinedClass(Class<?> clazz) {
        return !clazz.isPrimitive() && !clazz.getPackage().getName().startsWith("java");
    }

    @Override
    public Object plugin(Object target) {
        return Plugin.wrap(target, this);
    }

    @Override
    public void setProperties(Properties properties) {

    }
}

@Getter
class CryptContext {

    CryptContext(MetaObject metaObject, String fieldName) {
        this.metaObject = metaObject;
        this.fieldName = fieldName;
        this.value = (String) metaObject.getValue(fieldName);
        if (StringUtils.isBlank(value)) {
            this.secret = StringUtils.EMPTY;
        }
    }

    final MetaObject metaObject;

    final String fieldName;

    final String value;

    String secret;
}

LeetCode两个经典的排序算法
发表更新算法 / 排序3 分钟读完 (大约379个字)

LeetCode两个经典的排序算法

LeetCode两个经典的排序算法

这回是标题党， 记录下两个分而治之的排序算法（手写），分而治之的算法很容易改造成并行算法，肯定是未来的潮流， leetcode已通过， 两个算法都使用了原地(inplace)更新。

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
class Solution {
    public List<Integer> sortArray(int[] nums) {
        // merge(nums, 0, nums.length - 1);
        sort(nums, 0, nums.length - 1);
        return IntStream.of(nums).boxed().collect(Collectors.toList());
    }

	//-------------------归并排序-------------------//
    private void merge(int[] nums, int start, int end) {
        if (start >= end) return;
        int midIdx = start + (end - start) / 2;
        merge(nums, start, midIdx);
        merge(nums, midIdx+1, end);
        concat(nums, start, midIdx, end);
    }

    private void concat(int[] nums, int start, int midIdx, int end) {
        int[] tmp = new int[end - start + 1];
        int lp = start, rp = midIdx + 1, i = 0;

        while (lp <= midIdx && rp <= end) {
            tmp[i++] = nums[lp] < nums[rp] ? nums[lp++] : nums[rp++];
        }

        while (lp <= midIdx) {
            tmp[i++] = nums[lp++];
        }

        while (rp <= end) {
            tmp[i++] = nums[rp++];
        }

        System.arraycopy(tmp, 0, nums, start, tmp.length);
    }

    // -------------------  归并排序 链表 ---------------------//

    class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            if (lists.length == 0) return null;
            return merge(lists, 0 , lists.length - 1);
        }

        private ListNode merge(ListNode[] lists, int low, int high) {
            if (low == high) return lists[low];

            int mid = (high - low) / 2 + low;

            return mergeLists( merge(lists, low, mid), merge(lists, mid+1, high));
        }

        public ListNode mergeLists(ListNode node1, ListNode node2) {
            if (node1 == null) return node2;
            if (node2 == null) return node1;

            if (node1.val < node2.val) {
                node1.next = mergeLists(node1.next, node2);
                return node1;
                
            } else {
                node2.next = mergeLists(node1, node2.next);
                return node2;
            }
        }
    }
    
    //-------------------快速排序-------------------//

    private void sort(int[] nums, int start, int end) {
        if (start >= end) return;

        int bIdx = partition(nums, start, end);
        sort(nums, start, bIdx - 1);
        sort(nums, bIdx + 1, end);
    }

    private int partition(int[] nums, int start, int end) {
        int idx = start, base = nums[end];

        for (int i = start; i < end; i++) {
            if (nums[i] < base) {
                swap(nums, idx++, i);
            }
        }
        swap(nums, idx, end);
        return idx;
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
LeetCode 最长回文子串算法
发表更新算法 / 字符串1 分钟读完 (大约147个字)

LeetCode 最长回文子串算法

Manacher 算法 容易理解，实现起来也没什么大坑，复杂度还是 O(n)的， 花半个小时实现下很有意思

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
class Solution {
    public String longestPalindrome(String s) {        
        StringBuilder sb = new StringBuilder(2 + 2 * s.length());
        sb.append("^");
        for (int i = 0; i < s.length(); i++) {
            sb.append("#").append(s.charAt(i));
        }
        sb.append("#$");
        
        String s2 = sb.toString();
        
        int maxStart = 1, max = 0, rC = 1, rR = 1;
        int[] p = new int[s2.length()];
        
        for (int i = 1; i < s2.length() - 1; i++ ) {
            
            p[i] = i < rR ? Math.min(p[2 * rC - i], rR - i) : 0;
            
            while (s2.charAt(i+p[i]+1) == s2.charAt(i - p[i] - 1)) {
                p[i] = p[i]+1;
            }
            
            if (i + p[i] > rR) {
                rC = i;
                rR = i + p[i];
            }
            
            if (p[i] > max) {
                maxStart = i - p[i];
                max = p[i];
            }
        }
        

        return s2.substring(maxStart,maxStart + 2*max+1).replace("#", "");
    }
}
[项目] 多角色权限展示数据的一种实现
发表更新工作 / 挑战3 分钟读完 (大约428个字)

[项目] 多角色权限展示数据的一种实现

多角色权限如果遇到不同角色能看到不同的列可以怎么做

  • 逐行读取

最简单的解决方法，实现简单。但是在微服务中调用接口次数太多，性能很差。

  • 批量读取

实现较复杂，但是性能好很多，下面主要介绍这种方法的思路

批量读取

以分页读取数据为例：

  1. 读取第一页数据，包含需要展示数据的id和所属权限（多个）

为什么需要所属权限这个字段呢？ 因为决定能否看到这行是有你所拥有的所有权限决定的，而决定能否看到哪个列是由这行所拥有的权限决定的。

如何获取该行所拥有的权限呢，我的做法是分不同的权限查询结果通过union 组合起来

  1. 将第一页数据原始顺序保存， 然后按行拥有权限分组

记录原始顺序是因为后面分组后会打乱， 为什么要分组？分组后同样的查询才能聚合在一起，可以简化代码

  1. 根据权限分组多次查询所需要的字段，然后将查询结果合并

这里我使用的graphql来选择需要查询的字段

  1. 最后还原成原来的顺序

可以使用guava Ordering工具类方便生成Compartor

[]: https://blog.yamato.moe/2018/11/06/2018-11-06-biz/ “根据权限查询时避免角色切换的一种思路”
[]: https://blog.yamato.moe/2019/04/04/Mybatis%20ResultSetHandler_2019-04-04%20%E7%BB%AD/ “【片段】 Mybatis ResultSetHandler 实践-续”
[]: https://blog.yamato.moe/2019/01/09/Mybatis%20ResultSetHandler_2019-01-09/ “【片段】 Mybatis ResultSetHandler 实践”

LeetCode二叉树基础算法
发表更新算法 / 二叉树15 分钟读完 (大约2235个字)

LeetCode二叉树基础算法

树的高度

104. Maximum Depth of Binary Tree (Easy)

递归计算二叉树左右两边深度，取最大值。

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

/**

 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return Math.max(left, right) + 1;
    }
}

平衡树

110. Balanced Binary Tree (Easy)

递归遍历二叉树左右子树深度

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    
    private boolean balance = true;
    
    public boolean isBalanced(TreeNode root) {
        visitTree(root);
        return balance;
    }
    
    private int visitTree(TreeNode root) {
        if (root == null) return 0;
        int left = visitTree(root.left);
        int right = visitTree(root.right);
        if (Math.abs(left - right) > 1 ) this.balance = false;
        return Math.max(left, right) + 1;
    }
}

两节点的最长路径

543. Diameter of Binary Tree (Easy)

递归遍历二叉树左右子树深度， 路径就是两边子树深度之和

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    
    private int max;
        
    public int diameterOfBinaryTree(TreeNode root) {
        deep(root);
        return max;
    }
    
    private int deep(TreeNode root) {
        if (root == null) return 0;
        int left = deep(root.left);
        int right = deep(root.right);
        max = Math.max(max,left+right);
        return Math.max(left, right) + 1;
    }
}

翻转树

226. Invert Binary Tree (Easy)

递归交换左右子树的引用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return root;
        TreeNode right =root.right;
        root.right = invertTree(root.left);
        root.left = invertTree(right);
        return root;
    }
}

归并两棵树

617. Merge Two Binary Trees (Easy)

递归时如果其中一个节点是空，可以直接复用该节点。如果新建节点，需要拷贝节点的左右子树引用，递归时会用到。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null ) return null;
        if (t1 == null) return t2;
        if (t2 == null) return t1;
        TreeNode root =  new TreeNode(t1.val + t2.val);
        root.left = mergeTrees(t1.left, t2.left);
        root.right = mergeTrees(t1.right, t2.right);
        return root;
    }
}

判断路径和是否等于一个数

Leetcode : 112. Path Sum (Easy)

递归查询子树和是否等于目标和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) return false;
        if (root.val == sum && root.left == null && root.right == null) return true;
        return  hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
}

统计路径和等于一个数的路径数量

437. Path Sum III (Easy)

双层递归

  1. 以当前节点为起点统计路径和
  2. 当前节点以下节点为起点统计路径和

以root为根节点的路径数量= 以root为起点统计路径和+root左节点为起点统计路径和+root右节点为起点统计路径和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int pathSum(TreeNode root, int sum) {
        if (root == null) return 0;
        //结果数 等于 以当前root为父节点和 root以下为父节点结果数之和
        return sum(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
    }
    // 计算以当前node为父节点能都多少路径数
    private int sum(TreeNode node, int sum) {
        if (node == null) return 0;
        int count = 0;
        if (node.val == sum) count++;
        count += sum(node.left, sum - node.val) + sum(node.right, sum - node.val);
        return count;
    }
}

子树

572. Subtree of Another Tree (Easy)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSubtree(TreeNode s, TreeNode t) {
        if (s == null) return false;
        return isSubRoot(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
    }
    
    public boolean isSubRoot(TreeNode node, TreeNode t) {
        if (node == null && t == null) return true;
        if (node == null || t == null) return false;
        if (node.val != t.val) return false;
        return isSubRoot(node.left, t.left) && isSubRoot(node.right, t.right); 
    }
}

树的对称

101. Symmetric Tree (Easy)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return isSymmetric(root.left, root.right);
    }
    
    public boolean isSymmetric(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        if (left == null || right == null) return false;
        if (left.val != right.val) return false;
        return isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
    }
}

最小路径

111. Minimum Depth of Binary Tree (Easy)

和最大路径类似

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        int left = minDepth(root.left);
        int right = minDepth(root.right);
        if (left == 0 || right == 0) return left + right + 1;
        return Math.min(left, right) + 1;
    }
}

统计左叶子节点的和

404. Sum of Left Leaves (Easy)

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) return 0;
        if (root.left != null && root.left.left == null && root.left.right == null) return root.left.val + sumOfLeftLeaves(root.right);
        return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
    }
}
````

#### 相同节点值的最大路径长度

[687. Longest Univalue Path (Easy)](https://leetcode.com/problems/longest-univalue-path/)

递归查找左右子树相同节点值最大路径，最大路径的计算：如果相等路径+1，如果不相等置为0。

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int path = 0;
    
    public int longestUnivaluePath(TreeNode root) {
        visit(root);
       return path; 
    }
    
    private int visit(TreeNode root) {
        if  (root == null) return 0;
        int left = visit(root.left);
        int right = visit(root.right);
        
        left =  (root.left != null && root.val == root.left.val) ? left + 1 : 0;
        right = (root.right != null && root.val == root.right.val)? right + 1 : 0;
        path = Math.max(path, left+right);
        return Math.max(left, right );
    }
}

间隔遍历

337. House Robber III (Medium)

递归查询两种情况

  1. 如果从当前节点开始
  2. 从当前节点的子节点开始
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int rob(TreeNode root) {
        if (root == null) return 0;
        int val1 = root.val, val2 = 0;
        if (root.left != null) val1+= rob(root.left.left) + rob(root.left.right);
        if (root.right != null) val1+= rob(root.right.left) + rob(root.right.right);
        
        val2 = rob(root.left) + rob(root.right);
        return Math.max(val1, val2);
    }
}

找出二叉树中第二小的节点

Second Minimum Node In a Binary Tree (Easy)

第二小节点在子树节点上，如果子树值与根节点相等，继续向下查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int findSecondMinimumValue(TreeNode root) {
        if (root == null) return -1;
        if (root.left == null) return -1;
        int left = root.left.val, right = root.right.val;
        if (root.val == root.left.val) left = findSecondMinimumValue(root.left);
        if (root.val == root.right.val) right = findSecondMinimumValue(root.right);
        if (left != -1 && right != -1) return Math.min(left, right);
        if (left > -1) return left;
        return right;
    }
}

二叉树的层平均值

637. Average of Levels in Binary Tree (Easy)

BFS

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> ret = new ArrayList<>();
        if (root == null) return ret;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()) {
            int count = queue.size();
            double sum = 0d;
            
            for(int i = 0; i < count; i++) {
                TreeNode node = queue.poll();
                sum+= node.val;
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
            ret.add(sum/count);
        }
        return ret;
    }
}

找树左下角的值

513. Find Bottom Left Tree Value (Easy)

DFS

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int val = 0;
    
    public int findBottomLeftValue(TreeNode root) {
        if (root == null) return val;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()) {
            // 这一行的数量
            int count = queue.size();
            
            for (int i = 0; i < count; i++) {
                TreeNode node = queue.poll();
                if(i == 0) val = node.val;
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
        }
        return val;
    }
}

非递归实现二叉树的后序遍历

入栈条件： 未访问过该节点
出栈条件： 访问过该节点

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    
    private List<Integer> res = new LinkedList<>();
    private Stack<TreeNode> stack = new Stack<>();
    private Set<TreeNode> visited = new HashSet<>();
    
    public List<Integer> postorderTraversal(TreeNode root) {
        if (root == null) return res;
        stack.push(root);
        
        while (!stack.isEmpty()) {
            TreeNode node = stack.peek();
            
            if ((node.left == null && node.right == null) || visited.contains(node)) {
                TreeNode i = stack.pop();
                res.add(i.val);
            } else {
                visited.add(node);
                if (node.right != null)
                    stack.push(node.right);
                if (node.left != null) 
                    stack.push(node.left);
            }
        }
        return res;
    }
    
    private void visit(TreeNode root) {
        if(root == null) return;
        visit(root.left);
        visit(root.right);
        res.add(root.val);
    }
}

非递归实现二叉树的前序遍历

入栈条件： 无
出栈条件： 直接出栈

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private List<Integer> res = new LinkedList<>();
    private Stack<TreeNode> stack = new Stack<>();
    
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null) return res;
        stack.push(root);
        
        while (!stack.isEmpty()) {
                TreeNode node = stack.pop();
                res.add(node.val);
                if (node.right != null) stack.push(node.right);
                if (node.left != null)  stack.push(node.left);
        }
        return res;
    }
}

非递归实现二叉树的中序遍历

入栈条件： 未访问过该节点
出栈条件： 访问过该节点
入栈顺序: right -> middle -> left

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private List<Integer> res = new LinkedList<>();
    private Stack<TreeNode> stack = new Stack<>();
    private Set<TreeNode> visited = new HashSet<>();
    
    public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) return res;
        push(root);
        
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if ((node.left == null && node.right == null) || visited.contains(node)) {
                res.add(node.val);
            } else {
                push(node);
            }
        }
        return res;
    }
    
    private void push(TreeNode root) {
        if (root == null) return;
        visited.add(root);
        if (root.right != null) stack.push(root.right);
        stack.push(root);
        if (root.left != null) stack.push(root.left);
    }
}
LeetCode 二叉树排序树基础算法
发表更新算法 / 二叉树8 分钟读完 (大约1178个字)

LeetCode 二叉树排序树基础算法

修剪二叉搜索树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode trimBST(TreeNode root, int L, int R) {
        if (root == null) return null;
        if (root.val < L) return trimBST(root.right, L, R);
        if (root.val > R) return trimBST(root.left, L, R);
        root.left = trimBST(root.left, L, R);
        root.right = trimBST(root.right, L, R);
        return root;
    }
}

二叉搜索树中第K小的元素

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int cnt;
    private int val;
    
    public int kthSmallest(TreeNode root, int k) {
        search(root, k);
        return val;
    
    }
    
    private void search(TreeNode root, int k) {
        if (root == null) return;
        // 
        kthSmallest(root.left, k);
        cnt++;
        if (cnt == k) {
            val =  root.val;
            return;
        }
        kthSmallest(root.right, k);
    }
}

把二叉搜索树转换为累加树

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    
    private int sum;
    
    public TreeNode convertBST(TreeNode root) {
        // 中序遍历 但是是从右往左遍历
        // 
        visit(root);
        return root;
    }
    
    
    private void visit(TreeNode root) {
        if (root == null) return;
        
        visit(root.right);
         sum += root.val;
    
        root.val = sum;
        
        visit(root.left);
    }
}

二叉搜索树的最近公共祖先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 公共祖先在左边
        if (root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q);
        // 公共祖先在右边
        if (root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q);
        // 公共祖先在这
        return root;
    }
}

二叉树的最近公共祖先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == root || q == root) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        
        // 左右都是父节点， 上一级就是公共父节点
        if(left != null && right != null) return root;
        if (left == null && right == null) return null;
        if (left != null) return left;
        return right;
    }
}

将有序数组转换为二叉搜索树

二叉树中序遍历

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return build(nums, 0, nums.length -1);
    }
    
    
    private TreeNode build(int[] nums, int start, int end) {
        
        if(start> end) return null;
        
        TreeNode node = new TreeNode(nums[(start+end)/2]);
        
        node.left = build(nums, start, (start+end)/2 -1);
        node.right = build(nums, (start+end)/2+1, end);
        return node;
    }
}

有序链表转换二叉搜索树

链表转数组

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        List<Integer> list = new LinkedList();
        ListNode now = head;
        while (now != null) {
            list.add(now.val);
            now = now.next;
        }
        
        return build(list, 0, list.size() - 1);
    }
    
    
    private TreeNode build(List<Integer> nums, int start, int end) {
        
        if(start> end) return null;
        
        TreeNode node = new TreeNode(nums.get((start+end)/2));
        
        node.left = build(nums, start, (start+end)/2 -1);
        node.right = build(nums, (start+end)/2+1, end);
        return node;
    }
}

还可以使用双指针找到链表中间节点，缺点是重复遍历节点

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode sortedListToBST(ListNode head) {
//         List<Integer> list = new LinkedList();
//         ListNode now = head;
//         while (now != null) {
//             list.add(now.val);
//             now = now.next;
//         }
        
//         return build(list, 0, list.size() - 1);
        
        return sortedListToBST(head, null);
        
        

    }
    
    private TreeNode sortedListToBST(ListNode head, ListNode tail) {
        if (head == tail) return null;
        
        ListNode mid = head, end = head;
        while (end != tail && end.next != tail) {
            mid = mid.next;
            end = end.next.next;
        }
        
        TreeNode root = new TreeNode(mid.val);
        root.right = sortedListToBST(mid.next, tail);
        root.left = sortedListToBST(head, mid);
        return root;
    }
    
    
    private TreeNode build(List<Integer> nums, int start, int end) {
        
        if(start> end) return null;
        
        TreeNode node = new TreeNode(nums.get((start+end)/2));
        
        node.left = build(nums, start, (start+end)/2 -1);
        node.right = build(nums, (start+end)/2+1, end);
        return node;
    }
    
}

两数之和 IV - 输入 BST

自己写两次遍历搜索二叉树，注意要排除自身节点

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private boolean res;
    private TreeNode r;
    private TreeNode current;
    
    
    public boolean findTarget(TreeNode root, int k) {
        r = root;
        visit(root, k);
        return res;
    }
    
    private void visit(TreeNode root, int val) {
        if (root == null) return;
        visit(root.left, val);
        current = root;
        if (find(r, val - root.val)) {res = true; return;}
        visit(root.right, val);
    }
    
    private boolean find(TreeNode root, int value) {
        if (root == null) return false;
        if (root == current) return false;
        if (root.val == value ) return true;
        return  (value > root.val) ? find(root.right, value): find(root.left, value);
    }
}

正经思路， 中序遍历转化为排序数组， 使用双指针查找

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    private List<Integer> res = new ArrayList<>(64);
    
    public boolean findTarget(TreeNode root, int k) {

        visitTree(root);
        
        int low = 0, high = res.size() - 1;
        while (low < high) {
            int sum = res.get(low) + res.get(high);
            if (sum == k) return true;
            if (sum < k) low++;
            else high--;
        }
        return false;
        
    }
    

    
    private void visitTree(TreeNode root) {
        if (root == null) return;
        visitTree(root.left);
        res.add(root.val);
        visitTree(root.right);        
    }

}
发表更新工作 / 挑战6 分钟读完 (大约888个字)

[项目] 根据权限查询时避免角色切换遇到的坑

前情概要

1. 问题背景

使用多个角色查询列表时，会遇到两个维度的不同点：

  • 行维度：多个角色能够看到行的并集，sql需要多次查询取并集，之后还要去重分页排序
  • 列维度：如果不同角色可见列不同，计算出当前行能看到列的并集

举一个例子：

假设存在一个登录员工拥有两个角色：

  1. 长期激励负责人：能看到拥有长期激励的人（行维度），能看到基本信息和长期激励信息（列维度）
  2. 薪酬负责人：能看到低职级的人（行维度），能看到基本信息和薪酬信息（列维度）

那么，在列表中他能看见：

基本信息 薪酬信息 长期激励信息
低职级/无长期激励 √ √ x
低职级/长期激励 √ √ √
高职级/无长期激励 x x x
高职级/长期激励 √ x √

2. 实际遇到的问题（困难重重）

基本思路已经在前期概要里介绍，本人已经实践了一段时间，挖了两个深坑正在解决中。

性能问题（已解决）

最开始的实现中数据是一条一条读取的，同时薪酬字段属于加密信息，使用了第三方微服务提供解密，读取字段多+解密字段多 导致了在百条分页的情况下接口在超时的边缘不断试探。。。

解决方案：

  • 合并查询sql,批量查询数据
  • 合并解密请求,批量调用解密微服务

因为之前为了方便我们解密使用了mybatis的TypeHandler做到字段隐式加解密，目前我们的做法是对于单条数据的加解密，还是保持原来的typeHandler做法，而对批量数据处理，重新写一套数据实体，同时使用mybatis的拦截器对查询的批量数据做批量解密的处理。具体做法可以参见我的另一片文章：【片段】 Mybatis ResultSetHandler 实践-续

批量查询带来的问题

批量查询返回的列表中列字段都是一致的，而我们的需求是不同的行能看见不同的列字段，把批量查询出来的列表直接返回是有问题的，这个问题因为疏忽导致了线上的一次故障。

所以目前的思路是先做一次数据批量预取，之后在对列字段做处理，隐藏掉不能看见的字段。

3. 总结

没有想到当时想解决权限查询时避免角色切换这个问题时会遇到这么多困难，想法是正确的，在实际执行时还是困难重重。值得欣慰的在最开始的时候思路和方向都是正确的，同时也把其中遇到的各种问题和心得记录了下来，经过层层积累，才到达现在的高度。

[]: https://blog.yamato.moe/2018/11/06/2018-11-06-biz/ “根据权限查询时避免角色切换的一种思路”
[]: https://blog.yamato.moe/2019/04/04/Mybatis%20ResultSetHandler_2019-04-04%20%E7%BB%AD/ “【片段】 Mybatis ResultSetHandler 实践-续”
[]: https://blog.yamato.moe/2019/01/09/Mybatis%20ResultSetHandler_2019-01-09/ “【片段】 Mybatis ResultSetHandler 实践”

关注我

链接

分类

最新文章

归档

标签

IM系统1
aop1
java14
linux1
mybatis5
redis1
spring2
中间件2
代码23
分布式7
团队1
工作24
感悟3
搜索1
操作系统1
数据库5
架构2
消息3
消息队列2
算法7
缓存6
读书8
×