arts-20210328

Algorithm

• 题目: 组合总和
• 解题思路：
  1. 回溯，关键是招够 n 个数，并且不能重复，没法直接遍历，因为循环层数不固定
  2. 遍历过程中，如果后选择的数字肯定比已经选择的数字大，即遍历时从上次选择的数字的后一个数字开始选，可以保证不重不漏
  3. 回溯代码要素
  4. dfs 访问决策树
     • 路径：暂时选中的数字
     • 选择列表：还没遍历过的数字
     • 选择动作：
       1. 将遍历到的元素 i 添加到 selected 列表中
       2. 更新选择的数字之和 sum， sum += 1
       3. 将上次选择的结果更新成 i
     • 撤销选择
       1. 从 sum 中将当前元素减掉
       2. 删除选择列表中最后一个数字
       3. 将上次选择结果更新成新的最后一个元素
     • 剪枝
       1. 在尝试添加遍历到的元素 i 之前，先检查 sum + i > n 是否成立，如果成立则剪枝
• 代码

public class CombinationSum {

    public List<List<Integer>> combinationSum3(int k, int n) {
        Args args = new Args(k, n);

        dfs(args);

        return args.combinations;
    }

    private void dfs(Args args) {
        if (args.k == args.selected.size()) {
            if (args.sum == args.n) {
                args.combinations.add(new ArrayList<Integer>(args.selected));
            }
            return;
        }

        for (int i = args.lastSelected + 1; i <= 9; i++) {
            if (args.sum + i > args.n) {
                continue;
            }
            args.selected.add(i);
            args.sum += i;
            args.lastSelected = i;

            dfs(args);

            args.sum -= i;
            args.selected.remove(args.selected.size() - 1);
            args.lastSelected = args.selected.isEmpty() ? 0 : args.selected.get(args.selected.size() - 1);
        }
    }

    public static class Args {
        List<List<Integer>> combinations = new ArrayList<List<Integer>>();
        List<Integer> selected= new ArrayList<Integer>(10);
        int k;
        int n;
        int sum = 0;
        int lastSelected = 0;

        public Args(int k, int n) {
            this.k = k;
            this.n = n;
        }
    }
}

• 一个小坑
  1. 一开始总发现返回的结果中只有一个元素的 List<List>，并且这个元素是个空列表，结果没加进去
     • 原因: add 结果时是传引用， 因此后面再回溯时就把 combinations 结果里的元素全给删掉了
     • 解决办法：往 combinations 里添加结果时新建一个 list，把符合条件的选择列表复制过去

Review

原文地址：Prometheus - Service Discovery

本文介绍了为 Prometheus 开发服务发现机制时，需要注意的问题，有几个要点

1. 服务发现组件应该是个很通用的组件，逻辑很少，只关注将“服务元数据”暴露给 prometheus
2. 对于自定义的需求，推荐使用 “FileSD”
3. SD 暴露给 Prometheus 时需要注意几个问题
   1. SD 应该通过 KV 暴露给 Prometheus 元数据，pattern 为 __meta_<sdname>_<key>，地址应该通过 __address__标签来暴露，包含 host 和 port,数组应该 join 到一个字符串里，例如 [a,b,c] 应该是 ,a,b,c,
   2. SD 本身应该没什么逻辑，过滤、转换等逻辑应该通过 relabel 来实现
   3. SD 过程中如果出错，应该返回旧的发现结果，而不是部分结果

      If there is a failure while processing talking to the SD, abort rather than returning partial data. It is better to work from stale targets than partial or incorrect metadata.

   4. 一个 SD 如果有多种类型，应该通过配置文件来显示指定类型，而不是一个大的 SD 通过 relabel 来过滤，例如 kubernetes
   5. SD 应该倾向发现所有潜在的监控目标

• 总结

1. SD 应该只关注如何发现监控目标，并且 SD 暴露出来的应该是最原始的元数据
2. 发现 target 元数据和基于元数据进行过滤、转换的事情应该分离开，SD 和 relabel 配合紧密

Tips

1. 遇到问题要弄清楚背后的原因，不要只满足于现象本身
2. 重要的事情，及时加到日程安排里，防止遗忘、对外可见
3. 自己不熟悉的事情，准备好问题，提早找更资深的人请教往往会更高效