前言

如果幸福有颜色, 那一定是被终末之红染尽的苍蓝。

T1 化学反应

就是模拟，好像没啥好讲的.

Java

class Solution {
    
    public int lastMaterial(int[] material) {

        PriorityQueue<Integer> pp = new PriorityQueue<>((a, b) -> Integer.compare(b, a));
        
        for (int m: material) {
            pp.offer(m);
        }
        
        while (pp.size() >= 2) {            
            int m1 = pp.poll();
            int m2 = pp.poll();
            if (m1 > m2) {
                pp.offer(m1 - m2);
            }             
        }
        return pp.size() == 1 ? pp.peek() : 0;
        
    }
    
}

T2 销售出色区间

这题挺有意思, 我大致说下这一类的思路吧。

如果我们把 sale > 8, 视为1, <= 8, 视为-1，那就演变为一个前缀和问题.

设 f(i) 为数组[0, i)前缀和.

i < j, f(j + 1) - f(i) > 0, 是满足需求的解。

进而构造，g(i) = f(i), g(i)只和变量i相关。

变换 f(j + 1) - f(i) > 0 => f(i) < f(j + 1) => g(i) < g(j + 1)

这题的最优解等价于固定j, 寻找满足最小的i，满足 g(i) < g(j + 1)

遇到这种，基本可以等价构造单调队列（严格递减），然后枚举j，二分寻求下界，就是最优解, 当然这边也方便优化为双指针处理。

这边为啥要引入G函数，主要是为了泛化，比如这题如果改为，销售良好的一天能抵两天休息日，这才是这题的最大意义。

Java

class Solution {

    // f(i) < f(j + 1)
    public int longestESR(int[] sales) {

        int ans = 0;

        int n = sales.length;

        int[] presum = new int[n + 1];
        for (int i = 0; i < n; i++) {
            presum[i + 1] = presum[i] + (sales[i] > 8 ? 1 : -1);
        }

        // 构建单调队列 (只有更小)
        List<Integer> arr = new ArrayList<>();

        // 满足这个条件，最小的值
        for (int i = 0; i < n; i++) {
            // 添加
            if (arr.size() == 0 || presum[arr.get(arr.size() - 1)] > presum[i]) {
                arr.add(i);
            }

            // 二分找到下界
            int l = 0, r = arr.size() - 1;
            while (l <= r) {
                int m = l + (r - l) / 2;
                if (presum[arr.get(m)] >= presum[i + 1]) {
                    l = m + 1;
                } else {
                    r = m - 1;
                }
            }

            if (l < arr.size()) {
                ans = Math.max(ans, i - arr.get(l) + 1);
            }
        }

        return ans;

    }

}

T3 重复的彩灯树

本质上树的序列化和反序列化，因为节点数不多。

如果这颗树的节点特别多，那序列化成串，再寻找相同子树的代价就比较大。

这边给一个特征指纹解，说白了就是给每一棵子树赋予一个抽象的特征指纹码。

子树相同，那特征指纹必定相同。反过来，特征指纹相同，不见得子树相同，但这概率很小。

为了减少这种碰撞冲突，可以引入多个hash函数簇。

除了多加hash函数簇之外，需要注意树的结构，如何让它保留结构信息，这一点可以思考一下？

Java

class Solution {

    @FunctionalInterface
    interface TreeHash {
        long hash(String e);
    }

    static class Tuple implements Comparable<Tuple> {
        long[] elements;
        public Tuple(long[] elements) {
            this.elements = elements.clone();
        }
        @Override
        public int compareTo(Tuple o) {
            for (int i = 0; i < elements.length; i++) {
                if (elements[i] != o.elements[i]) {
                    return Long.compare(elements[i], o.elements[i]);
                }
            }
            return 0;
        }
    }

    long[] dfs(TreeNode root, TreeHash[] funcs, TreeMap<Tuple, List<TreeNode>> hash) {

        long[] finger = new long[funcs.length];

        if (root == null) {
            // 返回空节点
            for (int i = 0; i < funcs.length; i++) {
                finger[i] = funcs[i].hash("(x)");
            }        
            return finger;
        }

        long[] lcode = dfs(root.left, funcs, hash);
        long[] rcode = dfs(root.right, funcs, hash);

        for (int i = 0; i < funcs.length; i++) {
            // 添加'(', ')', ',' 可以保留结构信息
            finger[i] = funcs[i].hash(String.format("(%d,%d,%d)", lcode[i], root.val, rcode[i]));
        }

        Tuple tx = new Tuple(finger);
        hash.computeIfAbsent(tx, (a) -> new ArrayList<>()).add(root);

        return finger;
    }


    public List<TreeNode> lightDistribution(TreeNode root) {

        // 可以任意添加 多个hash函数簇
        TreeHash[] funcs = new TreeHash[] {
                (expr) -> expr.hashCode(),
                (expr) -> expr.chars().reduce(0, (a, b) -> a * 17 + b),
                (expr) -> expr.chars().reduce(0, (a, b) -> a * 31 + b),
        };

        TreeMap<Tuple, List<TreeNode>> hash = new TreeMap<>();

        dfs(root, funcs, hash);

        return hash.entrySet().stream().filter(e -> e.getValue().size() >= 2)
                .map(e -> e.getValue().get(0)).collect(Collectors.toList());

    }


}

T4 补给覆盖

妥妥的树形DP，但树形DP也有两种思路。

一种是自底向上，另一个自顶向下(特指状态).

说说自底向上，这边需要引入三种状态.

0: 节点没有补给，子节点也没有覆盖，需要父节点照顾
1: 节点没有补给，但子节点有覆盖
2: 节点本身有

对于空节点的状态处理
(0: inf, 1: 0, 2: inf)

这代码写的比别人要复杂，感觉，具体就不细说了.

class Solution {
    
    // 应该有三种状态 (0, 1, 2)
    // 2:1, 1:不用管, 0:要管
    int[] dfs(TreeNode root) {
        
        if (root == null) {
            return new int[] {Integer.MAX_VALUE / 4, 0, Integer.MAX_VALUE / 4};
        }

        int[] la = dfs(root.left);    
        int[] ra = dfs(root.right);


        int x2 = la[0] + ra[0] + 1;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                x2 = Math.min(la[i] + ra[j] + 1, x2);
            }
        }

        int x1 = la[2] + ra[2];
        for (int i = 1; i < 3; i++) {
            x1 = Math.min(la[2] + ra[i], x1);
            x1 = Math.min(la[i] + ra[2], x1);
        }

        int x0 = la[1] + ra[1];
        return new int[] {x0, x1, x2};            

    }
    
    public int minSupplyStationNumber(TreeNode root) {
        int[] res= dfs(root);
        return Math.min(res[1], res[2]);
    } 
    
}