// 11. hét – A gyakorlati feladatok megoldásai
// Futtatás: java Exercises11.java
import java.util.*;

public class Exercises11 {

    // F1. Két szám összege: van-e két elem, amelynek összege target? – O(n) hash halmazzal (O(n²) helyett)
    static int[] twoSum(int[] a, int target) {
        Map<Integer, Integer> seen = new HashMap<>(); // érték -> index
        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;
    }

    // F2. Az első nem ismétlődő karakter
    static Character firstUnique(String s) {
        Map<Character, Integer> c = new LinkedHashMap<>(); // beszúrási sorrendet megőrző hash tábla
        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;
    }

    // F3. Anagramma-csoportok: a kulcs a szó rendezett betűi
    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();
    }

    // F4. Van-e ismétlődés? – O(n) átlagosan
    static boolean hasDuplicate(int[] a) {
        Set<Integer> s = new HashSet<>();
        for (int x : a) if (!s.add(x)) return true; // az add hamisat ad, ha már benne volt
        return false;
    }

    // F5. Listás verem: zárójelek ellenőrzése a saját LinkedStack-kel helyett ArrayDeque-kel (ugyanaz az 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();
    }

    // F6. Telefonkönyv: név -> szám, keresés név szerint
    static void phoneBook() {
        Map<String, String> pb = new HashMap<>();
        pb.put("Li Wei", "+86 27 1234 5678");
        pb.put("Koczka Ferenc", "+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", "nincs ilyen név"));
    }

    public static void main(String[] args) {
        System.out.println("F1. twoSum([2,7,11,15], 9) = " + Arrays.toString(twoSum(new int[] { 2, 7, 11, 15 }, 9)));
        System.out.println("F2. firstUnique(\"swiss\") = " + firstUnique("swiss"));
        System.out.println("F3. groupAnagrams = " + groupAnagrams(new String[] { "eat", "tea", "tan", "ate", "nat", "bat" }));
        System.out.println("F4. hasDuplicate([1,2,3,1]) = " + hasDuplicate(new int[] { 1, 2, 3, 1 }) + ", [1,2,3] = " + hasDuplicate(new int[] { 1, 2, 3 }));
        System.out.println("F5. balanced(\"{[()]}\") = " + balanced("{[()]}") + ", balanced(\"([)]\") = " + balanced("([)]"));
        System.out.println("F6. telefonkönyv:");
        phoneBook();
    }
}