ACM退役了，接下来是考研的准备，刷刷leetcode保证不会生手，也算是调剂生活，初步计划是每天三题吧，希望可以坚持下去。
打算按照专题来做，先是Array。。。。本来以为特别水，结果。。。。
====================
今天做了
448 https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/?tab=Description
35 https://leetcode.com/problems/search-insert-position/?tab=Description
1 https://leetcode.com/problems/two-sum/?tab=Description
====================
448说的是
给你n个数字，每个数字不小于1不大于n，可能会有重复，输出1到n中没有在给定数组中出现过的数字。
我的思路：
很简单嘛，用一个n个数的一维数组标记下每个数字出现的次数就好了，O(n)
结果。。。leetcode居然用的是vector。。。而且输入输出都是vector。。。。。我写的不是整个程序居然是一个类。。。。输入居然没有给n的范围。。。
给的是vector，n可以用size得到，但是因为没有给n的范围，使用静态数组就不太好了，于是学习了下vector的使用方法，结果居然意外的很好使。。。。
下面是我的代码，时间复杂度O(n)，空间多开了n
1 #include<iostream> 2 #include<cstring> 3 #include<vector> 4 using namespace std; 5 class Solution { 6 public: 7 vector<int> findDisappearedNumbers(vector<int>& nums) { 8 int n=nums.size(); 9 vector<int> res; 10 for(int i=0;i<n;i++){ 11 res.push_back(0); 12 } 13 for(int i=0;i<n;i++){ 14 res[nums[i]-1]++; 15 } 16 int ptr=0; 17 for(int i=0;i<n;i++){ 18 if(res[i]==0){ 19 res[ptr++]=i+1; 20 } 21 } 22 res.resize(ptr); 23 return res; 24 } 25 };
代码提交后显示速度（126ms）击败了95%的用户，因为曾经是OI选手，对stl是深恶痛绝的，于是用指针又写了一版，企图击败99%的
1 #include<iostream> 2 #include<cstring> 3 #include<vector> 4 using namespace std; 5 class Solution { 6 public: 7 vector<int> findDisappearedNumbers(vector<int>& nums) { 8 int n=nums.size(); 9 int *temp=new int[n]; 10 memset(temp,0,sizeof(int)*n); 11 for (int i=0;i<n;i++) 12 temp[nums[i]-1]++; 13 vector<int> res; 14 for (int i=0;i<n;i++) 15 if(temp[i]==0) 16 res.push_back(i+1); 17 return res; 18 } 19 };
结果这一版（145ms）只击败了49%。。。。。。我就很迷茫了。。。。后来把下标换成迭代器
1 class Solution { 2 public: 3 vector<int> findDisappearedNumbers(vector<int>& nums) { 4 int n=nums.size(); 5 int *temp=new int[n]; 6 memset(temp,0,sizeof(int)*n); 7 for (vector<int>::iterator iter=nums.begin();iter!=nums.end();iter++) 8 temp[(*iter)-1]++; 9 vector<int> res; 10 for (int i=0;i<n;i++) 11 if(temp[i]==0) 12 res.push_back(i+1); 13 return res; 14 } 15 };
结果是（133ms）击败了77.4%的用户。。。。。虽然不太理解，不过不去纠结了。
我到讨论版去看了看，结果居然发现了空间O(1)的！！！！
因为题目里保证数字是非负非零的，我们可以用原始数组标记存在性，不用新开数组，如果某个数字存在，我们把原始数组的那个位置上的数字变为负数，厉害厉害。。。我提交了两遍这个“标程”结果一次跑了219ms一次跑了132ms。。。。机器不稳定不能怪我了23333
1 class Solution { 2 public: 3 vector<int> findDisappearedNumbers(vector<int>& nums) { 4 int len = nums.size(); 5 for(int i=0; i<len; i++) { 6 int m = abs(nums[i])-1; // index start from 0 7 nums[m] = nums[m]>0 ? -nums[m] : nums[m]; 8 } 9 vector<int> res; 10 for(int i = 0; i<len; i++) { 11 if(nums[i] > 0) res.push_back(i+1); 12 } 13 return res; 14 } 15 };
=========================================
35说的是
给你n个升序数字，再给你一个目标数字target，问你当target被插入到现有数组时应该被放在哪儿，输出下标。（有相同的尽量往前放）
我的思路
其实没什么好说的，就是基本的二分查找
1 class Solution { 2 public: 3 int searchInsert(vector<int>& nums, int target) { 4 int l=0,r=nums.size()-1; 5 while(l<=r){ 6 int mid=(l+r)/2; 7 if(nums[mid]==target)return mid; 8 else if(nums[mid]<target)l=mid+1; 9 else r=mid-1; 10 } 11 return l; 12 } 13 };
后来看讨论的时候，发现一个人是这么求mid的
int mid = low + (high-low)/2;
感觉很妙啊！！这样就可以避免相加后越界的问题了，66666
============================================
1说的是
给你n个数字（无序，可能重复），和一个数字target，在这n个数字中一定存在且只存在一组数字，相加等于target，输出他们的下标
我的思路
这题上来就想O（n^2）暴力，后来想了想如果只存在一组，那么排序后可以从两边往中间逼近，这样就是O(nlogn)啦！
1 bool mycmp(const int &a,const int &b){ 2 return a<b; 3 } 4 class Solution { 5 public: 6 /* 7 bool mycmp(const int &a,const int &b){ 8 return a<b; 9 } 10 */ 11 friend bool mycmp(const int &a,const int &b); 12 vector<int> twoSum(vector<int>& nums, int target) { 13 int n=nums.size(); 14 vector<int> mynum(nums); 15 sort(mynum.begin(),mynum.end(),mycmp); 16 int myend=n-1,mybegin=0; 17 vector<int> aim; 18 while(1){ 19 while(mynum[mybegin]+mynum[myend]>target) 20 myend--; 21 while(mynum[mybegin]+mynum[myend]<target) 22 mybegin++; 23 if(mynum[mybegin]+mynum[myend]==target){ 24 for(int i=0;i<n;i++){ 25 if(nums[i]==mynum[mybegin]){aim.push_back(i);continue;} 26 if(nums[i]==mynum[myend])aim.push_back(i); 27 } 28 break; 29 } 30 } 31 return aim; 32 } 33 };
结果没写过vector的sort。。。废了不少时间去搜博客，最后还是不明白为什么mycmp函数写在类内部就不行（即使是公有成员），必须写成友元函数。。。不是很懂。当然除了这种方法还可以直接把sort的第三个参数mycmp换成less<int>()也是可以的，但是希望自己定制策略嘛。
后来看了讨论，发现居然有O(n)的，当时就震惊了（中国99%的人不知道）。。。
原来是用hash来在线处理。。。。傻了，居然没有想到在线的方法。。。。
1 vector<int> twoSum(vector<int> &numbers, int target) 2 { 3 //Key is the number and value is its index in the vector. 4 unordered_map<int, int> hash; 5 vector<int> result; 6 for (int i = 0; i < numbers.size(); i++) { 7 int numberToFind = target - numbers[i]; 8 9 //if numberToFind is found in map, return them 10 if (hash.find(numberToFind) != hash.end()) { 11 //+1 because indices are NOT zero based 12 result.push_back(hash[numberToFind] + 1); 13 result.push_back(i + 1); 14 return result; 15 } 16 17 //number was not found. Put it in the map. 18 hash[numbers[i]] = i; 19 } 20 return result; 21 }
这里用到了unordered_map，第一次见，好神奇，O(n)的hash，get
原文：http://www.cnblogs.com/xuwangzihao/p/6498234.html
