package study.u90;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.IdentityHashMap;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;

/** U90：30 题广度清单的参考实现，算法与《算法与并发编码》逐题规格一致。 */
final class Solutions {
    private Solutions() {
    }

    // 1. 两数之和：先查后存
    static int[] twoSum(int[] a, int target) {
        Map<Integer, Integer> seen = new HashMap<>();
        for (int i = 0; i < a.length; i++) {
            Integer j = seen.get(target - a[i]);
            if (j != null) return new int[]{j, i};
            seen.put(a[i], i);
        }
        return new int[0];
    }

    // 2. 字母异位词分组：26 项频次带分隔符键
    static List<List<String>> groupAnagrams(String[] words) {
        Map<String, List<String>> groups = new LinkedHashMap<>();
        for (String w : words) {
            int[] count = new int[26];
            for (int i = 0; i < w.length(); i++) count[w.charAt(i) - 'a']++;
            String key = Arrays.toString(count);
            groups.computeIfAbsent(key, k -> new ArrayList<>()).add(w);
        }
        return new ArrayList<>(groups.values());
    }

    // 3. 最长连续序列：无前驱才向右探测
    static int longestConsecutive(int[] a) {
        Set<Integer> set = new HashSet<>();
        for (int x : a) set.add(x);
        int best = 0;
        for (int x : set) {
            if (set.contains(x - 1)) continue;
            int len = 1;
            while (set.contains(x + len)) len++;
            best = Math.max(best, len);
        }
        return best;
    }

    // 4. 除自身以外数组的乘积：左前缀 + 右滚动后缀（先使用后更新）
    static int[] productExceptSelf(int[] a) {
        int n = a.length;
        long[] out = new long[n];
        out[0] = 1;
        for (int i = 1; i < n; i++) out[i] = out[i - 1] * a[i - 1];
        long suffix = 1;
        for (int i = n - 1; i >= 0; i--) {
            out[i] *= suffix;
            suffix *= a[i];
        }
        long[] result = out;
        int[] ints = new int[n];
        for (int i = 0; i < n; i++) ints[i] = (int) result[i];
        return ints;
    }

    // 5. 三数之和：排序 + 固定 i + 双指针，long 求和
    static List<List<Integer>> threeSum(int[] a) {
        Arrays.sort(a);
        Set<List<Integer>> found = new HashSet<>();
        for (int i = 0; i < a.length - 2 && a[i] <= 0; i++) {
            if (i > 0 && a[i] == a[i - 1]) continue;
            int left = i + 1, right = a.length - 1;
            while (left < right) {
                long sum = (long) a[i] + a[left] + a[right];
                if (sum < 0) left++;
                else if (sum > 0) right--;
                else {
                    found.add(List.of(a[i], a[left], a[right]));
                    left++;
                    right--;
                }
            }
        }
        List<List<Integer>> out = new ArrayList<>(found);
        Collections.sort(out, (x, y) -> {
            for (int k = 0; k < 3; k++) {
                int c = Integer.compare(x.get(k), y.get(k));
                if (c != 0) return c;
            }
            return 0;
        });
        return out;
    }

    // 6. 盛最多水的容器：两端夹逼移动短边
    static long maxWaterContainer(int[] h) {
        int lo = 0, hi = h.length - 1;
        long best = 0;
        while (lo < hi) {
            best = Math.max(best, (long) (hi - lo) * Math.min(h[lo], h[hi]));
            if (h[lo] <= h[hi]) lo++;
            else hi--;
        }
        return best;
    }

    // 7. 接雨水：双指针维护两侧最高
    static long trapRain(int[] h) {
        int lo = 0, hi = h.length - 1;
        long water = 0;
        int leftMax = 0, rightMax = 0;
        while (lo < hi) {
            if (h[lo] <= h[hi]) {
                leftMax = Math.max(leftMax, h[lo]);
                water += leftMax - h[lo];
                lo++;
            } else {
                rightMax = Math.max(rightMax, h[hi]);
                water += rightMax - h[hi];
                hi--;
            }
        }
        return water;
    }

    // 8. 无重复字符最长子串：最近下标，left 不回退
    static int lengthOfLongestSubstring(String s) {
        int[] last = new int[128];
        Arrays.fill(last, -1);
        int left = 0, best = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (last[c] >= left) left = last[c] + 1;
            last[c] = i;
            best = Math.max(best, i - left + 1);
        }
        return best;
    }

    // 9. 最小覆盖子串：need 计数伸缩
    static String minWindow(String s, String t) {
        int[] need = new int[128];
        for (int i = 0; i < t.length(); i++) need[t.charAt(i)]++;
        int missing = t.length(), left = 0, bestLeft = -1, bestLen = Integer.MAX_VALUE;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            if (need[c] > 0) missing--;
            need[c]--;
            if (missing == 0) {
                while (need[s.charAt(left)] < 0) {
                    need[s.charAt(left)]++;
                    left++;
                }
                if (right - left + 1 < bestLen) {
                    bestLeft = left;
                    bestLen = right - left + 1;
                }
            }
        }
        return bestLeft < 0 ? "" : s.substring(bestLeft, bestLeft + bestLen);
    }

    // 10. 找到所有字母异位词：固定窗口计数
    static List<Integer> findAnagrams(String s, String p) {
        List<Integer> out = new ArrayList<>();
        if (p.length() > s.length()) return out;
        int[] need = new int[26], window = new int[26];
        for (int i = 0; i < p.length(); i++) {
            need[p.charAt(i) - 'a']++;
            window[s.charAt(i) - 'a']++;
        }
        if (Arrays.equals(need, window)) out.add(0);
        for (int i = p.length(); i < s.length(); i++) {
            window[s.charAt(i) - 'a']++;
            window[s.charAt(i - p.length()) - 'a']--;
            if (Arrays.equals(need, window)) out.add(i - p.length() + 1);
        }
        return out;
    }

    // 11. 二分查找：[lo,hi)
    static int binarySearch(int[] a, int target) {
        int lo = 0, hi = a.length;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (a[mid] < target) lo = mid + 1;
            else hi = mid;
        }
        return lo < a.length && a[lo] == target ? lo : -1;
    }

    // 12. 搜索旋转排序数组：有序半边闭区间判断
    static int searchRotated(int[] a, int target) {
        int lo = 0, hi = a.length - 1;
        while (lo <= hi) {
            int mid = (lo + hi) >>> 1;
            if (a[mid] == target) return mid;
            if (a[lo] <= a[mid]) {
                if (a[lo] <= target && target < a[mid]) hi = mid - 1;
                else lo = mid + 1;
            } else {
                if (a[mid] < target && target <= a[hi]) lo = mid + 1;
                else hi = mid - 1;
            }
        }
        return -1;
    }

    // 13. 首末位置：两个 lower bound
    static int[] searchRange(int[] a, int target) {
        int lower = lowerBound(a, target);
        if (lower == a.length || a[lower] != target) return new int[]{-1, -1};
        int upper = target == Integer.MAX_VALUE ? a.length : lowerBound(a, target + 1L);
        return new int[]{lower, upper - 1};
    }

    private static int lowerBound(int[] a, long target) {
        int lo = 0, hi = a.length;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (a[mid] < target) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }

    // 14. 有效的括号
    static boolean isValidBrackets(String s) {
        if (s.length() % 2 == 1) return false;
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            switch (c) {
                case '(' -> stack.push(')');
                case '[' -> stack.push(']');
                case '{' -> stack.push('}');
                default -> {
                    if (stack.isEmpty() || stack.pop() != c) return false;
                }
            }
        }
        return stack.isEmpty();
    }

    // 15. 每日温度：递减栈
    static int[] dailyTemperatures(int[] t) {
        int[] out = new int[t.length];
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < t.length; i++) {
            while (!stack.isEmpty() && t[stack.peek()] < t[i]) {
                int top = stack.pop();
                out[top] = i - top;
            }
            stack.push(i);
        }
        return out;
    }

    // 16. 柱状图最大矩形：单调栈 + 虚拟 0/-1
    static long largestRectangle(int[] h) {
        Deque<Integer> stack = new ArrayDeque<>();
        long best = 0;
        for (int i = 0; i <= h.length; i++) {
            int cur = i == h.length ? 0 : h[i];
            while (!stack.isEmpty() && h[stack.peek()] > cur) {
                int height = h[stack.pop()];
                int left = stack.isEmpty() ? -1 : stack.peek();
                best = Math.max(best, (long) height * (i - left - 1));
            }
            stack.push(i);
        }
        return best;
    }

    // 17-20：链表节点
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
        }
    }

    static ListNode reverseList(ListNode head) {
        ListNode prev = null, cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }

    static ListNode mergeTwoLists(ListNode a, ListNode b) {
        ListNode sentinel = new ListNode(0), tail = sentinel;
        while (a != null && b != null) {
            if (a.val <= b.val) {
                tail.next = a;
                a = a.next;
            } else {
                tail.next = b;
                b = b.next;
            }
            tail = tail.next;
        }
        tail.next = a != null ? a : b;
        return sentinel.next;
    }

    static ListNode detectCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                slow = head;
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
        }
        return null;
    }

    static ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> heap = new PriorityQueue<>((x, y) -> Integer.compare(x.val, y.val));
        for (ListNode node : lists) if (node != null) heap.offer(node);
        ListNode sentinel = new ListNode(0), tail = sentinel;
        while (!heap.isEmpty()) {
            ListNode node = heap.poll();
            tail.next = node;
            tail = node;
            if (node.next != null) heap.offer(node.next);
        }
        return sentinel.next;
    }

    // 21. 第 K 个最大元素：快速选择（随机枢轴）
    static int findKthLargest(int[] a, int k) {
        int target = a.length - k, lo = 0, hi = a.length - 1;
        while (lo < hi) {
            int pivot = lo + (int) (Math.random() * (hi - lo + 1));
            int stored = lo;
            swap(a, pivot, hi);
            for (int i = lo; i < hi; i++) {
                if (a[i] < a[hi]) swap(a, i, stored++);
            }
            swap(a, stored, hi);
            if (stored == target) return a[stored];
            if (stored < target) lo = stored + 1;
            else hi = stored - 1;
        }
        return a[lo];
    }

    private static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    // 22. 前 K 个高频元素：k 小顶堆（频率低/值大更差）
    static int[] topKFrequent(int[] a, int k) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int x : a) count.merge(x, 1, Integer::sum);
        PriorityQueue<int[]> heap = new PriorityQueue<>((x, y) ->
                x[1] != y[1] ? Integer.compare(x[1], y[1]) : Integer.compare(y[0], x[0]));
        for (Map.Entry<Integer, Integer> e : count.entrySet()) {
            heap.offer(new int[]{e.getKey(), e.getValue()});
            if (heap.size() > k) heap.poll();
        }
        int[] out = new int[k];
        for (int i = k - 1; i >= 0; i--) out[i] = heap.poll()[0];
        return out;
    }

    // 23-25：二叉树
    static class TreeNode {
        int val;
        TreeNode left, right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    static TreeNode buildTree(Integer[] level, List<TreeNode> allNodes) {
        if (level.length == 0 || level[0] == null) return null;
        TreeNode root = new TreeNode(level[0]);
        allNodes.add(root);
        java.util.Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        int i = 1;
        while (!queue.isEmpty() && i < level.length) {
            TreeNode node = queue.poll();
            if (i < level.length) {
                if (level[i] != null) {
                    node.left = new TreeNode(level[i]);
                    allNodes.add(node.left);
                    queue.offer(node.left);
                }
                i++;
            }
            if (i < level.length) {
                if (level[i] != null) {
                    node.right = new TreeNode(level[i]);
                    allNodes.add(node.right);
                    queue.offer(node.right);
                }
                i++;
            }
        }
        return root;
    }

    static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> out = new ArrayList<>();
        if (root == null) return out;
        java.util.Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            out.add(level);
        }
        return out;
    }

    static boolean isValidBST(TreeNode root) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;
        long prev = 0;
        boolean hasPrev = false;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            if (hasPrev && cur.val <= prev) return false;
            prev = cur.val;
            hasPrev = true;
            cur = cur.right;
        }
        return true;
    }

    static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) return root;
        return left != null ? left : right;
    }

    // 26. 岛屿数量：BFS 淹没
    static int numIslands(char[][] grid) {
        int count = 0;
        int m = grid.length, n = m > 0 ? grid[0].length : 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != '1') continue;
                count++;
                Deque<int[]> queue = new ArrayDeque<>();
                grid[i][j] = '0';
                queue.offer(new int[]{i, j});
                while (!queue.isEmpty()) {
                    int[] cell = queue.poll();
                    if (cell[0] > 0 && grid[cell[0] - 1][cell[1]] == '1') {
                        grid[cell[0] - 1][cell[1]] = '0';
                        queue.offer(new int[]{cell[0] - 1, cell[1]});
                    }
                    if (cell[0] + 1 < m && grid[cell[0] + 1][cell[1]] == '1') {
                        grid[cell[0] + 1][cell[1]] = '0';
                        queue.offer(new int[]{cell[0] + 1, cell[1]});
                    }
                    if (cell[1] > 0 && grid[cell[0]][cell[1] - 1] == '1') {
                        grid[cell[0]][cell[1] - 1] = '0';
                        queue.offer(new int[]{cell[0], cell[1] - 1});
                    }
                    if (cell[1] + 1 < n && grid[cell[0]][cell[1] + 1] == '1') {
                        grid[cell[0]][cell[1] + 1] = '0';
                        queue.offer(new int[]{cell[0], cell[1] + 1});
                    }
                }
            }
        }
        return count;
    }

    // 27. 课程表：Kahn 入度
    static boolean canFinish(int v, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        int[] indegree = new int[v];
        for (int i = 0; i < v; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[1]).add(e[0]);
            indegree[e[0]]++;
        }
        Deque<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < v; i++) if (indegree[i] == 0) queue.offer(i);
        int processed = 0;
        while (!queue.isEmpty()) {
            int node = queue.poll();
            processed++;
            for (int next : adj.get(node)) {
                if (--indegree[next] == 0) queue.offer(next);
            }
        }
        return processed == v;
    }

    // 28. 零钱兑换
    static int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int x = 1; x <= amount; x++) {
            for (int coin : coins) {
                if (coin > 0 && coin <= x) dp[x] = Math.min(dp[x], dp[x - coin] + 1);
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }

    // 29. 最长递增子序列：tails 二分
    static int lengthOfLIS(int[] a) {
        int[] tails = new int[a.length];
        int size = 0;
        for (int x : a) {
            int lo = 0, hi = size;
            while (lo < hi) {
                int mid = (lo + hi) >>> 1;
                if (tails[mid] < x) lo = mid + 1;
                else hi = mid;
            }
            tails[lo] = x;
            if (lo == size) size++;
        }
        return size;
    }

    // 30. 编辑距离：滚动两行
    static int minDistance(String w1, String w2) {
        int m = w1.length(), n = w2.length();
        int[] prev = new int[n + 1], cur = new int[n + 1];
        for (int j = 0; j <= n; j++) prev[j] = j;
        for (int i = 1; i <= m; i++) {
            cur[0] = i;
            for (int j = 1; j <= n; j++) {
                if (w1.charAt(i - 1) == w2.charAt(j - 1)) cur[j] = prev[j - 1];
                else cur[j] = 1 + Math.min(prev[j - 1], Math.min(prev[j], cur[j - 1]));
            }
            int[] tmp = prev;
            prev = cur;
            cur = tmp;
        }
        return prev[n];
    }
}