专栏首页算法工程师之路哈希表-LeetCode 217、219、220、232(hashset、hashmap)

哈希表-LeetCode 217、219、220、232(hashset、hashmap)

作者: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

本文分享自微信公众号 - 算法工程师之路(Zleopard7319538),作者:TeddyZhang

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-11-15

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 最大堆,DP问题-LeetCode 373 374 376 377 605(DP,最大堆)

    给定两个以升序排列的整形数组 nums1 和 nums2, 以及一个整数 k。 定义一对值 (u,v),其中第一个元素来自 nums1,第二个元素来自 nums...

    算法工程师之路
  • gcd,哈希问题-LeetCode 357、355、365、367、380

    给定一个非负整数 n,计算各位数字都不同的数字 x 的个数,其中 0 ≤ x < 10n 。

    算法工程师之路
  • 单调栈-LeetCode 739、287(单调栈,桶计数)

    根据每日 气温 列表,请重新生成一个列表,对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高,请在该位置用 0 来代替。 例如,给定...

    算法工程师之路
  • 【LeetCode】两数之和

    Jacob丶
  • 剑指Offer题解

    在一个长度为n+1的数组里的所有数字都在1~n的范围内,所以数组中至少存在一个数字是重复的。 请找出数组中任意一个重复的数字,但不能修改输入的数组。 例如输...

    星如月勿忘初心
  • 查找数组中两数之和等于指定的数

    题目:给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

    Melody132
  • 【LeetCode】找出数组中重复的数字day01

    居士
  • 【LeetCode】136. Single Number

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • 【LeetCode】两数之和

    给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标。

    弗兰克的猫
  • Largest Number Greater Than Twice of Others

    思路1: 非排序,如果存在一个数,比其他任何数的两倍还大必然是最大数。时间复杂度为O(n2)O(n^2)

    用户1147447

扫码关注云+社区

领取腾讯云代金券