哈希表-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