2017-3-3 leetcod 1 35 448

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

 #include<iostream>

 #include<cstring>

 #include<vector>

 using namespace std;

 class Solution {

 public:

     vector<int> findDisappearedNumbers(vector<int>& nums) {

         int n=nums.size();

         vector<int> res;

         for(int i=;i<n;i++){

             res.push_back();

         }

         for(int i=;i<n;i++){

             res[nums[i]-]++;

         }

         int ptr=;

         for(int i=;i<n;i++){

             if(res[i]==){

                 res[ptr++]=i+;

             }

         }

         res.resize(ptr);

         return res;

     }

 };

O(n)vector

代码提交后显示速度（126ms）击败了95%的用户，因为曾经是OI选手，对stl是深恶痛绝的，于是用指针又写了一版，企图击败99%的

 #include<iostream>

 #include<cstring>

 #include<vector>

 using namespace std;

 class Solution {

 public:

     vector<int> findDisappearedNumbers(vector<int>& nums) {

         int n=nums.size();

         int *temp=new int[n];

         memset(temp,,sizeof(int)*n);

         for (int i=;i<n;i++)

             temp[nums[i]-]++;

         vector<int> res;

         for (int i=;i<n;i++)

             if(temp[i]==)

                 res.push_back(i+);

         return res;

     }

 };

pointer

结果这一版（145ms）只击败了49%。。。。。。我就很迷茫了。。。。后来把下标换成迭代器

 class Solution {

 public:

     vector<int> findDisappearedNumbers(vector<int>& nums) {

         int n=nums.size();

         int *temp=new int[n];

         memset(temp,,sizeof(int)*n);

         for (vector<int>::iterator iter=nums.begin();iter!=nums.end();iter++)

             temp[(*iter)-]++;

         vector<int> res;

         for (int i=;i<n;i++)

             if(temp[i]==)

                 res.push_back(i+);

         return res;

     }

 };

iterator

结果是（133ms）击败了77.4%的用户。。。。。虽然不太理解，不过不去纠结了。
我到讨论版去看了看，结果居然发现了空间O(1)的！！！！
因为题目里保证数字是非负非零的，我们可以用原始数组标记存在性，不用新开数组，如果某个数字存在，我们把原始数组的那个位置上的数字变为负数，厉害厉害。。。我提交了两遍这个“标程”结果一次跑了219ms一次跑了132ms。。。。机器不稳定不能怪我了23333

 class Solution {

 public:

     vector<int> findDisappearedNumbers(vector<int>& nums) {

         int len = nums.size();

         for(int i=; i<len; i++) {

             int m = abs(nums[i])-; // index start from 0

             nums[m] = nums[m]> ? -nums[m] : nums[m];

         }

         vector<int> res;

         for(int i = ; i<len; i++) {

             if(nums[i] > ) res.push_back(i+);

         }

         return res;

     }

 };

space O(1)

=========================================

35说的是

给你n个升序数字，再给你一个目标数字target，问你当target被插入到现有数组时应该被放在哪儿，输出下标。（有相同的尽量往前放）

我的思路
其实没什么好说的，就是基本的二分查找

 class Solution {

 public:

     int searchInsert(vector<int>& nums, int target) {

         int l=,r=nums.size()-;

         while(l<=r){

             int mid=(l+r)/;

             if(nums[mid]==target)return mid;

             else if(nums[mid]<target)l=mid+;

             else r=mid-;

         }

         return l;

     }

 };

binary search

后来看讨论的时候，发现一个人是这么求mid的

int mid = low + (high-low)/2;

感觉很妙啊！！这样就可以避免相加后越界的问题了，66666

============================================

1说的是

给你n个数字（无序，可能重复），和一个数字target，在这n个数字中一定存在且只存在一组数字，相加等于target，输出他们的下标

我的思路
这题上来就想O（n^2）暴力，后来想了想如果只存在一组，那么排序后可以从两边往中间逼近，这样就是O(nlogn)啦！

 bool mycmp(const int &a,const int &b){

         return a<b;

 }

 class Solution {

 public:

     /*

     bool mycmp(const int &a,const int &b){

         return a<b;

     }

     */

     friend bool mycmp(const int &a,const int &b);

     vector<int> twoSum(vector<int>& nums, int target) {

         int n=nums.size();

         vector<int> mynum(nums);

         sort(mynum.begin(),mynum.end(),mycmp);

         int myend=n-,mybegin=;

         vector<int> aim;

         while(){

             while(mynum[mybegin]+mynum[myend]>target)

                 myend--;

             while(mynum[mybegin]+mynum[myend]<target)

                 mybegin++;

             if(mynum[mybegin]+mynum[myend]==target){

                 for(int i=;i<n;i++){

                     if(nums[i]==mynum[mybegin]){aim.push_back(i);continue;}

                     if(nums[i]==mynum[myend])aim.push_back(i);

                 }

                 break;

             }

         }

         return aim;

     }

 };

结果没写过vector的sort。。。废了不少时间去搜博客，最后还是不明白为什么mycmp函数写在类内部就不行（即使是公有成员），必须写成友元函数。。。不是很懂。当然除了这种方法还可以直接把sort的第三个参数mycmp换成less<int>()也是可以的，但是希望自己定制策略嘛。
后来看了讨论，发现居然有O(n)的，当时就震惊了（中国99%的人不知道）。。。
原来是用hash来在线处理。。。。傻了，居然没有想到在线的方法。。。。

 vector<int> twoSum(vector<int> &numbers, int target)

 {

     //Key is the number and value is its index in the vector.

     unordered_map<int, int> hash;

     vector<int> result;

     for (int i = ; i < numbers.size(); i++) {

         int numberToFind = target - numbers[i];

             //if numberToFind is found in map, return them

         if (hash.find(numberToFind) != hash.end()) {

                     //+1 because indices are NOT zero based

             result.push_back(hash[numberToFind] + );

             result.push_back(i + );

             return result;

         }

             //number was not found. Put it in the map.

         hash[numbers[i]] = i;

     }

     return result;

 }

hash

这里用到了unordered_map，第一次见，好神奇，O(n)的hash，get

巴特西

2017-3-3 leetcod 1 35 448

最新文章

热门文章