# 基础

常用数据结构：

数组，有限确定项，比如字母串
map，映射
set，集合

Go的map底层使用哈希表实现，set可通过将map的value置空实现。
C++的std::map/std::multimap由红黑树实现，std::unorderd_map由哈希表实现。

# 实践

# 数组判断有效字母异位词

有效的字母异位词

数组直接存储

func isAnagram(s string, t string) bool {
    var a,b [26]int
    for _, i:= range s {
        a[i-'a']++
    }
    for _, i:= range t {
        b[i-'a']++
    }
    return a==b
}

# 赎金信

有效的字母异位词

数组直接存储

func canConstruct(ransomNote string, magazine string) bool {
    var r [26]int
    for _, c := range magazine {
        r[c - 'a']++
    }
    for _, c := range ransomNote {
        if r[c - 'a'] == 0 {
            return false
        }
        r[c - 'a']--
    }
    return true
}

# 集合判断数组相交

两个数组的交集

集合存储

type Set map[int]struct{}

func (s Set)Add(n int) {
    s[n] = struct{}{}
}

func (s Set)And(t Set) []int {
    ret := []int{}
    if len(s) > len(t) {
        s, t = t, s
    }
    for k := range s {
        if _, ok := t[k]; ok {
            ret = append(ret, k)
        } 
    }
    return ret
}

func intersection(nums1 []int, nums2 []int) []int {
    a, b := Set{}, Set{}
    for _, n := range nums1 {
        a.Add(n)
    }
    for _, n := range nums2 {
        b.Add(n)
    }
    return a.And(b)
}

# 集合判断快乐数

快乐数

集合存储

func happy(n int) int {
    sum := 0
    for n > 0 {
        s := n % 10
        sum += s * s
        n /= 10
    }
    return sum
}

func isHappy(n int) bool {
   set := map[int]struct{}{}
   for {
       sum := happy(n)
       if sum == 1 {
           return true
       }
       if _, ok := set[sum]; ok {
           return false
       } else {
           set[sum] = struct{}{}
       }
       n = sum
   }
}

# 映射存储两数之和

两数之和

func twoSum(nums []int, target int) []int {
    m := map[int]int{}
    for i, n := range nums {
        if v, ok := m[target - n]; ok {
            return []int{v, i}
        }
        m[n] = i
    }
    return []int{}
}

class Solution {
public:
    /**
     * 
     * @param numbers int整型vector 
     * @param target int整型 
     * @return int整型vector
     */
    vector<int> twoSum(vector<int>& numbers, int target) {
        std::map<int, int> h;
        int tmp = 0;
        for (int i = 0; i < numbers.size(); i++) {
            tmp = numbers[i];
            auto it = h.find(target - tmp);
            if (it != h.end()) {
                return vector<int>{h[target - tmp] + 1, i + 1};
            }
            h[tmp] = i;
        }
        return vector<int>{};
    }
};

# 映射统计四数相加结果次数

四数相加 II

func fourSumCount(A []int, B []int, C []int, D []int) int {
    m := map[int]int{}
    for _, a := range A {
        for _, b := range B {
            m[a + b]++
        }
    }
    count := 0 
    for _, c := range C {
        for _, d := range D {
            if v, ok := m[-c-d]; ok {
                count += v
            }
        }
    }
    return count
}

# 员工的重要性

员工的重要性

/**
 * Definition for Employee.
 * type Employee struct {
 *     Id int
 *     Importance int
 *     Subordinates []int
 * }
 */

func getImportance(employees []*Employee, id int) int {
    m := make(map[int]*Employee)
    for _, e := range employees {
        m[e.Id] = e
    }
    count := 0
    queue := []int{}
    queue = append(queue, id)
    for len(queue) > 0 {
        id = queue[0]
        queue = queue[1:]
        if e, ok := m[id]; ok {
            count += e.Importance
            for _, sub := range e.Subordinates {
                queue = append(queue, sub)
            }
        }
    }
    return count
}

Previous post: 算法基础 - 栈 Next post: 算法基础 - 数组

吹拉弹唱

# 基础

# 实践

# 数组判断有效字母异位词

# 赎金信

# 集合判断数组相交

# 集合判断快乐数

# 映射存储两数之和

# 映射统计四数相加结果次数

# 员工的重要性