arts-20210405

Algorithm

• 题目：给定一个数组（含重复元素），返回这些元素的不重复的全排列
• 题目地址：https://leetcode-cn.com/problems/permutations-ii/submissions/
• 思路：
  1. 当数组元素没有重复时，直接回溯数组即可得到不重复的全排列，因此一开始想到了最粗暴的解法，即在将选择路径加到结果之前做一个判断，判断这个结果是不是已经存在，如果存在则直接跳过
• 代码实现：

class Solution {

        public List<List<Integer>> permuteUnique(int[] nums) {
        if (nums.length == 0) {
            return Collections.emptyList();
        }

        if (nums.length == 1) {
            List<Integer> l = new ArrayList<Integer>(1);
            l.add(nums[0]);
            return Collections.singletonList(l);
        }

        Set<List<Integer>> ret = new HashSet<List<Integer>>(fact(nums.length));
        List<Integer> path = new ArrayList<Integer>(nums.length);
        // boolean default to false
        boolean[] selected = new boolean[nums.length];

        permute(ret, nums, path, selected);

        return new ArrayList<List<Integer>>(ret);
    }

    private void permute(Set<List<Integer>> ret, int[] nums, List<Integer> path, boolean[] selected) {
        if (path.size() == nums.length) {
            if (!ret.contains(path)) {
                ret.add(new ArrayList<Integer>(path));
            }
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            // select
            if (selected[i]) {
                continue;
            }

            path.add(nums[i]);
            selected[i] = true;

            permute(ret, nums, path, selected);

            // unselect
            path.remove(path.size() - 1);
            selected[i] = false;
        }
    }

    private int fact(int n) {
        if (n == 0) {
            return 0;
        }
        int f = 1;
        for (int i = 2; i <= n; i++) {
            f *= i;
        }
        return f;
    }
}

• Leetcode 大佬解法
  • 思路：由于输入的数组存在重复，假设 i,j 位置的元素重复，则排列时选择 i，j 和 j，i 就是重复的排列，应该避免这种情况
    1. 回溯之前先对输入的数组 nums 排序，让重复的元素相邻
    2. 回溯剪枝：对于已知重复的元素（nums[i] == nums[i-1]），只有当 nums[i - 1] 被选择了的时候才选择 nums[i]
  • 代码

/*
 * 这道题的思路和46的全排列一样，都是通过递归回溯的方式
 * 但是这道题原数组会包含重复数字，这是要解决的问题
 * 例如1，1，2， 以递归的方式，情况1: 第一个数取第一个1 第二个数取第二个1，  和情况2: 第一个数取第二个1 第二个数取第一个1
 * 这两种情况需要避免
 * 所以题目在一开始对nums进行排序，第二个数在加入数字的时候，该数字不能是首次被加入，换句话说，也就是首次被加入的重复数据才算数，浅层的递归调用会生效，因为更快访问到这个重复数据，而深层次的则直接抛弃，因为在之前已经计算过了
*/

class Solution {
    boolean[] vis;

    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        List<Integer> perm = new ArrayList<Integer>();
        vis = new boolean[nums.length];
        Arrays.sort(nums);
        backtrack(nums, ans, 0, perm);
        return ans;
    }

    public void backtrack(int[] nums, List<List<Integer>> ans, int idx, List<Integer> perm) {
        if (idx == nums.length) {
            ans.add(new ArrayList<Integer>(perm));
            return;
        }
        for (int i = 0; i < nums.length; ++i) {
            if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
                continue;
            }
            perm.add(nums[i]);
            vis[i] = true;
            backtrack(nums, ans, idx + 1, perm);
            vis[i] = false;
            perm.remove(idx);
        }
    }
}

Review

原文地址：Anomaly Detection in VictoriaMetrics

有些指标本身波动范围很大，很难通过一个固定的阈值来设置报警发现问题，因此 vm 推出了 vmanomaly 组件来解决这一问题。

原理是对于周期性波动的指标，根据历史数据来预测合法取值的范围，当实际取值不再合法范围内时，认为检测到异常。

Tips

1. 在做系统设计时，要避免过度追求自动扩展，而把系统搞的很复杂，更好的做法是先通过实验确定组件的容量，如果单机能搞定就先不搞集群，保证架构简单

• 起因：在设计 vmagent 的采集架构时，一开始想了完整的 target 分发方案，后来对 vmagent 做了性能测试后发现，单机就能抗住目前的负载，扩展 3-4 倍都没问题，也就不必再做负责的分发方案了
• 总结：先知道量化的能力上限，再来做设计更有底气