ARTS计划2021/02

2021年第2周。本周ARTS计划继续。

Algorithm 滑动窗口

leetcode上刷到一个有趣的评论:每天起床第一句,先给自己用个技。每次多生一次气,就要说声对不起。魔镜魔镜看看我,我的客人在哪里。努力我要努力,我要顾客都满意。
什么鬼,不是算法题的网站吗,怎么还有混子来着编顺口溜来着,哈哈哈哈

一个有场景的题目,爱生气的老板 https://leetcode-cn.com/problems/grumpy-bookstore-owner/
今天,书店老板有一家店打算试营业 customers.length 分钟。每分钟都有一些顾客(customers[i])会进入书店,所有这些顾客都会在那一分钟结束后离开。
在某些时候,书店老板会生气。 如果书店老板在第 i 分钟生气,那么 grumpy[i] = 1,否则 grumpy[i] = 0。 当书店老板生气时,那一分钟的顾客就会不满意,不生气则他们是满意的。
书店老板知道一个秘密技巧,能抑制自己的情绪,可以让自己连续 X 分钟不生气,但却只能使用一次。
请你返回这一天营业下来,最多有多少客户能够感到满意的数量。

示例:

1
2
3
4
5
输入:customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3
输出:16
解释:
书店老板在最后 3 分钟保持冷静。
感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.

这个题目的思路就是先把生气的客人组成一个数组,然后用X大小的滑动窗格算出来最多的X个组不满意的客人,然后就得到了答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int maxSatisfied(int[] customers, int[] grumpy, int X) {
int result = 0;
// 不满意的客户数组
for (int i = 0; i < customers.length; i++) {
if(grumpy[i] == 0) {
result += customers[i];
customers[i] = 0;
}
}
int max = 0;
int sum = 0;
//窗口长度为X,窗口在向前滑动一位之前,需要将窗口中的最左边的一位数减掉
for (int i = 0; i < customers.length; i++) {
if (i >= X) {
sum = sum + customers[i] - customers[i-X];
if (sum >= max) {
max = sum;
}
} else {
sum = sum + customers[i];
}
}
return result + max;
}

Review

本周阅读文档-无

Tips - Spring天然支持的策略模式

本来这个事情我之前就知道了,也用过两次,印象不深。前两天我同事说他发现了这个好用的东西,说Spring如果Autoried的是一个以String作为key的Map,那Spring会把对应的id或者name作为key,把所有由Spring管理的对应的匹配value类型的对象作为这个map的value。我也就记录这个作为Tips吧。

比如:员工的数据权限包括“本级”、“本级和子级”、“所有权限”,“自定义权限集合”四种情况,和数据库中记录对应如下表。

数据权限 代码
所有权限 1
本级 2
本级和子级 3
自定义权限集合 4

每次写代码查询用户的所有权限都需要根据用户属性获取对应的策略来完成,可以这样做。

1
2
3
4
5
6
7
8
9
@Service
public class DataScopeContext {
@Autowired
private final Map<String, DataScopeHandler> strategyMap = new ConcurrentHashMap<>();
// 根据用户权限类型获取角色的数据权限
public List<Integer> getDeptIdsForDataScope(RoleDTO roleDto, Integer type) {
return strategyMap.get(String.valueOf(type)).getDeptIds(roleDto, DataScopeTypeEnum.valueOf(type));
}
}
1
2
3
4
5
6
7
8
9
10
public interface DataScopeHandler {

/**
* 根据获取用户数据权限部门id列表
* @param roleDto
* @param dataScopeTypeEnum
* @return
*/
List<Integer> getDeptIds(RoleDTO roleDto, DataScopeTypeEnum dataScopeTypeEnum);
}

对应着有四种图表中的实现

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
@Component("1")
public class AllDataScope implements DataScopeHandler {
@Override
public List<Integer> getDeptIds(RoleDTO roleDto, DataScopeTypeEnum dataScopeTypeEnum) {
// todo 获取所有的部分列表...
}
}

@Component("2")
public class ThisLevelDataScope implements DataScopeHandler {

@Override
public List<Integer> getDeptIds(RoleDTO roleDto, DataScopeTypeEnum dataScopeTypeEnum) {
// todo 获取用户所在部门的id
}
}

@Component("3")
public class ThisLevelChildenDataScope implements DataScopeHandler {

@Override
public List<Integer> getDeptIds(RoleDTO roleDto, DataScopeTypeEnum dataScopeTypeEnum) {
// todo 获取用户所在部门以及其子部门的id列表
}
}

@Component("4")
public class CustomizeDataScope implements DataScopeHandler {
@Override
public List<Integer> getDeptIds(RoleDTO roleDto, DataScopeTypeEnum dataScopeTypeEnum) {
// todo 获取为用户自定义的部门id列表
}
}

后来朋友还给我看了Spring官方在@Autowried的注释里写了对于这一功能的描述

1
2
3
4
5
6
7
8
9
10
11
12
/**
* ......
* In case of a {@link java.util.Collection} or {@link java.util.Map} dependency type,
* the container autowires all beans matching the declared value type. For such purposes,
* the map keys must be declared as type String which will be resolved to the corresponding
* bean names. Such a container-provided collection will be ordered, taking into account
* {@link org.springframework.core.Ordered}/{@link org.springframework.core.annotation.Order}
* values of the target components, otherwise following their registration order in the
* container. Alternatively, a single matching target bean may also be a generally typed
* {@code Collection} or {@code Map} itself, getting injected as such.
* ......
*/

我就好奇跟了一下代码,这些将写在Share环节中。

Share

Spring的Bean的生命周期多次在面试中被问到,还经常被问到如果处理的循环依赖,其实在Bean加载的过程中针对Map 和 Collection还专门做了一些事情,我之前读源码的时候也没看到这一块。

在Spring做到刷新容器的时候,inject方法做针对@Autowired的注解对象去执行beanFactory.resolveDependency,然后执行doResolveDependency方法(一般Spring中的具体执行都是使用do开头的,这是他的风格),在这个方法中,有这么一行

1
2
3
4
5
// 处理数组、集合、Map等
Object multipleBeans = resolveMultipleBeans(descriptor, beanName, autowiredBeanNames, typeConverter);
if (multipleBeans != null) {
return multipleBeans;
}
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
@Nullable
private Object resolveMultipleBeans(DependencyDescriptor descriptor, @Nullable String beanName,
@Nullable Set<String> autowiredBeanNames, @Nullable TypeConverter typeConverter) {

final Class<?> type = descriptor.getDependencyType();

if (descriptor instanceof StreamDependencyDescriptor) {
Map<String, Object> matchingBeans = findAutowireCandidates(beanName, type, descriptor);
if (autowiredBeanNames != null) {
autowiredBeanNames.addAll(matchingBeans.keySet());
}
Stream<Object> stream = matchingBeans.keySet().stream()
.map(name -> descriptor.resolveCandidate(name, type, this))
.filter(bean -> !(bean instanceof NullBean));
if (((StreamDependencyDescriptor) descriptor).isOrdered()) {
stream = stream.sorted(adaptOrderComparator(matchingBeans));
}
return stream;
}
else if (type.isArray()) {
Class<?> componentType = type.getComponentType();
ResolvableType resolvableType = descriptor.getResolvableType();
Class<?> resolvedArrayType = resolvableType.resolve(type);
if (resolvedArrayType != type) {
componentType = resolvableType.getComponentType().resolve();
}
if (componentType == null) {
return null;
}
Map<String, Object> matchingBeans = findAutowireCandidates(beanName, componentType,
new MultiElementDescriptor(descriptor));
if (matchingBeans.isEmpty()) {
return null;
}
if (autowiredBeanNames != null) {
autowiredBeanNames.addAll(matchingBeans.keySet());
}
TypeConverter converter = (typeConverter != null ? typeConverter : getTypeConverter());
Object result = converter.convertIfNecessary(matchingBeans.values(), resolvedArrayType);
if (result instanceof Object[]) {
Comparator<Object> comparator = adaptDependencyComparator(matchingBeans);
if (comparator != null) {
Arrays.sort((Object[]) result, comparator);
}
}
return result;
}
else if (Collection.class.isAssignableFrom(type) && type.isInterface()) {
Class<?> elementType = descriptor.getResolvableType().asCollection().resolveGeneric();
if (elementType == null) {
return null;
}
Map<String, Object> matchingBeans = findAutowireCandidates(beanName, elementType,
new MultiElementDescriptor(descriptor));
if (matchingBeans.isEmpty()) {
return null;
}
if (autowiredBeanNames != null) {
autowiredBeanNames.addAll(matchingBeans.keySet());
}
TypeConverter converter = (typeConverter != null ? typeConverter : getTypeConverter());
Object result = converter.convertIfNecessary(matchingBeans.values(), type);
if (result instanceof List) {
Comparator<Object> comparator = adaptDependencyComparator(matchingBeans);
if (comparator != null) {
((List<?>) result).sort(comparator);
}
}
return result;
}
else if (Map.class == type) {
ResolvableType mapType = descriptor.getResolvableType().asMap();
Class<?> keyType = mapType.resolveGeneric(0);
if (String.class != keyType) {
return null;
}
Class<?> valueType = mapType.resolveGeneric(1);
if (valueType == null) {
return null;
}
Map<String, Object> matchingBeans = findAutowireCandidates(beanName, valueType,
new MultiElementDescriptor(descriptor));
if (matchingBeans.isEmpty()) {
return null;
}
if (autowiredBeanNames != null) {
autowiredBeanNames.addAll(matchingBeans.keySet());
}
return matchingBeans;
}
else {
return null;
}
}

这里就分情况分别注入,再往下看findAutowireCandidates就是获取对象了,我就没继续看。