前言

你是我见过许许多多第一次的人，露天街第一个对我伸出援手的人，第一个带我去眺望风景的人，让我第一次涌现各种各样感情的人，第一个让我依靠的人，第一个打败我的人，真要细数根本说不完，所以呢，第一个喜欢上的人当然也是你了，这点事情自己好歹自己察觉到啊，笨蛋。

整体评价

国庆中，唯一能参加的一场，很珍惜，可惜没达到预想的成绩，小小遗憾一下。

所贴代码，都是比赛中第一版AC代码，不好之处，请包容。

1. 删除字符使频率相同

大概写到一半，意识到这题易错，迅速转为暴力解，真的是抖机灵了一把

class Solution {
    
    boolean check(char[] buf, int idx) {
        int[] hash = new int[26];
        for (int i = 0; i < buf.length; i++) {
            if (i == idx) continue;
            int p = buf[i] - 'a';
            hash[p]++;
        }
        
        int a = -1;
        for (int i = 0; i < 26; i++) {
            if (hash[i] > 0) a = hash[i];
        }
        if (a == -1) return true;
        
        for (int i = 0; i < 26; i++) {
            if (hash[i] > 0 && hash[i] != a) return false;
        }
        return true;
    }
    
    public boolean equalFrequency(String word) {    
        
        char[] buf = word.toCharArray();
        for (int i = 0; i < buf.length; i++) {
            if (check(buf, i)) return true;
        }
        // 易错题
        return false;
        
        
    }
    
}

2. 最长上传前缀

均摊 $O (1)$ ，这场周赛中，写的最优雅的代码，感谢力扣君

class LUPrefix {

    int n;
    int[] arr;
    int ptr = 0;
    
    public LUPrefix(int n) {
        this.n = n;
        this.arr = new int[n + 1];
    }
    
    // 有意思
    public void upload(int video) {
        this.arr[video] = 1;
        
        while (ptr < n && arr[ptr + 1] == 1) {
            ptr++;
        }
    }
    
    public int longest() {
        return ptr;
    }
    
}

珂朵莉树版, 模板详细参考 https://leetcode.cn/circle/discuss/ScJICj/

class LUPrefix {

    static
    class ODTTree {

        static class Node {
            int l, r, v;
            public Node(int l, int r, int v) {
                this.l = l;
                this.r = r;
                this.v = v;
            }
        }

        TreeMap<Integer, Node> tree = new TreeMap<>();
        
        public ODTTree() {
        }

        public ODTTree(int l, int r, int v) {
            tree.put(l, new Node(l, r, v));
        }

        public void split(int l) {
            Map.Entry<Integer, Node> prev = tree.floorEntry(l);
            if (prev == null || prev.getKey() == l || prev.getValue().r < l) return;

            Node cur = prev.getValue();
            int r = cur.r, v = cur.v;

            tree.remove(prev.getKey());
            tree.put(prev.getKey(), new Node(cur.l, l - 1, v));
            tree.put(l, new Node(l, r, v));
        }

        public void merge(int l, int r, int v) {
            this.split(l);
            this.split(r + 1);

            // l闭区间, r+1开区间
            tree.subMap(l, r + 1).clear();

            // 再做一个合并
            //      和前一个元素进行合并
            Map.Entry<Integer, Node> prev = tree.floorEntry(l - 1);
            if (prev != null && prev.getValue().v == v && prev.getValue().r == l - 1) {
                tree.remove(prev.getKey());
                l = prev.getKey();
            }

            //      和后一个区间进行合并
            Map.Entry<Integer, Node> next = tree.ceilingEntry(r + 1);
            if (next != null && next.getValue().v == v && next.getKey() == r + 1) {
                tree.remove(next.getKey());
                r = next.getValue().r;
            }

            tree.put(l, new Node(l, r, v));
        }

        // 扩展longest() 接口
        public int longest() {
            Map.Entry<Integer, Node> cur = tree.firstEntry();
            if (cur == null || cur.getKey().intValue() != 1) return 0;
            return cur.getValue().r;
        }

    }

    ODTTree odt = new ODTTree();

    public LUPrefix(int n) {

    }
    
    public void upload(int video) {
        odt.merge(video, video, 1);
    }
    
    public int longest() {
        return odt.longest();
    }
}

注：好像是双 100%，哈哈，好高兴

3. 所有数对的异或和

我总觉得哪里做过，然后一直在回忆，又不愿意查看以前写过的代码, 就一直卡在那边，真的太累了。

或者直接模拟一下，结果就出来了.

class Solution {
    
    // 好像做过
    // 3 * 4 = 12个， (0 ^ 1) = 1 (0^0)
    // 
    public int xorAllNums(int[] nums1, int[] nums2) {
    
        int[] tabs2 = new int[30];
        
        for (int v: nums2) {
            for (int i = 0; i < 30; i++) {
                if ((v & (1 << i)) != 0) {
                    tabs2[i]++;
                }
            }
        }
        
        int[] tabs1 = new int[30];
        
        for (int v: nums1) {
            for (int i = 0; i < 30; i++) {
                if ((v & (1 << i)) != 0) {
                    tabs1[i]++;
                }
            }
        }
        
        int ans = 0;
        for (int i = 0; i < 30; i++) {
            int t = tabs1[i] * (nums2.length - tabs2[i]) + (tabs2[i]) * (nums1.length - tabs1[i]);
            if ((t % 2) == 1) {
                ans |= (1 << i);
            }
        }
    
        return ans;
        
    }
    
}

4. 满足不等式的数对数目

首先是等于转换

$n u m s 1 [i] + n u m s 2 [j] <= n u m s 2 [i] + n u m s 2 [j] + d i ff$

$n u m s 1 [i] - n u m s 2 [i] <= n u m s 1 [j] - n u m s 2 [j] + d i ff$

令 $f (i) = n u m s 1 [i] - n u m s 2 [i]$

即 $f (i) < f (j) + d i ff$ ， $i < j$ 的总个数

这题就很直接了，

直接上树状数组，不过还得离散化一把。

不过我真的不想这么用，挣扎了一会，最后还是妥协了。

class Solution {

    static class BIT {
        int n;
        int[] arr;
        public BIT(int n) {
            this.n = n;
            this.arr = new int[n + 1];
        }

        int lowbit(int x) {
            return x & (-x);
        }

        void update(int p, int x) {
            while (p <= n) {
                this.arr[p] += x;
                p += lowbit(p);
            }
        }

        int query(int p) {
            int res = 0;
            while (p > 0) {
                res += arr[p];
                p -= lowbit(p);
            }
            return res;
        }

    }

    // C++ 有优势
    // 树状数组吗？
    public long numberOfPairs(int[] nums1, int[] nums2, int diff) {

        TreeSet<Long> sets = new TreeSet<>();

        // 定义函数F(函数)
        int n = nums1.length;
        long[] f = new long[n];
        for (int i = 0; i < n; i++) {
            f[i] = (long)nums1[i] - (long)nums2[i];

            sets.add(f[i]);
        }

        TreeMap<Long, Integer> idxMap = new TreeMap<>();
        int ptr = 1;
        for (Long v: sets) {
            idxMap.put(v, ptr);
            ptr++;
        }

        BIT bit = new BIT(ptr - 1);

        // *) 
        long ans = 0;

        // 离散化 + BIT
        for (int i = 0; i < n; i++) {
            long tv = f[i] + diff;

            // 前面 <= 的个数     
            // 统计计算
            Map.Entry<Long, Integer> e = idxMap.floorEntry(tv);
            if (e != null) {
                ans += bit.query(e.getValue());
            }

            int p = idxMap.get(f[i]);
            bit.update(p, 1);
        }

        return ans;
    }
}