【每日一题】周末问题合并帖

本文最后更新于:2021年4月18日 晚上

【周六】LeetCode 220. 存在重复元素 III

思路

这题请教了一下学长,确定就是一个滑动窗口的延伸,也是动态的查询一个区间,每次都判断区间边界一边的点是否符合,如果不符合,再看看边界另一边的点是否符合,如果两者有一个符合,则可以直接返回true,否则的话就继续向下寻找,直到找出符合条件的值即可

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
typedef long long ll;
multiset<ll> s;
s.insert(1e18); s.insert(-1e18);
for(int i=0,j=0;i<nums.size();i++)
{
if(i-j>k) s.erase(s.find(nums[j++]));
int x=nums[i];
auto it =s.lower_bound(x);
if(*it -x<=t) return true;
--it;
if(x-*it<=t) return true;
s.insert(x);
}
return false;
}
};

【周日】LeetCode 26. 删除有序数组中的重复项

思路

这题是个纯模拟题,直接暴力枚举判定出来把符合条件的数存进一个新的数组(空间换时间)即可

C++代码

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int k=0;
for(int i=0;i<nums.size(); i++)
if(!i || nums[i] != nums[i-1])
nums[k++]=nums[i];
return k;
}
};