594. 最长和谐子序列
和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是1。
现在，给定一个整数数组，你需要在所有可能的子序列中找到最长的和谐子序列的长度。
示例 1:
输入: [1,3,2,2,5,2,3,7]
输出: 5
原因: 最长的和谐数组是：[3,2,2,2,3].
说明: 输入的数组长度最大不超过20,000.
第一版，犯糊涂了，要用有序的map才对，中规中矩
执行用时 :136 ms, 在所有 cpp 提交中击败了59.33%的用户
内存消耗 :20.7 MB, 在所有 cpp 提交中击败了51.40%的用户
intfindLHS(vector<int>&nums) {
if (nums.size() <=1) return0;
sort(nums.begin(), nums.end(), greater<int>());
map<int, int>result;//元素，次数
intmaxLen=0, temp,len=nums.size();
for (unsignedi=0; i<len; ++i) {
result[nums[i]]++;
}
for (autobeg=result.begin(), beg2=++result.begin(); beg2!=result.end() &&beg!=result.end();++beg,++beg2 ) {
if (1+beg->first==beg2->first) {
temp=beg->second+beg2->second;
maxLen=temp>maxLen?temp : maxLen;
// cout << maxLen << endl;
// cout << beg->first << " " << beg2->first << " " << temp << endl;
}
}
// cout << maxLen << endl;
returnmaxLen;
}
204. 计数质数
统计所有小于非负整数 n 的质数的数量。
示例:
输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
第一版，暴力法，超时
intisPrimes(inti) {
for (intj=2; j*j<=i; ++j) {
if (i%j==0) return0;
}
return1;
}
intcountPrimes(intn) {
if (n<=2) return0;
intsum=0;
for (inti=2; i<n; ++i) {
sum+=isPrimes(i);
}
returnsum;
}
第二版，比较牛逼的一种解法
执行用时 :40 ms, 在所有 cpp 提交中击败了91.18%的用户
内存消耗 :21.6 MB, 在所有 cpp 提交中击败了5.23%的用户
这题搜到一个非常牛逼的算法,叫做厄拉多塞筛法. 比如说求20以内质数的个数,首先0,1不是质数.2是第一个质数,然后把20以内所有2的倍数划去.2后面紧跟的数即为下一个质数3,然后把3所有的倍数划去.3后面紧跟的数即为下一个质数5,再把5所有的倍数划去.以此类推.
intcountPrimes(intn) {
vector<int>a(n);
intcount=0;
for (inti=2; i<n; i++)
a[i] =1;
for (inti=2; i<n; i++)
if (a[i])
{
count++;
for (intj=2*i; j<n; j+=i)
a[j] =0;
}
returncount;
}
