作者：TeddyZhang

哈希表：LeetCode #217 219 220 232

编程题

【LeetCode #217】存在重复元素

给定一个整数数组，判断是否存在重复元素。 如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。

示例 1: 输入: [1,2,3,1] 输出: true

解题思路：

第一种使用hash_set去重，第二种排序后检查相邻元素是否相等。

(哈希表)

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> set;
        for(auto num: nums){
            if(set.count(num)){
                return true;
            }else{
                set.insert(num);
            }
        }
        return false;
    }
};

(排序法)

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        if(nums.size() < 1) return false;
        sort(nums.begin(), nums.end(), [](const int &a, const int &b){
            return a < b;
        }); 
        for(int i = 0; i < nums.size()-1; i++){
            if(nums[i] == nums[i+1]) 
                return true;
        }
        return false;
    }
};

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/contains-duplicate

【LeetCode #219】存在重复元素II

给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的绝对值最大为 k。

示例 1: 输入: nums = [1,2,3,1], k = 3 输出: true 示例 2: 输入: nums = [1,0,1,1], k = 1 输出: true

解题思路：

使用哈希表，将每个数字的索引号存入哈希表，nums[i]为key, i为vlaue, 遍历数组，并查询哈希表，如果存在，即两数相同，则判断索引之间差值是否小于等于K, 如果是返回true，否则更新nums[i]所对应的索引，用于下一次的比较！

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> hashmap;
        for(int i = 0; i < nums.size(); i++){
            if(hashmap.count(nums[i])){
                if(i - hashmap[nums[i]] <= k){     //判断相同的值得索引差值
                    return true;
                }else{
                    hashmap[nums[i]] = i;  //更新nums[i]的索引
                }
            }else{
                hashmap.emplace(nums[i], i);
            }
        }
        return false;
    }
};

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/contains-duplicate-ii

【LeetCode #220】存在重复元素III

给定一个整数数组，判断数组中是否有两个不同的索引 i 和 j，使得 nums [i] 和 nums [j] 的差的绝对值最大为 t，并且 i 和 j 之间的差的绝对值最大为 ķ。

示例 1: 输入: nums = [1,2,3,1], k = 3, t = 0 输出: true

解题思路：

首先使用一个set作为一个滑动窗口，这样可以保证每个数的索引i和j之间差值小于等于k，然后另外一个条件是nums[i]和nums[j]的差的绝对值小于等于t，即 -t <= nums[i]-nums[j] <= t , 再进一步： nums[i] - t <= nums[j] <= nums[i] + t，也就是说在set中找到满足这个式子的i, j就可以返回true了！ 在STL库中，low_bound(type t)表示返回一个大于等于t的值，如果找不到就返回end() 因此在程序中，首先找到low_bound(nums[i]-t)，然后判断其是不是小于等于nums[i]+t，如果满足，则返回true，否则就继续移动长为k的滑动窗口寻找！

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        if(k < 1 || t < 0){
            return false;
        }
        int size = nums.size();
        if(size == 1)  return false;

        set<long long> s;
        int low = 0;
        for(int i = 0; i < size; i++){
            auto it = s.lower_bound((long long)nums[i]-t);
            if(it != s.end() && *it <= (long long)nums[i]+t){
                return true;
            }
            s.insert(nums[i]);     // 使得滑动窗口的大小不变
            if(s.size() == k+1){      
                s.erase(nums[low++]);
            }
        }
        return false;
    }
};

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/contains-duplicate-iii

【LeetCode #232】用栈实现队列

使用栈实现队列的下列操作： push(x) -- 将一个元素放入队列的尾部。 pop() -- 从队列首部移除元素。 peek() -- 返回队列首部的元素。 empty() -- 返回队列是否为空。

示例: MyQueue queue = new MyQueue(); queue.push(1); queue.push(2); queue.peek(); // 返回 1 queue.pop(); // 返回 1 queue.empty(); // 返回 false

解题思路：

用栈实现队列，十分简单，使用两个栈，一个为data栈，用于数据入队列，而另一个为tmp栈，用于数据出队列！

class MyQueue {
public:
    /** Initialize your data structure here. */
    stack<int> data;
    stack<int> tmp; 
    MyQueue() {}

    /** Push element x to the back of queue. */
    void push(int x) {
        data.push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        if(tmp.empty()){
            int size = data.size();
            while(size--){
                tmp.push(data.top());
                data.pop();
            }
        }
        int t = tmp.top();
        tmp.pop();
        return t;
    }

    /** Get the front element. */
    int peek() {
          if(tmp.empty()){
            int size = data.size();
            while(size--){
                tmp.push(data.top());
                data.pop();
            }
        }
        return tmp.top();      
    }

    /** Returns whether the queue is empty. */
    bool empty() {
        return data.empty() && tmp.empty();
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/implement-queue-using-stacks