// 第 11 周 – 实践课练习的参考答案
// 运行：java Exercises11.java
import java.util.*;

public class Exercises11 {

    // E1. 两数之和：是否有两个元素之和等于 target?– 用哈希表 O(n)（而不是 O(n²)）
    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 null;
    }

    // E2. 第一个不重复的字符
    static Character firstUnique(String s) {
        Map<Character, Integer> c = new LinkedHashMap<>(); // 保持插入顺序的哈希表
        for (char ch : s.toCharArray()) c.merge(ch, 1, Integer::sum);
        for (Map.Entry<Character, Integer> e : c.entrySet()) if (e.getValue() == 1) return e.getKey();
        return null;
    }

    // E3. 变位词分组：键是单词排序后的字母
    static Collection<List<String>> groupAnagrams(String[] words) {
        Map<String, List<String>> g = new TreeMap<>();
        for (String w : words) {
            char[] cs = w.toCharArray();
            Arrays.sort(cs);
            g.computeIfAbsent(new String(cs), k -> new ArrayList<>()).add(w);
        }
        return g.values();
    }

    // E4. 是否有重复元素？– 平均 O(n)
    static boolean hasDuplicate(int[] a) {
        Set<Integer> s = new HashSet<>();
        for (int x : a) if (!s.add(x)) return true; // 如果元素已经在集合中，add 返回 false
        return false;
    }

    // E5. 括号：括号对存放在 map 中；栈是 ArrayDeque（同一个 ADT）
    static boolean balanced(String s) {
        Deque<Character> st = new ArrayDeque<>();
        Map<Character, Character> pair = Map.of(')', '(', ']', '[', '}', '{');
        for (char c : s.toCharArray()) {
            if ("([{".indexOf(c) >= 0) st.push(c);
            else if (pair.containsKey(c) && (st.isEmpty() || st.pop() != pair.get(c))) return false;
        }
        return st.isEmpty();
    }

    // E6. 电话簿：姓名 -> 号码，按姓名查找
    static void phoneBook() {
        Map<String, String> pb = new HashMap<>();
        pb.put("Li Wei", "+86 27 1234 5678");
        pb.put("Ferenc Koczka", "+36 36 520 400");
        pb.put("Wang Fang", "+86 10 8765 4321");
        System.out.println("  Wang Fang: " + pb.get("Wang Fang") + ", Zhang San: " + pb.getOrDefault("Zhang San", "no such name"));
    }

    public static void main(String[] args) {
        System.out.println("E1. twoSum([2,7,11,15], 9) = " + Arrays.toString(twoSum(new int[] { 2, 7, 11, 15 }, 9)));
        System.out.println("E2. firstUnique(\"swiss\") = " + firstUnique("swiss"));
        System.out.println("E3. groupAnagrams = " + groupAnagrams(new String[] { "eat", "tea", "tan", "ate", "nat", "bat" }));
        System.out.println("E4. hasDuplicate([1,2,3,1]) = " + hasDuplicate(new int[] { 1, 2, 3, 1 }) + ", [1,2,3] = " + hasDuplicate(new int[] { 1, 2, 3 }));
        System.out.println("E5. balanced(\"{[()]}\") = " + balanced("{[()]}") + ", balanced(\"([)]\") = " + balanced("([)]"));
        System.out.println("E6. phone book:");
        phoneBook();
    }
}