ji那天好像是周六。。。。。吃完饭意识到貌似今天要有比赛(有题解当然要做啦),跑回寝室发现周日才开始233333
======================================================================
leetcode217 Contains Duplicate
leetcode219 Contains Duplicate II
leetcode228 Summary Ranges
=======================================================================
217讲的是
给你n个数字,判断下是否有重复的数据出现。
我的思路
丢到unordered_map里检查下就行。。。
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
int n=nums.size();
unordered_map<int,int> m;
for(int i=;i<n;i++){
if(m.find(nums[i])==m.end()){
m[nums[i]]=;
}else return true;
}
return false;
}
};
217
讨论版里没有什么新奇的思路。。。
=======================================================================
219讲的是
给你n个数字和一个数字k,判断下是否有重复的数据出现在任意长度为k的区间内。
也就是说如果有任意ij满足nums[i]==nums[j]&&abs(i-j)<=k则返回真
我的思路
丢到unordered_map里检查下就行。。。距离小于i-k的erase掉就好。。。
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
int n=nums.size();
unordered_map<int,int> m;
for(int i=;i<min(n,k+);i++){
if(m.find(nums[i])==m.end()){
m[nums[i]]=;
}else return true;
}
for(int i=min(n,k+);i<n;i++){
m.erase(nums[i-k-]);
if(m.find(nums[i])==m.end()){
m[nums[i]]=;
}else return true;
}
return false;
}
};
219
恩,其实这种判断元素存在性的题目,用set会更好些。
========================================================================
228讲的是
给你n个数字(有序,无重),把点转化为区间。
比如输入[0,1,2,4,5,7],输出["0->2","4->5","7"](字符串数组)
我的思路
线性的扫就好了。。。O(n)啊。。。不知道为什么难度被定义为中等。。
class Solution {
public:
vector<string> summaryRanges(vector<int>& nums) {
int n=nums.size();
vector<string> aim;
if(!n)return aim;
int s=nums[],t=nums[];
for(int i=;i<n;i++){
if(nums[i]!=nums[i-]+){
t=nums[i-];
char temp[];
if(s==t)
sprintf(temp,"%d",s);
else sprintf(temp,"%d->%d",s,t);
string s_temp(temp);
aim.push_back(s_temp);
s=nums[i];
}
}
t=nums[n-];
char temp[];
if(s==t)
sprintf(temp,"%d",s);
else sprintf(temp,"%d->%d",s,t);
string s_temp(temp);
aim.push_back(s_temp);
return aim;
}
};
228
我想使用to_string函数来着的,但是我的codeblocks一直报错。。。重装系统+VS当做官方IDE已经迫在眉睫了