散列表 2019-04-15

散列表（哈希表）
1.实现一个基于链表法解决冲突问题的散列表
2.实现一个 LRU 缓存淘汰算法

对应练习题
哈希思想实现：
1.两数之和(1)
https://leetcode-cn.com/problems/two-sum/

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        //构造一个哈希数组m，一个指针数值
        unordered_map<int, int> m;
        vector<int> res;
        //遍历nums，建立索引
        for (int i = 0; i < nums.size(); ++i) {
            m[nums[i]] = i;
        }
        //查找和值为target的整数所在下标
        for (int i = 0; i < nums.size(); ++i) {
            int t = target - nums[i];
            //判断查找到的数字是不是第一个出现的数字，不是就OK（比如4=2+2，需要t是第二个2） 压栈存下标
            if (m.count(t) && m[t] != i) {
                res.push_back(i);
                res.push_back(m[t]);
                break;
            }
        }
        return res;
    }
};

2.Happy Number(202)
https://leetcode-cn.com/problems/happy-number/
如果出现了4，则这个数就不可能是快乐数了。

class Solution {
public:
    bool isHappy(int n) {
        //hash无序 值即键 表
        unordered_set<int> st;
        while (n != 1) {
            int sum = 0;
            while (n) {
                sum += (n % 10) * (n % 10);
                n /= 10;
            }
            n = sum;
            if (st.count(n)) break;
            st.insert(n);
        }
        return n == 1;
    }
};