ARTS打卡-第二周

发表于 | 分类于

Algorithm：每周至少做一个 leetcode 的算法题

518. 零钱兑换 II

该题目是一道非常经典的动态规划算法题，一种完全背包的解法，每一种零钱能凑出来的金额的方式数，都从小金额一直统计到大金额，例：要凑5块钱，有1、2、5块三种零钱，那么可以创建一个大小为比5块数值大1的数组，即new int[amount+1]，然后统计1块至5块，每一个金额，1块钱零钱能凑出来的方式数量，得到的结果为[1,1,1,1,1,1]（第一个元素默认为1，因为要凑得金额如果为0，则肯定也只有一种方式，也就是什么零钱都不用），然后第二步是统计2块钱零钱能凑出来的方式数量，循环至索引为2的时候，也就是统计金额2的凑成方式数，那么数量则为原有1块钱凑成金额2的1种方式 加上 当前2块钱凑成的1种方式 等于2种方式，这时候结果是[1,1,2,1,1,1]，然后循环至3的时候，也就是统计金额3的凑成方式数，那么数量则为原有1块钱凑成金额3的1种方式 加上 金额1凑成的方式数量（因为3-2之后得到的1，也就是说1有多少种凑成方式，那么相应的3就有多少种（和零钱2凑成金额3）的方式），这时候结果是[1,1,2,2,1,1]，周而复始，到4的时候结果是[1,1,2,2,3,1]，到5的时候结果是[1,1,2,2,3,3]，然后统计下一个零钱5块的时候，得到的结果就是[1,1,2,2,3,4]

1
2
3
4
5
6
7
8
public int change(int amount, int[] coins) {
    int bb[] = new int[amount+1];
    bb[0] = 1;
    for (int coin : coins)
        for (int i=coin;i < bb.length;i++)
            bb[i] = bb[i] + bb[i - coin];
    return bb[amount];
}

501. 二叉搜索树中的众数

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
TreeNode pre = null;
int current = 0;
int max = 0;
public int[] findMode(TreeNode root) {
    List<Integer> maxList = new ArrayList<>();
    dg(root,maxList);
    int []zs = new int[maxList.size()];
    for (int i = 0; i < maxList.size();i++)
        zs[i] = maxList.get(i);
        
    return zs;
}

public void dg(TreeNode root, List <Integer> maxList) {
    if (root != null) {
        
        dg(root.left, maxList);
        
        if (pre != null && pre.val == root.val) {
            current++;
        } else {
            current = 1;
        }
        
        if (current > max) {
            max = current;
            maxList.clear();
            maxList.add(root.val);
        } else if (current == max) {
            maxList.add(root.val);
        }
        
        pre = root;
        
        dg(root.right, maxList);
        
    }
}

Review：阅读并点评至少一篇英文技术文章

Tip：学习至少一个技术技巧

java的SPI机制

java的spi机制，是开发人员通过在jar包的META-INF/services目录底下，创建一个class全路径相同名称（不包含.class）的文件，例

1
META-INF/services/com.alibaba.csp.sentinel.init.InitFunc

并在文件内以行为单位，每个单位为一个class的全路径（不包含.class），例

1
2
com.alibaba.csp.sentinel.transport.init.CommandCenterInitFunc
com.alibaba.csp.sentinel.transport.init.HeartbeatSenderInitFunc

然后使用ServiceLoader的load方法，就能通过把services目录下，与InitFunc接口的全路径名称

1
com.alibaba.csp.sentinel.init.InitFunc

相同名称的文件内，实现了InitFunc接口的所有类都实例化并加载为loader实例（可遍历的集合）

1
2
3
4
ServiceLoader<InitFunc> loader = ServiceLoader.load(InitFunc.class);
for (InitFunc initFunc : loader) {
    
}

很多人看到这里，会想，这样做有什么意义呢？的确，我这里还没说完，到重点了。

当我们的代码是一个通讯服务，分为了三个jar包，A为核心core，实现了具体的通讯信息处理逻辑，而B和C是负责通讯的实现，其中B为Netty实现，C为简单的SocketServer实现，当我们只引入B或者C的其中一个Jar，而A在调用

1
ServiceLoader.load(InitFunc.class)

后，会去加载B或者C的jar下

1
META-INF/services/com.alibaba.csp.sentinel.init.InitFunc

文件内的InitFunc实现类实例化，如果引入的是B，那么我们的通讯服务就会以Netty实现，反之则是SocketServer，这样，我们就能利用spi机制，通过引入的jar包而选择具体的实现方式。

Share：分享一篇有观点和思考的技术文章