2025-07-24

Leetcode Daily 20250718-20250724

Leetcode 20250718到20250724每日一题的记录，使用Java解题

2163. 删除元素后和的最小差值

20250718
题目链接

参考：官方题解

思路

为了使前 $$n$$ 个数减后 $$n$$ 个数的差值最小，要使前 $$n$$ 个数尽可能小，后 $$n$$ 个数尽可能大。

在前 $$n + i$$ 个数中去掉 $$i$$ 个最大值、后 $$2n - i$$ 个数中去掉 $$n - i$$ 个最小值。( $0 \leq i \leq n$ )

维护一个数组代表当前 $$i$$ 下前面数组和的最小值

用大顶堆将前 $$n$$ 个元素入堆。向后遍历，对于之后的每一个数，如果小于当前最大值，将最大值出堆，再将这个数入堆，更新当前和的最小值；如果大于当前最大值则不用操作,和的最小值不变。

用小顶堆将后 $$n$$ 个元素入堆。向前遍历，对于之后的每一个数，如果大于当前最小值，将最小值出堆，再将这个数入堆，更新当前和的最大值；如果小于当前最小值则不用操作，和的最大值不变。实现时这里可以开始更新结果：取上面对应下标的最小值数组与当前和的最大值的差的最小值。不用再用一个数组存最大值了。

Java 大顶堆(优先队列)

PriorityQueue<Integer> pq = new PriorityQueue<>(n, new Comparator<Integer>() {
            @Override
            public int compare(Integer a,Integer b) {
                return b - a;
            }
        }); //优先队列

优先队列相关操作

pq.offer(i)元素入堆
- 与pq.add(i)的区别是：向满的队列加元素时pq.offer(i)会返回false,pq.add(i)会抛出异常
pq.poll()元素出堆并返回当前最大（小）值
- 与pq.remove()的区别是：向空的队列删元素时pq.poll()会返回null,pq.remove()会抛出异常
pq.peek()返回当前最大（小）值
- 与pq.element()的区别是：向空的队列删元素时pq.peek()会返回null,pq.element()会抛出异常

其他

Math.max(a, b)求2个数的最大值，Math.min(a, b)求2个数的最小值，注意只能求2个数

复杂度

时间复杂度：堆操作每次 $O(\log{(N)})$ ，因此总体是 $O(N\log{(N)})$
空间复杂度：堆、数组 $$O(N)$$

代码

class Solution {
    public long minimumDifference(int[] nums) {
        int len = nums.length;
        int n = len / 3;
        long[] minv = new long[n + 1];
        minv[0] = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>(n, new Comparator<Integer>() {
            @Override
            public int compare(Integer a,Integer b) {
                return b - a;
            }
        });

        for (int i = 0; i < n; i++) {
            pq.offer(nums[i]);
            minv[0] += nums[i];
        }
        
        for (int i = n; i < 2 * n; i++) {
            if (nums[i] >= pq.peek()) {
                minv[i - n + 1] = minv[i - n];
            } else {
                minv[i - n + 1] = minv[i - n] + nums[i] - pq.peek();
                pq.poll();
                pq.offer(nums[i]);
            }
        }
        pq = new PriorityQueue<Integer>(n);
        long sum = 0;
        for (int i = 2 * n; i < len; i++) {
            pq.offer(nums[i]);
            sum += nums[i];
        }
        long res = minv[n] - sum;
        for (int i = 2 * n - 1; i >= n; i--) {
            if (nums[i] > pq.peek())  {
                sum = sum + nums[i] - pq.peek();
                pq.poll();
                pq.offer(nums[i]);
            }
            res = Math.min(res, minv[i - n] - sum);
        }
        return res;
    }
}

1233. 删除子文件夹

20250719
题目链接

参考：官方题解
用时前排的代码

解法1 排序

思路

将字符串数组按字典序排序后一定会按照 $$1$$ 个文件夹后面跟着 $$n$$ 个( $n \geq 0$ )该文件夹的子文件夹这种形式。
例如：

/a
/a/b
---
/c/d
/c/d/e
---
/c/f

字典序

$$aa < ab < abc$$

第一个不同的字母小的字典序小
如果一个字符串是另一个字符串的前缀，并且较短，它的字典序较小
$$/ < 数字 < 大写字母 < 小写字母$$ ascii码顺序

复杂度

时间复杂度： $$l$$ 为字符串平均长度，排序 $O(N \log(N))$ ，整体 $O(Nl \log(N))$
空间复杂度：存储结果 $$O(Nl)$$

其他

字符串长度s.length()
字符串子串s.substring(a, b)，从a到b，包括a不包括b
数组排序Arrays.sort(array)

优化

按照字符串长度排序，此时一个字符串的子串必然出现在它之后。

用集合存储结果，如果当前字符串的前缀在集合内则舍弃当前字符串，否则将此字符串加入集合

自定义数组排序Comparator

Arrays.sort(folder, new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                return s1.length() - s2.length();
            }

        });

代码

class Solution {
    public List<String> removeSubfolders(String[] folder) {
        List<String> res = new LinkedList<>();
        Arrays.sort(folder);
        String pref = "*";
        for (String s : folder) {
            if (s.equals("/") || s.contains("//")) {
                continue;
            }
            if (!(s.length() > pref.length() && pref.equals(s.substring(0, pref.length())) && s.charAt(pref.length()) == '/')) {
                pref = s;
                res.add(s);
            }
        }

        return res;
    }
}

优化后

class Solution {
    public List<String> removeSubfolders(String[] folder) {
        List<String> ans = new ArrayList<>();
        Arrays.sort(folder, new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                return s1.length() - s2.length();
            }

        });
        Set<String> set = new HashSet<>();
        for (String f : folder) {
            int n = f.length();
            boolean flag = false;
            for (int i = 1; i < n; i++) {
                if (f.charAt(i) == '/') {
                    String sub = f.substring(0, i);
                    if (set.contains(sub)) {
                        flag = true;
                        break;
                    }
                }
            }
            if (!flag) {
                ans.add(f);
                set.add(f);
            }
        }
        return ans;
    }
}

解法2 前缀树

思路

按照/分割每一个文件夹构造前缀树，在最后一个节点处放置标记。然后DFS，如果遇到标记则返回，并将当前文件夹加入结果。

复杂度

时间复杂度：构造前缀树、DFS需要 $$O(Nl)$$
空间复杂度：存储前缀树需要 $$O(Nl)$$

优化

前缀树的节点可以存储字符串的哈希以提升效率，数据范围规定文件夹只有小写字母，将字符串当作数字，选择一个26及以上的数字当作进制数构造哈希，（虽然感觉碰撞率很高，但是可以通过本题）。使用str.hashCode()时间上会慢一些。
在构造前缀树的时候，如果当前节点存在且有标记，则表示当前文件夹必然是子文件夹，可以直接舍弃当前文件夹。

其他

Map操作

map.putIfAbsent(key, value)，如果key不存在则执行map.put(key, value)；如果key存在则不执行

代码

class Solution {
    class Trie {
        int index;
        Map<Integer, Trie> children;
        public Trie() {
            index = -1;
            children = new HashMap<>();
        }
    }
    public List<String> removeSubfolders(String[] folder) {
        List<String> res = new ArrayList<>();
        Trie root = new Trie();
        Trie cur = root;
        for (int i = 0; i < folder.length; i++) {
            int hash = 0;
            cur = root;
            boolean flag = false;
            
            for (int j = 1; j < folder[i].length(); j++) {
                if (folder[i].charAt(j) == '/') {
                    if (cur.index != -1) {
                        flag = true;
                        break;
                    }
                    cur.children.putIfAbsent(hash, new Trie());
                    cur = cur.children.get(hash);
                    hash = 0;
                } else {
                    hash = hash * 28 + folder[i].charAt(j);
                }
            }
            if (flag) {
                continue;
            }
            cur.children.putIfAbsent(hash, new Trie());
            cur = cur.children.get(hash);
            if (cur.index == -1) {
                cur.index = i;
            }
            
        }

        dfs(root, res, folder);
        return res;
    }

    private void dfs(Trie cur, List<String> res, String[] folder) {
        if (cur.index != -1) {
            res.add(folder[cur.index]);
            return;
        }
        for (Trie t : cur.children.values()) {
            dfs(t, res, folder);
        }
    }
}

1948. 删除系统中的重复文件夹

20250720
题目链接

参考：官方题解
执行用时前排代码

思路

后序遍历整棵树，生成每个节点的序列化子树,如果当前节点的序列化子树在集合中不存在，则将它加入map，设置出现次数为1；如果存在，则次数加 $$1$$ 。

然后DFS整棵树，如果当前节点的序列化子树出现次数大于 $$1$$ ，则不将它加入答案；如果等于 $$1$$ 则将它加入答案。

子树序列化方法：
$$serial(node) = child1(serial(child1))child2(serial(child2))...childn(serial(childn))$$

$$child$$ 之间按照字典序排序

优化1

生成序列化子树时，不使用出现次数来判断，给前缀树节点增加一个删除标记，如果在Map中查询到有节点存在，则删除Map中的节点和当前节点

在DFS时，通过删除标记判断，如果为真则返回

优化2

本题的输入保证了如果有 $$n$$ 个路径，则一定有 $$n$$ 个前缀树节点

如果按照长度对路径数组排序，结果是按照第 $$1$$ 层节点、第 $$2$$ 层节点…直到最后一层节点分布的

从前向后遍历路径数组建树，每次都会新增一个节点

从后向前遍历增加的节点，跳过所有叶节点，生成它的序列化子树，在Map中查询，如果不存在，则将它加入Map；如果存在，则将查询到的节点设置删除标记，将当前节点设置删除标记

对于子节点可以使用TreeMap存储以保证其按字典序排列

设置删除标记的时候要将它的子节点同时设置删除标记。(如果有 $$2$$ 个 $$3$$ 层的树同构，那么必定存在 $$2$$ 个 $$2$$ 层的树同构(即 $$3$$ 层树的子树)，删除 $$3$$ 层同构树前一定删除过它的所有 $$2$$ 层子同构树。)

最后从前向后遍历所有节点，如果该节点没被删除，则可以将路径数组对应下标直接加入答案中

代码

class Solution {
    public List<List<String>> deleteDuplicateFolder(List<List<String>> paths) {
        Trie root = new Trie();
        for (List<String> list : paths) {
            Trie cur = root;
            for (String s : list) {
                cur.children.putIfAbsent(s, new Trie());
                cur = cur.children.get(s);
            }
        }
        Map<String, Integer> freq = new HashMap<>();
        getSerial(root, freq);

        List<List<String>> res = new ArrayList<>();
        List<String> path = new ArrayList<>();
        dfs(root, freq, res, path);
        return res;
    }
    class Trie {
        String serial;
        Map<String, Trie> children;
        public Trie() {
            children = new HashMap<>();
        }
    }

    void getSerial(Trie cur, Map<String, Integer> freq) {
        if (cur.children.isEmpty()) {
            return;
        }
        List<String> cl = new ArrayList<>();
        for (Map.Entry<String, Trie> entry : cur.children.entrySet()) {
            String s = entry.getKey();
            Trie t = entry.getValue();
            getSerial(t, freq);
            cl.add(s + "(" + t.serial + ")");
        }
        Collections.sort(cl);
        StringBuilder sb = new StringBuilder();
        for (String s : cl) {
            sb.append(s);
        }
        cur.serial = sb.toString();
        freq.put(cur.serial, freq.getOrDefault(cur.serial, 0) + 1);
    }

    void dfs(Trie cur, Map<String, Integer> freq, List<List<String>> res, List<String> path) {
        if (freq.getOrDefault(cur.serial, 0) > 1) {
            return;
        }
        if (!path.isEmpty()) {
            res.add(new ArrayList<>(path));
        }
        for (Map.Entry<String, Trie> entry : cur.children.entrySet()) {
            String s = entry.getKey();
            Trie t = entry.getValue();
            path.add(s);
            dfs(t, freq, res, path);
            path.removeLast();
        }
    }
}

优化1：

class Solution {
    public List<List<String>> deleteDuplicateFolder(List<List<String>> paths) {
        Trie root = new Trie();
        for (List<String> list : paths) {
            Trie cur = root;
            for (String s : list) {
                cur.children.putIfAbsent(s, new Trie());
                cur = cur.children.get(s);
            }
        }
        Map<String, Trie> map = new HashMap<>();
        getSerial(root, map);

        List<List<String>> res = new ArrayList<>();
        List<String> path = new ArrayList<>();
        dfs(root, res, path);
        return res;
    }
    class Trie {
        String serial;
        Map<String, Trie> children;
        boolean deleted;
        public Trie() {
            children = new HashMap<>();
            deleted = false;
        }
        public void setD() {
            deleted = true;
        }
    }

    void getSerial(Trie cur, Map<String, Trie> map) {
        if (cur.children.isEmpty()) {
            return;
        }
        List<String> cl = new ArrayList<>();
        for (Map.Entry<String, Trie> entry : cur.children.entrySet()) {
            String s = entry.getKey();
            Trie t = entry.getValue();
            getSerial(t, map);
            cl.add(s + "(" + t.serial + ")");
        }
        Collections.sort(cl);
        StringBuilder sb = new StringBuilder();
        for (String s : cl) {
            sb.append(s);
        }
        cur.serial = sb.toString();
        Trie t = map.get(cur.serial);
        if (t == null) {
            map.put(cur.serial, cur);
        } else {
            t.setD();
            cur.setD();
        }
    }

    void dfs(Trie cur, List<List<String>> res, List<String> path) {
        if (cur.deleted) {
            return;
        }
        if (!path.isEmpty()) {
            res.add(new ArrayList<>(path));
        }
        for (Map.Entry<String, Trie> entry : cur.children.entrySet()) {
            String s = entry.getKey();
            Trie t = entry.getValue();
            path.add(s);
            dfs(t, res, path);
            path.removeLast();
        }
    }
}

优化2

class Solution {
    public List<List<String>> deleteDuplicateFolder(List<List<String>> paths) {
        Trie root = new Trie();
        paths.sort(new Comparator<List<String>>() {
            @Override
            public int compare(List<String> l1, List<String> l2) {
                return l1.size() - l2.size();
            }
        });
        int n = paths.size();
        List<Trie> tlist = new ArrayList<>(n);
        for (List<String> list : paths) {
            Trie cur = root;
            for (int i = 0 ; i < list.size() - 1; i++) {
                String s = list.get(i);
                cur = cur.children.get(s);
            }
            Trie t = new Trie();
            cur.children.put(list.getLast(), t);
            tlist.add(t);
        }
        StringBuilder sb = new StringBuilder();
        Map<String, Trie> map = new HashMap<>();

        for (int i = n - 1; i >= 0; i--) {
            Trie cur = tlist.get(i);
            if (cur.children.isEmpty()) {
                continue;
            }
            
            for (Map.Entry<String, Trie> entry : cur.children.entrySet()) {
                sb.append(entry.getKey()).append("(").append(entry.getValue().serial).append(")");
            }
            cur.serial = sb.toString();
            Trie t = map.get(cur.serial);
            if (t == null) {
                map.put(cur.serial, cur);
            } else {
                t.setD();
                cur.setD();
            }
            sb.setLength(0);
        }
        List<List<String>> res = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (!tlist.get(i).deleted) {
                res.add(paths.get(i));
            }
        }
        return res;
    }
    class Trie {
        String serial;
        Map<String, Trie> children;
        boolean deleted;
        public Trie() {
            children = new TreeMap<>();
            deleted = false;
        }
        public void setD() {
            if (deleted) {
                return;
            }
            deleted = true;
            for (Trie t : children.values()) {
                t.setD();
            }
        }
    }
}

1957. 删除字符使字符串变好

20250721
题目链接

参考：执行用时前排代码

思路

字符串长度小于3时直接返回

用一个指针存新字符串的结束位置，遍历字符串至倒数第3个字符，如果当前字符与后面2个字符不相同则将该位置的字符加入新字符串中，指针后移一位

默认将最后两个字符加入新字符串

实现上可以在同一个数组中操作，因为从前向后遍历，向后判断字符是否相同，指针在遍历位置之前不会影响判断

优化

使用byte数组存字符

byte[] sc = s.getBytes(java.nio.charset.StandartCharsets.ISO_8859_1);

最后用byte数组构建String

new String(sc, 0, p, java.nio.charset.StandardCharsets.ISO_8859_1)

代码

class Solution {
    public String makeFancyString(String s) {
        if (s.length() < 3) {
            return s;
        }
        byte[] sc = s.getBytes(java.nio.charset.StandardCharsets.ISO_8859_1);
        int p = 0;
        for (int i = 0; i < s.length() - 2; i++) {
            if (!(sc[i] == sc[i + 1] && sc[i] == sc[i + 2])) {
                sc[p++] = sc[i];
            }
        }
        sc[p++] = sc[s.length() - 2];
        sc[p++] = sc[s.length() - 1];
        return new String(sc, 0, p, java.nio.charset.StandardCharsets.ISO_8859_1);
    }
}

1695. 删除子数组的最大得分

20250722
题目链接

参考：官方题解

执行用时前排代码

思路

遍历数组，如果这个数没出现过，将它加入集合；如果出现过，用一个指针遍历到上一次出现这个数的下标，同时更新集合(删除元素)和得分。结果取得分的最大值。

复杂度

时间复杂度：遍历数组时更新HashSet，且次数不会超过 $$N$$ ，总体为 $$O(N)$$
空间复杂度：需要一个HashSet，为 $$O(N)$$

优化

题目数据范围 $1 \leq nums[i] \leq 10^{4}$
初始化一个 $$10^4 + 1$$ 大小的数组 $$pren$$ ，下标 $$n$$ 的值表示上一次出现 $$n$$ 值的前缀和

遍历数组时，用 $$starts$$ 表示区间前一个下标的前缀和，那么当前得分可以表示为 $$ends - starts$$

查询 $$pren[nums[i]]$$ ，如果大于 $$starts$$ ，表示 $$nums[i]$$ 在当前区间起点后出现了，当前得分为 $$sum - pren[nums[i]]$$ ，更新 $$starts$$ 为 $$pren[nums[i]]$$

如果小于等于 $$starts$$ ，表示这个数在当前区间起点之前出现了，当前得分为 $$ends - starts$$

代码

class Solution {
    public int maximumUniqueSubarray(int[] nums) {
        Set<Integer> s = new HashSet<>();
        int ans = 0;
        int tem = 0;
        for (int i = 0, j = 0; i < nums.length; i++) {
            tem += nums[i];
            while (s.contains(nums[i])) {
                s.remove(nums[j]);
                tem -= nums[j];
                j++;
            }
            s.add(nums[i]);
            ans = Math.max(ans, tem);
        }
        return ans;
    }
}

优化后

class Solution {
    public int maximumUniqueSubarray(int[] nums) {
        int[] pren = new int[10001];
        int ans = 0;
        int ends = 0, starts = 0;
        for (int num : nums) {
            if(pren[num] > starts) {
                starts = pren[num];
            }
            ends += num;
            pren[num] = ends;
            ans = Math.max(ans, ends - starts);
        }

        return ans;
    }
}

1717. 删除子字符串的最大得分

20250723
题目链接

参考：官方题解

思路

假设 $$ab$$ 得分大于 $$ba$$ ，对于每个只包含 $$a$$ 和 $$b$$ 的最长子串，从前向后遍历贪心更多的 $$ab$$ ，遍历结束后加上剩余的 $$ba$$

实现时用 $$cl$$ 存储得分高的字符串的第一个字符，用 $$cr$$ 存储得分高的字符串的第二个字符，并且使 $$x$$ 为高分， $$y$$ 为低分

假设 $$ab$$ 得分更高，遍历字符串，假设当前字符为 $$b$$ ，如果 $$a$$ 的数量大于 $$0$$ ，则 $$a$$ 的数量减 $$1$$ ，得分加 $$x$$ ；如果 $$a$$ 的数量为 $$0$$ ， $$b$$ 的数量加 $$1$$ 。字符为 $$a$$ 的时候 $$a$$ 的数量加 $$1$$

遍历到非 $$a$$ 或 $$b$$ 的字符时该字串结束，该子串必定只剩下 $b...ba...a(b \geq 0, a \geq 0)$ 的形式，得分加上 $min(cnta, cntb) \times y$

复杂度

时间复杂度：遍历数组， $$O(N)$$
空间复杂度：不需要额外空间， $$O(1)$$

其他

遍历字符串的字符
for (char c : s.toCharArray())

代码

class Solution {
    public int maximumGain(String s, int x, int y) {
        int ans = 0;
        int cntl = 0, cntr= 0;
        char cl = x > y ? 'a' : 'b';
        char cr = x > y ? 'b' : 'a';
        int t1 = Math.max(x, y);
        int t2 = Math.min(x, y);
        x = t1;
        y = t2;
        for (char c : s.toCharArray()) {
            if (c == cl) {
                cntl++;
            } else if (c == cr) {
                if (cntl == 0) {
                    cntr++;
                } else {
                    ans += x;
                    cntl--;
                }
            } else {
                ans += Math.min(cntl, cntr) * y;
                cntl = 0;
                cntr = 0;
            }
        }
        ans += Math.min(cntl, cntr) * y;
        return ans;
    }
}

2322. 从树中删除边的最小分数

20250724
题目链接

参考：官方题解

思路

前置知识：

异或性质：如果 $a \oplus b = c$ ，则 $b \oplus c = a$
DFS时间戳：DFS遍历初始化in和out数组，如果i是j的子节点则 $$in[i] > in[j]$$ 并且 $out[i] \leq out[j]$

使用邻接表建(无向)图，假设树以 $$0$$ 为根,从 $$0$$ 开始DFS整颗树并更新in和out数组,维护一个xor数组存储以 $$i$$ 为根的子树的异或值，等于其本身的值与所有子树异或值的异或，在DFS的同时可以完成

枚举除 $$0$$ 以外的任意 $$2$$ 个节点，删除它们与它们父节点之间的边，剩下的 $$3$$ 个连通块有 $$3$$ 种情况

假设 $$2$$ 个节点分别为 $$i$$ 和 $$j$$

$$i$$ 是 $$j$$ 的子节点，以 $$i$$ 为根的连通块的异或值为 $$xor[i]$$ ；以 $$j$$ 为根的连通块要排除以 $$i$$ 为根的连通块，异或值为 $xor[j] \oplus xor[i]$ ；以 $$0$$ 为根的连通块的要排除整个以 $$j$$ 为根的子树，异或值为 $xor[0] \oplus xor[j]$
$$j$$ 是 $$i$$ 的子节点，与上一种类似，三个连通块的异或值分别为 $$xor[j]$$ 、 $xor[i] \oplus xor[j]$ 和 $xor[0] \oplus xor[i]$
$$i$$ 和 $$j$$ 互不为子节点，以 $$i$$ 为根的连通块的异或值为 $$xor[i]$$ ；以 $$j$$ 为根的连通块的异或值为 $$xor[j]$$ ；以 $$0$$ 为根的连通块要排除以 $$i$$ 为根的连通块和以 $$j$$ 为根的连通块，异或值为 $xor[0] \oplus xor[i] \oplus xor[j]$ ；

复杂度

时间复杂度：枚举 $$2$$ 个任意节点， $O(N ^ {2})$
空间复杂度：in，out，xor等数组长度与节点数量相等， $$O(N)$$

其他

邻接表的定义及初始化：

List<Integer>[] g;
g = new List[n];
for (int i = 0; i < n; i++) {
    g[i] = new ArrayList<>();
}

代码

class Solution {
    int clock = 0;
    int in[];
    int out[];
    int s[];
    List<Integer>[] g;
    private int getres(int xo1, int xo2, int xo3) {
        return Math.max(xo1, Math.max(xo2, xo3)) - Math.min(xo1, Math.min(xo2, xo3));
    }
    public int minimumScore(int[] nums, int[][] edges) {
        g = new List[nums.length];
        for (int i = 0; i < nums.length; i++) {
            g[i] = new ArrayList<>();
        }
        in = new int[nums.length];
        out = new int[nums.length];
        s = new int[nums.length];
        for (int i = 0; i < edges.length; i++) {
            g[edges[i][0]].add(edges[i][1]);
            g[edges[i][1]].add(edges[i][0]);
        }
        for (int i = 0; i < nums.length; i++) {
            s[i] = nums[i];
        }
        dfs(0, -1);
        int ans = Integer.MAX_VALUE;
        for (int i = 1; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (in[i] > in[j] && out[i] <= out[j]) {
                    ans = Math.min(ans, getres(s[i], s[j] ^ s[i], s[0] ^ s[j]));
                } else if (in[j] > in[i] && out[j] <= out[i]) {
                    ans = Math.min(ans, getres(s[j], s[i] ^ s[j], s[0] ^ s[i]));
                } else {
                    ans = Math.min(ans, getres(s[i], s[j], s[0] ^ s[i] ^ s[j]));
                }
            }
        }
        return ans;
    }
    private int dfs(int node, int fa) {
        in[node] = clock++;
        for (int i = 0; i < g[node].size(); i++) {
            if (g[node].get(i) == fa) {
                continue;
            }
            s[node] ^= dfs(g[node].get(i), node);
        }
        out[node] = clock;
        return s[node];
    }
}

如有错误欢迎批评指正

Dave233

目录

2163. 删除元素后和的最小差值

思路

Java 大顶堆(优先队列)

优先队列相关操作

其他

复杂度

代码

1233. 删除子文件夹

解法1 排序

思路

字典序

复杂度

其他

优化

代码

解法2 前缀树

思路

复杂度

优化

其他

代码

1948. 删除系统中的重复文件夹

思路

优化1

优化2

代码

1957. 删除字符使字符串变好

思路

优化

代码

1695. 删除子数组的最大得分

思路

复杂度

优化

代码

1717. 删除子字符串的最大得分

思路

复杂度

其他

代码

2322. 从树中删除边的最小分数

思路

复杂度

其他

代码