// 第 11 周 – 实践课练习的参考答案
// 运行：go run ./w11/exercises
package main

import (
	"fmt"
	"slices"
	"strings"
)

// E1. 两数之和 – 用 map 实现 O(n)
func twoSum(a []int, target int) (int, int, bool) {
	seen := map[int]int{} // 值 -> 下标
	for i, x := range a {
		if j, ok := seen[target-x]; ok {
			return j, i, true
		}
		seen[x] = i
	}
	return 0, 0, false
}

// E2. 第一个不重复的字符
func firstUnique(s string) (rune, bool) {
	cnt := map[rune]int{}
	for _, c := range s {
		cnt[c]++
	}
	for _, c := range s { // map 的顺序是随机的，所以再遍历一次字符串
		if cnt[c] == 1 {
			return c, true
		}
	}
	return 0, false
}

// E3. 变位词分组
func groupAnagrams(words []string) [][]string {
	g := map[string][]string{}
	for _, w := range words {
		r := []rune(w)
		slices.Sort(r)
		g[string(r)] = append(g[string(r)], w)
	}
	keys := make([]string, 0, len(g))
	for k := range g {
		keys = append(keys, k)
	}
	slices.Sort(keys)
	var res [][]string
	for _, k := range keys {
		res = append(res, g[k])
	}
	return res
}

// E4. 是否有重复元素？
func hasDuplicate(a []int) bool {
	seen := map[int]bool{}
	for _, x := range a {
		if seen[x] {
			return true
		}
		seen[x] = true
	}
	return false
}

// E5. 括号 – 用切片实现栈，括号对存放在 map 中
func balanced(s string) bool {
	pair := map[rune]rune{')': '(', ']': '[', '}': '{'}
	var st []rune
	for _, c := range s {
		if strings.ContainsRune("([{", c) {
			st = append(st, c)
		} else if open, ok := pair[c]; ok {
			if len(st) == 0 || st[len(st)-1] != open {
				return false
			}
			st = st[:len(st)-1]
		}
	}
	return len(st) == 0
}

func main() {
	i, j, _ := twoSum([]int{2, 7, 11, 15}, 9)
	fmt.Println("E1. twoSum([2 7 11 15], 9) =", i, j)
	c, _ := firstUnique("swiss")
	fmt.Printf("E2. firstUnique(\"swiss\") = %c\n", c)
	fmt.Println("E3. groupAnagrams =", groupAnagrams([]string{"eat", "tea", "tan", "ate", "nat", "bat"}))
	fmt.Println("E4. hasDuplicate([1 2 3 1]) =", hasDuplicate([]int{1, 2, 3, 1}), ", [1 2 3] =", hasDuplicate([]int{1, 2, 3}))
	fmt.Println(`E5. balanced("{[()]}") =`, balanced("{[()]}"), `, balanced("([)]") =`, balanced("([)]"))
	pb := map[string]string{"Li Wei": "+86 27 1234 5678", "Eerenc Koczka": "+36 36 520 400", "Wang Fang": "+86 10 8765 4321"}
	num, ok := pb["Zhang San"]
	fmt.Println("E6. Wang Fang:", pb["Wang Fang"], ", Zhang San:", num, ok)
}