package study.u90;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.IdentityHashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;

import static study.u90.Solutions.*;

/** U90：逐题运行文章样例与各题指定的独立对照方法；对照实现与被测实现分开书写。 */
public class U90Lab {

    private static int passed = 0;

    public static void main(String[] args) throws Exception {
        q1();
        q2();
        q3();
        q4();
        q5();
        q6();
        q7();
        q8();
        q9();
        q10();
        q11();
        q12();
        q13();
        q14();
        q15();
        q16();
        q17();
        q18();
        q19();
        q20();
        q21();
        q22();
        q23();
        q24();
        q25();
        q26();
        q27();
        q28();
        q29();
        q30();
        out("allQuestions passed=" + passed + " total=30");
    }

    private static void ok(String name) {
        passed++;
        out(name + "=PASS");
    }

    private static void out(String line) {
        System.out.println("U90 " + line);
    }

    private static void check(boolean condition, String message) {
        if (!condition) throw new AssertionError(message);
    }

    // 独立对照：双循环枚举不同下标
    private static int[] bruteTwoSum(int[] a, int target) {
        for (int i = 0; i < a.length; i++)
            for (int j = i + 1; j < a.length; j++)
                if (a[i] + a[j] == target) return new int[]{i, j};
        return new int[0];
    }

    private static void q1() {
        check(Arrays.equals(twoSum(new int[]{2, 7, 11, 15}, 9), new int[]{0, 1}), "样例1");
        check(Arrays.equals(twoSum(new int[]{3, 3}, 6), new int[]{0, 1}), "样例2");
        int[] a = {-3, 4, 3, 90};
        int[] r = twoSum(a, 0);
        int[] brute = bruteTwoSum(a, 0);
        check(Arrays.equals(r, brute) && r[0] != r[1] && a[r[0]] + a[r[1]] == 0, "负数与目标0对照");
        ok("q1 twoSum");
    }

    private static void q2() {
        List<List<String>> groups = groupAnagrams(new String[]{"eat", "tea", "tan", "ate", "nat", "bat"});
        Set<Set<String>> normalized = new HashSet<>();
        int total = 0;
        for (List<String> g : groups) {
            normalized.add(new HashSet<>(g));
            total += g.size();
        }
        check(normalized.equals(Set.of(new HashSet<>(List.of("eat", "tea", "ate")),
                new HashSet<>(List.of("tan", "nat")), new HashSet<>(List.of("bat")))), "样例分组");
        check(total == 6, "保留重复字符串数量");
        List<List<String>> empty = groupAnagrams(new String[]{"", ""});
        check(empty.size() == 1 && empty.get(0).size() == 2, "两个空串同组");
        // 独立对照：排序键分组比较
        Map<String, Set<String>> brute = new HashMap<>();
        for (String w : new String[]{"eat", "tea", "tan", "ate", "nat", "bat"}) {
            char[] c = w.toCharArray();
            Arrays.sort(c);
            brute.computeIfAbsent(new String(c), k -> new HashSet<>()).add(w);
        }
        Set<Set<String>> bruteSets = new HashSet<>(brute.values());
        check(bruteSets.equals(normalized), "排序键对照");
        ok("q2 groupAnagrams");
    }

    private static void q3() {
        check(longestConsecutive(new int[]{100, 4, 200, 1, 3, 2, 2}) == 4, "样例1");
        check(longestConsecutive(new int[]{}) == 0, "空数组");
        // 独立对照：去重排序逐段计数
        int[] a = {2147483646, -2147483647, 0, 2, 2147483645, 1};
        Set<Integer> set = new HashSet<>();
        for (int x : a) set.add(x);
        List<Integer> sorted = new ArrayList<>(set);
        java.util.Collections.sort(sorted);
        int brute = 0, run = 1;
        for (int i = 1; i <= sorted.size(); i++) {
            if (i < sorted.size() && sorted.get(i) - sorted.get(i - 1) == 1L) run++;
            else {
                brute = Math.max(brute, run);
                run = 1;
            }
        }
        check(longestConsecutive(a) == brute, "MIN/MAX 同时存在不误连（long 比较）");
        ok("q3 longestConsecutive");
    }

    private static void q4() {
        check(Arrays.equals(productExceptSelf(new int[]{1, 2, 3, 4}), new int[]{24, 12, 8, 6}), "样例1");
        check(Arrays.equals(productExceptSelf(new int[]{-1, 0, 3}), new int[]{0, -3, 0}), "单个0");
        check(Arrays.equals(productExceptSelf(new int[]{0, 4, 0}), new int[]{0, 0, 0}), "两个0全0");
        // 独立对照：逐位置排除自身乘法
        int[] a = {2, 3, -1, 5};
        int[] brute = new int[a.length];
        for (int i = 0; i < a.length; i++) {
            int p = 1;
            for (int j = 0; j < a.length; j++) if (j != i) p *= a[j];
            brute[i] = p;
        }
        check(Arrays.equals(productExceptSelf(a), brute), "逐位置枚举对照");
        ok("q4 productExceptSelf");
    }

    private static void q5() {
        List<List<Integer>> r = threeSum(new int[]{-1, 0, 1, 2, -1, -4});
        check(r.equals(List.of(List.of(-1, -1, 2), List.of(-1, 0, 1))), "样例1");
        check(threeSum(new int[]{0, 0, 0, 0}).equals(List.of(List.of(0, 0, 0))), "全0去重");
        // 独立对照：三重枚举 + 排序放 set
        int[] a = {-2, 0, 2, 4, -4};
        Set<List<Integer>> brute = new HashSet<>();
        for (int i = 0; i < a.length; i++)
            for (int j = i + 1; j < a.length; j++)
                for (int k = j + 1; k < a.length; k++)
                    if (a[i] + a[j] + a[k] == 0) {
                        List<Integer> trip = new ArrayList<>(List.of(a[i], a[j], a[k]));
                        trip.sort(null);
                        brute.add(trip);
                    }
        check(new HashSet<>(threeSum(a)).equals(brute), "三重枚举对照");
        ok("q5 threeSum");
    }

    private static void q6() {
        check(maxWaterContainer(new int[]{1, 8, 6, 2, 5, 4, 8, 3, 7}) == 49, "样例1");
        check(maxWaterContainer(new int[]{0, 0}) == 0, "全0");
        // 独立对照：枚举所有线对
        int[] a = {3, 1, 2, 4, 3};
        long brute = 0;
        for (int i = 0; i < a.length; i++)
            for (int j = i + 1; j < a.length; j++)
                brute = Math.max(brute, (long) (j - i) * Math.min(a[i], a[j]));
        check(maxWaterContainer(a) == brute, "线对枚举对照");
        ok("q6 maxWaterContainer");
    }

    private static void q7() {
        check(trapRain(new int[]{4, 2, 0, 3, 2, 5}) == 9, "样例1");
        check(trapRain(new int[]{5, 4, 3, 2, 1}) == 0, "单调递减0");
        check(trapRain(new int[]{1, 2}) == 0, "长度不足3");
        // 独立对照：逐位置扫左右最大
        int[] a = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        long brute = 0;
        for (int i = 0; i < a.length; i++) {
            int left = 0, right = 0;
            for (int j = 0; j <= i; j++) left = Math.max(left, a[j]);
            for (int j = i; j < a.length; j++) right = Math.max(right, a[j]);
            brute += Math.max(0, Math.min(left, right) - a[i]);
        }
        check(trapRain(a) == brute, "逐位置左右最大对照");
        ok("q7 trapRain");
    }

    private static void q8() {
        check(lengthOfLongestSubstring("abcabcbb") == 3, "样例1");
        check(lengthOfLongestSubstring("abba") == 2, "abba 不回退");
        check(lengthOfLongestSubstring("") == 0, "空串");
        // 独立对照：枚举子串集合检查唯一
        String s = "pwwkew";
        int brute = 0;
        for (int i = 0; i < s.length(); i++)
            for (int j = i + 1; j <= s.length(); j++) {
                Set<Character> chars = new HashSet<>();
                for (char c : s.substring(i, j).toCharArray()) chars.add(c);
                if (chars.size() == j - i) brute = Math.max(brute, j - i);
            }
        check(lengthOfLongestSubstring(s) == brute, "子串枚举对照");
        ok("q8 lengthOfLongestSubstring");
    }

    private static void q9() {
        check(minWindow("ADOBECODEBANC", "ABC").equals("BANC"), "样例1");
        check(minWindow("a", "aa").equals(""), "s 不足");
        check(minWindow("aa", "aa").equals("aa"), "全覆盖");
        // 独立对照：枚举子串按多重计数判覆盖
        String s = "cabwefgewcwaefgcf", t = "cae";
        String brute = "";
        for (int i = 0; i < s.length(); i++)
            for (int j = i + 1; j <= s.length(); j++) {
                String sub = s.substring(i, j);
                Map<Character, Integer> need = new HashMap<>();
                for (char c : t.toCharArray()) need.merge(c, 1, Integer::sum);
                for (char c : sub.toCharArray()) need.computeIfPresent(c, (k, v) -> v > 1 ? v - 1 : null);
                if (need.isEmpty() && (brute.isEmpty() || sub.length() < brute.length())) brute = sub;
            }
        check(minWindow(s, t).equals(brute), "子串覆盖对照");
        ok("q9 minWindow");
    }

    private static void q10() {
        check(findAnagrams("cbaebabacd", "abc").equals(List.of(0, 6)), "样例1");
        check(findAnagrams("abab", "ab").equals(List.of(0, 1, 2)), "重叠匹配");
        check(findAnagrams("ab", "abc").isEmpty(), "p 长于 s");
        // 独立对照：逐窗口排序比较
        String s = "cbaebabacd", p = "abc";
        List<Integer> brute = new ArrayList<>();
        char[] pSorted = p.toCharArray();
        Arrays.sort(pSorted);
        for (int i = 0; i + p.length() <= s.length(); i++) {
            char[] w = s.substring(i, i + p.length()).toCharArray();
            Arrays.sort(w);
            if (Arrays.equals(w, pSorted)) brute.add(i);
        }
        check(findAnagrams(s, p).equals(brute), "窗口排序对照");
        ok("q10 findAnagrams");
    }

    private static void q11() {
        check(binarySearch(new int[]{-1, 0, 3, 5, 9, 12}, 9) == 4, "样例命中");
        check(binarySearch(new int[]{-1, 0, 3, 5, 9, 12}, 2) == -1, "样例未命中");
        // 独立对照：线性查找 + 区间缩小检查
        int[] a = {1, 3, 5, 7};
        for (int target : new int[]{0, 1, 3, 4, 5, 6, 7, 8}) {
            int brute = -1;
            for (int i = 0; i < a.length; i++) if (a[i] == target) brute = i;
            check(binarySearch(a, target) == brute, "线性对照 target=" + target);
        }
        ok("q11 binarySearch");
    }

    private static void q12() {
        check(searchRotated(new int[]{4, 5, 6, 7, 0, 1, 2}, 0) == 4, "样例命中");
        check(searchRotated(new int[]{4, 5, 6, 7, 0, 1, 2}, 3) == -1, "样例未命中");
        // 独立对照：长度≤20 枚举旋转点与全部目标
        int[] base = {1, 2, 3, 4, 5, 6, 7, 8};
        for (int rotate = 0; rotate < base.length; rotate++) {
            int[] a = new int[base.length];
            for (int i = 0; i < base.length; i++) a[i] = base[(i + rotate) % base.length];
            for (int target = 0; target <= 9; target++) {
                int brute = -1;
                for (int i = 0; i < a.length; i++) if (a[i] == target) brute = i;
                check(searchRotated(a, target) == brute, "旋转 " + rotate + " target=" + target);
            }
        }
        ok("q12 searchRotated");
    }

    private static void q13() {
        check(Arrays.equals(searchRange(new int[]{5, 7, 7, 8, 8, 10}, 8), new int[]{3, 4}), "样例1");
        check(Arrays.equals(searchRange(new int[]{}, 5), new int[]{-1, -1}), "空数组");
        check(Arrays.equals(searchRange(new int[]{2, 2}, 2), new int[]{0, 1}), "全相等");
        int[] withMax = {Integer.MIN_VALUE, 5, Integer.MAX_VALUE};
        check(Arrays.equals(searchRange(withMax, Integer.MAX_VALUE), new int[]{2, 2}), "MAX 不溢出");
        // 独立对照：线性扫描收集
        int[] a = {1, 2, 2, 2, 3};
        int target = 2;
        List<Integer> positions = new ArrayList<>();
        for (int i = 0; i < a.length; i++) if (a[i] == target) positions.add(i);
        int[] brute = positions.isEmpty() ? new int[]{-1, -1} : new int[]{positions.get(0), positions.get(positions.size() - 1)};
        check(Arrays.equals(searchRange(a, target), brute), "线性收集对照");
        ok("q13 searchRange");
    }

    private static void q14() {
        check(isValidBrackets("([]){}"), "样例1");
        check(!isValidBrackets("([)]"), "交叉");
        check(!isValidBrackets("]"), "右括号开头");
        check(!isValidBrackets("(("), "未闭合左括号");
        // 独立对照：反复删除相邻合法对
        String s = "{[()()]}";
        StringBuilder sb = new StringBuilder(s);
        boolean changed = true;
        while (changed) {
            changed = false;
            for (int i = 0; i + 1 < sb.length(); i++) {
                String pair = sb.substring(i, i + 2);
                if (pair.equals("()") || pair.equals("[]") || pair.equals("{}")) {
                    sb.delete(i, i + 2);
                    changed = true;
                    break;
                }
            }
        }
        check(isValidBrackets(s) == (sb.length() == 0), "删对对照");
        ok("q14 isValidBrackets");
    }

    private static void q15() {
        check(Arrays.equals(dailyTemperatures(new int[]{73, 74, 75, 71, 69, 72, 76, 73}),
                new int[]{1, 1, 4, 2, 1, 1, 0, 0}), "样例1");
        check(Arrays.equals(dailyTemperatures(new int[]{30, 30}), new int[]{0, 0}), "相等严格更大才计数");
        // 独立对照：向右扫首个严格更高
        int[] a = {55, 60, 50, 70, 70, 80};
        int[] brute = new int[a.length];
        for (int i = 0; i < a.length; i++)
            for (int j = i + 1; j < a.length; j++)
                if (a[j] > a[i]) {
                    brute[i] = j - i;
                    break;
                }
        check(Arrays.equals(dailyTemperatures(a), brute), "右扫对照");
        ok("q15 dailyTemperatures");
    }

    private static void q16() {
        check(largestRectangle(new int[]{2, 1, 5, 6, 2, 3}) == 10, "样例1");
        check(largestRectangle(new int[]{2, 2}) == 4, "等高");
        check(largestRectangle(new int[]{}) == 0, "空");
        // 独立对照：枚举区间维护最小高度
        int[] a = {6, 2, 5, 4, 5, 1, 6};
        long brute = 0;
        for (int i = 0; i < a.length; i++) {
            int min = a[i];
            for (int j = i; j < a.length; j++) {
                min = Math.min(min, a[j]);
                brute = Math.max(brute, (long) min * (j - i + 1));
            }
        }
        check(largestRectangle(a) == brute, "区间最小高度对照");
        ok("q16 largestRectangle");
    }

    private static Solutions.ListNode build(int... vals) {
        Solutions.ListNode sentinel = new Solutions.ListNode(0), tail = sentinel;
        for (int v : vals) {
            tail.next = new Solutions.ListNode(v);
            tail = tail.next;
        }
        return sentinel.next;
    }

    private static int[] toArray(Solutions.ListNode head) {
        List<Integer> vals = new ArrayList<>();
        while (head != null) {
            vals.add(head.val);
            head = head.next;
        }
        return vals.stream().mapToInt(Integer::intValue).toArray();
    }

    private static boolean hasCycle(Solutions.ListNode head) {
        Set<Solutions.ListNode> seen = java.util.Collections.newSetFromMap(new IdentityHashMap<>());
        while (head != null) {
            if (!seen.add(head)) return true;
            head = head.next;
        }
        return false;
    }

    private static void q17() {
        Solutions.ListNode reversed = reverseList(build(1, 2, 3));
        check(Arrays.equals(toArray(reversed), new int[]{3, 2, 1}), "样例反转");
        check(reverseList(null) == null, "null");
        // 独立对照：节点身份逆序 + 反转两次恢复 + 无环
        Solutions.ListNode original = build(4, 5, 6, 7);
        List<Solutions.ListNode> identity = new ArrayList<>();
        for (Solutions.ListNode n = original; n != null; n = n.next) identity.add(n);
        Solutions.ListNode once = reverseList(original);
        List<Solutions.ListNode> reversedIdentity = new ArrayList<>();
        for (Solutions.ListNode n = once; n != null; n = n.next) reversedIdentity.add(n);
        check(reversedIdentity.equals(Arrays.asList(identity.get(3), identity.get(2), identity.get(1), identity.get(0))), "身份逆序");
        Solutions.ListNode twice = reverseList(once);
        check(!hasCycle(twice) && toArray(twice).length == 4, "反转两次恢复且无环");
        ok("q17 reverseList");
    }

    private static void q18() {
        check(Arrays.equals(toArray(mergeTwoLists(build(1, 2, 4), build(1, 3, 4))), new int[]{1, 1, 2, 3, 4, 4}), "样例");
        check(mergeTwoLists(null, build(1)) != null, "一条空");
        // 独立对照：值合并排序 + 节点身份 + 无环
        Solutions.ListNode a = build(2, 5, 9), b = build(1, 3);
        Solutions.ListNode merged = mergeTwoLists(a, b);
        int[] brute = {2, 5, 9, 1, 3};
        Arrays.sort(brute);
        check(Arrays.equals(toArray(merged), brute), "值对照");
        Set<Solutions.ListNode> identity = java.util.Collections.newSetFromMap(new IdentityHashMap<>());
        int count = 0;
        for (Solutions.ListNode n = merged; n != null; n = n.next) {
            identity.add(n);
            count++;
        }
        check(identity.size() == count && count == 5 && !hasCycle(merged), "身份数量与无环");
        ok("q18 mergeTwoLists");
    }

    private static void q19() {
        // 样例：3→2→0→-4 尾连到值 2 节点
        Solutions.ListNode n0 = new Solutions.ListNode(3), n1 = new Solutions.ListNode(2),
                n2 = new Solutions.ListNode(0), n3 = new Solutions.ListNode(-4);
        n0.next = n1;
        n1.next = n2;
        n2.next = n3;
        n3.next = n1;
        check(detectCycle(n0) == n1, "样例入口");
        Solutions.ListNode self = new Solutions.ListNode(7);
        self.next = self;
        check(detectCycle(self) == self, "自环");
        check(detectCycle(build(1, 2)) == null, "无环");
        // 独立对照：IdentityHashMap 首次重复
        Solutions.ListNode cycleHead = build(1, 2, 3);
        Solutions.ListNode tail = cycleHead;
        while (tail.next != null) tail = tail.next;
        tail.next = cycleHead.next; // 入口为第二个节点
        Map<Solutions.ListNode, Boolean> seen = new IdentityHashMap<>();
        Solutions.ListNode brute = null;
        for (Solutions.ListNode n = cycleHead; n != null; n = n.next) {
            if (seen.put(n, true) != null) {
                brute = n;
                break;
            }
        }
        check(detectCycle(cycleHead) == brute, "首次重复对照");
        ok("q19 detectCycle");
    }

    private static void q20() {
        Solutions.ListNode merged = mergeKLists(new Solutions.ListNode[]{build(1, 4, 5), build(1, 3, 4), build(2, 6)});
        check(Arrays.equals(toArray(merged), new int[]{1, 1, 2, 3, 4, 4, 5, 6}), "样例");
        check(mergeKLists(new Solutions.ListNode[0]) == null, "k=0");
        // 独立对照：全值排序 + 数量/无环
        Solutions.ListNode[] lists = {build(3, 7), build(1), null, build(2, 8, 10)};
        Solutions.ListNode result = mergeKLists(lists);
        int[] brute = {3, 7, 1, 2, 8, 10};
        Arrays.sort(brute);
        check(Arrays.equals(toArray(result), brute), "值对照");
        check(!hasCycle(result) && toArray(result).length == brute.length, "数量与无环");
        ok("q20 mergeKLists");
    }

    private static void q21() {
        check(findKthLargest(new int[]{3, 2, 3, 1, 2, 4, 5, 5, 6}, 4) == 4, "样例");
        // 独立对照：排序取 n-k；覆盖 k=1、k=n、全等
        int[][] cases = {{3, 2, 1, 5, 6, 4}, {3, 2, 3, 1, 2, 4, 5, 5, 6}, {7, 7, 7}, {1, 2, 3}};
        int[][] ks = {{2}, {4}, {1}, {3}};
        for (int c = 0; c < cases.length; c++) {
            int[] brute = cases[c].clone();
            Arrays.sort(brute);
            int k = ks[c][0];
            check(findKthLargest(cases[c], k) == brute[brute.length - k], "case " + c + " k=" + k);
        }
        check(findKthLargest(new int[]{5}, 1) == 5, "k=n");
        ok("q21 findKthLargest");
    }

    private static void q22() {
        check(Arrays.equals(topKFrequent(new int[]{1, 1, 1, 2, 2, 3}, 2), new int[]{1, 2}), "样例");
        check(Arrays.equals(topKFrequent(new int[]{2, 1}, 1), new int[]{1}) || Arrays.equals(topKFrequent(new int[]{2, 1}, 1), new int[]{2}),
                "同频按比较器裁决");
        // 独立对照：完整频次表按规则排序
        int[] a = {4, 4, 4, 6, 6, 1, 1, 1, 1, 9};
        int k = 3;
        Map<Integer, Integer> count = new HashMap<>();
        for (int x : a) count.merge(x, 1, Integer::sum);
        List<int[]> sorted = new ArrayList<>();
        count.forEach((key, value) -> sorted.add(new int[]{key, value}));
        sorted.sort((x, y) -> x[1] != y[1] ? Integer.compare(y[1], x[1]) : Integer.compare(x[0], y[0]));
        int[] brute = new int[k];
        for (int i = 0; i < k; i++) brute[i] = sorted.get(i)[0];
        int[] result = topKFrequent(a, k);
        check(Arrays.equals(result, brute) || java.util.Set.of(brute).containsAll(java.util.List.of(result)), "频次表对照");
        ok("q22 topKFrequent");
    }

    private static void q23() {
        List<Solutions.TreeNode> nodes = new ArrayList<>();
        Solutions.TreeNode root = buildTree(new Integer[]{3, 9, 20, null, null, 15, 7}, nodes);
        check(levelOrder(root).equals(List.of(List.of(3), List.of(9, 20), List.of(15, 7))), "样例");
        // 独立对照：DFS 携带深度
        List<List<Integer>> brute = new ArrayList<>();
        dfsLevels(root, 0, brute);
        check(levelOrder(root).equals(brute), "DFS 对照");
        check(levelOrder(null).isEmpty(), "空树");
        Solutions.TreeNode chain = buildTree(new Integer[]{1, 2, null, 3, null, null, null}, nodes);
        check(levelOrder(chain).equals(List.of(List.of(1), List.of(2), List.of(3))), "单链");
        ok("q23 levelOrder");
    }

    private static void dfsLevels(Solutions.TreeNode node, int depth, List<List<Integer>> out) {
        if (node == null) return;
        if (out.size() == depth) out.add(new ArrayList<>());
        out.get(depth).add(node.val);
        dfsLevels(node.left, depth + 1, out);
        dfsLevels(node.right, depth + 1, out);
    }

    private static void q24() {
        List<Solutions.TreeNode> nodes = new ArrayList<>();
        Solutions.TreeNode bad = buildTree(new Integer[]{5, 1, 4, null, null, 3, 6}, nodes);
        check(!isValidBST(bad), "样例1 false");
        List<Solutions.TreeNode> good = new ArrayList<>();
        Solutions.TreeNode ok = buildTree(new Integer[]{2, 1, 3}, good);
        check(isValidBST(ok), "样例2 true");
        // 独立对照：long 开区间递归
        check(isValidBstRecursive(ok, Long.MIN_VALUE, Long.MAX_VALUE), "开区间对照 true");
        check(!isValidBstRecursive(bad, Long.MIN_VALUE, Long.MAX_VALUE), "开区间对照 false");
        check(isValidBST(new Solutions.TreeNode(Integer.MIN_VALUE)), "MIN 单节点");
        ok("q24 isValidBST");
    }

    private static boolean isValidBstRecursive(Solutions.TreeNode node, long lo, long hi) {
        if (node == null) return true;
        if (node.val <= lo || node.val >= hi) return false;
        return isValidBstRecursive(node.left, lo, node.val) && isValidBstRecursive(node.right, node.val, hi);
    }

    private static void q25() {
        List<Solutions.TreeNode> nodes = new ArrayList<>();
        Solutions.TreeNode root = buildTree(new Integer[]{3, 5, 1, 6, 2, 0, 8, null, null, 7, 4}, nodes);
        Solutions.TreeNode p = nodes.get(1), q4 = nodes.get(8), one = nodes.get(2);
        check(lowestCommonAncestor(root, p, q4) == p, "p=5 q=4 → 5");
        check(lowestCommonAncestor(root, p, one) == root, "p=5 q=1 → 3");
        check(lowestCommonAncestor(root, p, p) == p, "p=q");
        // 独立对照：父指针表 + 两条到根路径共同后缀
        Map<Solutions.TreeNode, Solutions.TreeNode> parent = new IdentityHashMap<>();
        buildParents(root, parent);
        List<Solutions.TreeNode> pathP = pathToRoot(p, parent);
        List<Solutions.TreeNode> pathQ = pathToRoot(q4, parent);
        Solutions.TreeNode brute = null;
        for (Solutions.TreeNode a : pathP) {
            if (pathQ.contains(a)) {
                brute = a;
                break;
            }
        }
        check(lowestCommonAncestor(root, p, q4) == brute, "路径对照");
        ok("q25 lowestCommonAncestor");
    }

    private static void buildParents(Solutions.TreeNode node, Map<Solutions.TreeNode, Solutions.TreeNode> parent) {
        if (node.left != null) {
            parent.put(node.left, node);
            buildParents(node.left, parent);
        }
        if (node.right != null) {
            parent.put(node.right, node);
            buildParents(node.right, parent);
        }
    }

    private static List<Solutions.TreeNode> pathToRoot(Solutions.TreeNode node, Map<Solutions.TreeNode, Solutions.TreeNode> parent) {
        List<Solutions.TreeNode> path = new ArrayList<>();
        while (node != null) {
            path.add(node);
            node = parent.get(node);
        }
        return path;
    }

    private static void q26() {
        char[][] grid1 = {"11000".toCharArray(), "11000".toCharArray(), "00100".toCharArray(), "00011".toCharArray()};
        check(numIslands(grid1) == 3, "样例1");
        char[][] grid2 = {"10".toCharArray(), "01".toCharArray()};
        check(numIslands(grid2) == 2, "对角不相连");
        // 独立对照：并查集合并右/下相邻陆地
        char[][] grid3 = {"101".toCharArray(), "010".toCharArray(), "101".toCharArray()};
        int m = grid3.length, n = grid3[0].length;
        int[] parent = new int[m * n];
        for (int i = 0; i < m * n; i++) parent[i] = i;
        int land = 0;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (grid3[i][j] == '1') land++;
        IntFind find = x -> {
            while (parent[x] != x) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        };
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                if (grid3[i][j] != '1') continue;
                if (j + 1 < n && grid3[i][j + 1] == '1') {
                    int a = find.find(i * n + j), b = find.find(i * n + j + 1);
                    if (a != b) {
                        parent[a] = b;
                        land--;
                    }
                }
                if (i + 1 < m && grid3[i + 1][j] == '1') {
                    int a = find.find(i * n + j), b = find.find((i + 1) * n + j);
                    if (a != b) {
                        parent[a] = b;
                        land--;
                    }
                }
            }
        check(numIslands(grid3) == land, "并查集对照");
        char[][] allWater = {"000".toCharArray()};
        check(numIslands(allWater) == 0, "全水");
        ok("q26 numIslands");
    }

    interface IntFind {
        int find(int x);
    }

    private static void q27() {
        check(canFinish(2, new int[][]{{1, 0}}), "样例1 true");
        check(!canFinish(2, new int[][]{{1, 0}, {0, 1}}), "成环 false");
        check(!canFinish(1, new int[][]{{0, 0}}), "自环 false");
        // 独立对照：小图枚举全部排列
        int v = 4;
        int[][] edges = {{1, 0}, {2, 0}, {3, 1}, {3, 2}};
        List<List<Integer>> permutations = permutations(v);
        boolean brute = false;
        for (List<Integer> perm : permutations) {
            Map<Integer, Integer> position = new HashMap<>();
            for (int i = 0; i < perm.size(); i++) position.put(perm.get(i), i);
            boolean valid = true;
            for (int[] e : edges) if (position.get(e[1]) > position.get(e[0])) valid = false;
            if (valid) {
                brute = true;
                break;
            }
        }
        check(canFinish(v, edges) == brute, "排列枚举对照");
        ok("q27 canFinish");
    }

    private static List<List<Integer>> permutations(int v) {
        List<List<Integer>> out = new ArrayList<>();
        permute(new int[v], 0, new boolean[v], new ArrayList<>(), out);
        return out;
    }

    private static void permute(int[] slots, int index, boolean[] used, List<Integer> current, List<List<Integer>> out) {
        if (index == slots.length) {
            out.add(new ArrayList<>(current));
            return;
        }
        for (int i = 0; i < used.length; i++) {
            if (used[i]) continue;
            used[i] = true;
            current.add(i);
            permute(slots, index + 1, used, current, out);
            current.remove(current.size() - 1);
            used[i] = false;
        }
    }

    private static void q28() {
        check(coinChange(new int[]{1, 2, 5}, 11) == 3, "样例1");
        check(coinChange(new int[]{2}, 3) == -1, "样例无解");
        check(coinChange(new int[]{}, 0) == 0, "amount 0");
        check(coinChange(new int[]{1, 3, 4}, 6) == 2, "贪心失效用例 [1,3,4],6=2（3+3）");
        // 独立对照：BFS 层数
        int[] coins = {2, 5, 7};
        int amount = 12;
        java.util.Queue<Integer> queue = new java.util.ArrayDeque<>();
        Set<Integer> visited = new HashSet<>();
        queue.offer(0);
        visited.add(0);
        int layers = 0, brute = -1;
        while (!queue.isEmpty()) {
            layers++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int cur = queue.poll();
                for (int coin : coins) {
                    int next = cur + coin;
                    if (next == amount) brute = layers;
                    if (next < amount && visited.add(next)) queue.offer(next);
                }
            }
            if (brute > 0) break;
        }
        check(coinChange(coins, amount) == brute, "BFS 层数对照");
        ok("q28 coinChange");
    }

    private static void q29() {
        check(lengthOfLIS(new int[]{10, 9, 2, 5, 3, 7, 101, 18}) == 4, "样例1");
        check(lengthOfLIS(new int[]{2, 2}) == 1, "重复值");
        check(lengthOfLIS(new int[]{}) == 0, "空");
        // 独立对照：O(n²) dp
        int[] a = {5, 8, 7, 1, 9};
        int[] dp = new int[a.length];
        int brute = 0;
        for (int i = 0; i < a.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) if (a[j] < a[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
            brute = Math.max(brute, dp[i]);
        }
        check(lengthOfLIS(a) == brute, "O(n²) 对照");
        check(lengthOfLIS(new int[]{3, 2, 1}) == 1, "逆序");
        ok("q29 lengthOfLIS");
    }

    private static void q30() {
        check(minDistance("horse", "ros") == 3, "样例1");
        check(minDistance("", "abc") == 3, "空串");
        check(minDistance("same", "same") == 0, "相同串");
        // 独立对照：a/b 字母表 BFS + 对称性
        String w1 = "ab", w2 = "baa";
        java.util.Queue<String> queue = new java.util.ArrayDeque<>();
        Set<String> visited = new HashSet<>();
        queue.offer(w1);
        visited.add(w1);
        int steps = 0, brute = -1;
        while (!queue.isEmpty() && brute < 0) {
            steps++;
            int size = queue.size();
            for (int i = 0; i < size && brute < 0; i++) {
                String cur = queue.poll();
                for (int p = 0; p <= cur.length() && brute < 0; p++) {
                    for (char insert = 'a'; insert <= 'b' && brute < 0; insert++) {
                        String candidate = cur.substring(0, p) + insert + cur.substring(p);
                        if (candidate.equals(w2)) brute = steps;
                        if (candidate.length() <= w1.length() + w2.length() && visited.add(candidate)) queue.offer(candidate);
                    }
                    if (p < cur.length()) {
                        String deleted = cur.substring(0, p) + cur.substring(p + 1);
                        if (deleted.equals(w2)) brute = steps;
                        if (!deleted.isEmpty() && visited.add(deleted)) queue.offer(deleted);
                        char replacedA = cur.charAt(p) == 'a' ? 'b' : 'a';
                        String replaced = cur.substring(0, p) + replacedA + cur.substring(p + 1);
                        if (replaced.equals(w2)) brute = steps;
                        if (visited.add(replaced)) queue.offer(replaced);
                    }
                }
            }
        }
        check(minDistance(w1, w2) == brute, "BFS 对照");
        check(minDistance(w1, w2) == minDistance(w2, w1), "对称性");
        check(minDistance(w1, w2) >= Math.abs(w1.length() - w2.length()), "长度差下界");
        ok("q30 minDistance");
    }
}