虽说周末要早起来着，但是日子过得有点奇怪，一不小心就忘掉了。。。
leetcode414 https://leetcode.com/problems/third-maximum-number/?tab=Description
leetcode485 https://leetcode.com/problems/max-consecutive-ones/?tab=Description
leetcode495 https://leetcode.com/problems/teemo-attacking/?tab=Description
======================================
414说的是
给你n个数字（无序，有重复），输出第三大的数，如果没有，输出最大的，使用O(n)的算法。注意，你的排序中不能有相同的，也就是说如果输入2，3，2，3，我们要输出3，因为没有第三大的数字。
我的思路
这题目，一下子就会想到堆priority_queue，但是堆是nlogn的，好吧，手动维护三个数字分别表示最大、次大、次次大好了，但是初始化设成什么值好呢，用0x80 memset一下好了，得到的是-1e9，感觉 够大了。
1 class Solution { 2 public: 3 int thirdMax(vector<int>& nums) { 4 int aim[4]; 5 int n=nums.size(); 6 memset(aim,0x80,sizeof(aim)); 7 for(int i=0;i<n;i++){ 8 if(nums[i]>aim[0]){ 9 aim[2]=aim[1]; 10 aim[1]=aim[0]; 11 aim[0]=nums[i]; 12 } 13 if(aim[0]>nums[i]&&nums[i]>aim[1]){ 14 aim[2]=aim[1]; 15 aim[1]=nums[i]; 16 } 17 if(aim[1]>nums[i]&&nums[i]>aim[2]){ 18 aim[2]=nums[i]; 19 } 20 } 21 return aim[2]==aim[3]?aim[0]:aim[2]; 22 } 23 };
结果提交了一次，返回了WA，人家有数据是-2e9的。。。。好吧，那就写标记，用给的元素维护赋初值好了。
1 class Solution { 2 public: 3 void swap(int &x,int &y){ 4 x^=y;y^=x;x^=y; 5 } 6 int thirdMax(vector<int>& nums) { 7 int aim[3],flag=0; 8 int n=nums.size(); 9 memset(aim,0x80,sizeof(aim)); 10 for(int i=0;i<n;i++){ 11 if(flag==0){ 12 aim[0]=nums[i]; 13 flag++; 14 continue; 15 } 16 if(flag==1){ 17 if(nums[i]==aim[0])continue; 18 aim[1]=nums[i]; 19 if(aim[0]<aim[1])swap(aim[0],aim[1]); 20 flag++; 21 continue; 22 } 23 if(flag==2){ 24 if(nums[i]==aim[0]||nums[i]==aim[1])continue; 25 if(nums[i]>aim[0]){ 26 aim[2]=aim[1]; 27 aim[1]=aim[0]; 28 aim[0]=nums[i]; 29 }else if(aim[0]>nums[i]&&nums[i]>aim[1]){ 30 aim[2]=aim[1]; 31 aim[1]=nums[i]; 32 }else aim[2]=nums[i]; 33 flag++; 34 continue; 35 } 36 if(nums[i]>aim[0]){ 37 aim[2]=aim[1]; 38 aim[1]=aim[0]; 39 aim[0]=nums[i]; 40 } 41 if(aim[0]>nums[i]&&nums[i]>aim[1]){ 42 aim[2]=aim[1]; 43 aim[1]=nums[i]; 44 } 45 if(aim[1]>nums[i]&&nums[i]>aim[2]){ 46 aim[2]=nums[i]; 47 } 48 } 49 return flag!=3?aim[0]:aim[2]; 50 } 51 };
完成是完成了，这也太丑了吧。。。去学习学习别人的写法。结果发现了这个。。。。
1 int thirdMax(vector<int>& nums) { 2 set<int> top3; 3 for (int num : nums) 4 if (top3.insert(num).second && top3.size() > 3) 5 top3.erase(top3.begin()); 6 return top3.size() == 3 ? *top3.begin() : *top3.rbegin(); 7 }
（很优美。。。。不想折叠），虽然set确实提供了logn的复杂度用来插入和删除，但是我们只需要前3大的数据，所以set的size只需要有3就好，log3算是常数.。。。。。。。心悦诚服
=======================================
485说的是
给你一个数组，只由01组成，问你最长的连续的1有多长
我的思路
没有思路，暴力出奇迹，扫一遍就好。
1 class Solution { 2 public: 3 int findMaxConsecutiveOnes(vector<int>& nums) { 4 int n=nums.size(),temp=0,aim=0; 5 for(int i=0;i<n;i++){ 6 if(nums[i])temp++; 7 else{ 8 aim=max(aim,temp); 9 temp=0; 10 } 11 } 12 aim=max(aim,temp); 13 return aim; 14 } 15 };
========================================
495说的是
有一个人的攻击可以让敌人中毒，毒会持续duration个时间单位，他会攻击很多次（不超过1e4），告诉你每次攻击的时间（非负，不超过1e7），问你敌人一共中毒中多久。
比如输入[1,2] 2 输出3
表示1秒2秒各攻击一次，每次中毒持续2秒，敌人一共中毒3秒
我的思路：
因为数据没有保证有序，先排序一下，然后扫一遍，记录每一个中毒区间的头尾，在出区间的时候统一计算时间加到答案里。复杂度O(nlogn)
1 class Solution { 2 public: 3 int findPoisonedDuration(vector<int>& timeSeries, int duration) { 4 vector<int> nums(timeSeries); 5 int n=nums.size(); 6 sort(nums.begin(),nums.end(),less<int>()); 7 int aim=0,st=-1,et=-1; 8 for(int i=0;i<n;i++){ 9 if(nums[i]>et){ 10 aim+=et-st; 11 st=nums[i]; 12 et=st+duration; 13 }else{ 14 et=nums[i]+duration; 15 } 16 } 17 aim+=et-st; 18 return aim; 19 } 20 };
很不开心啊。。。发现居然（75ms）只击败了27.6%不开心啊，看了看讨论版，发现别人的代码好像没有排序，我去题面看了看，人家加粗了一个单词“ascending ”，我当时不明白，以为是攻击力会提升，，，，现在明白了，人家说的是升序给出攻击时间序列2333333
好吧，去掉sort后63ms，击败了67%。。。。就这样吧，毕竟评测机不稳定。。。