2017-3-8 leetcode 380 381 532

l两周以来，第一次睡了个爽，开心！

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

leetcode380 https://leetcode.com/problems/insert-delete-getrandom-o1/?tab=Description

leetcode381 https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/

leetcode532 https://leetcode.com/problems/k-diff-pairs-in-an-array/?tab=Description

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

380讲的是
设计一个数据结构，要求可以在O(1)的时间内完成以下操作
1，插入一个数字（如果不存在的话）
2，删除一个数字（如果存在的话）
3，随机返回一个数字（要求已存在的数字被返回的概率均等）

我的思路
一开始其实是一脸懵逼的，后来看了讨论版才明白。。
如果只有前两个要求，就是普通的hash表，连冲突处理都不需要，加上第三个要求后，要求把数据映射在0——n-1上，那就双向hash好了。。。
用a数组来存储数据，无序的
用unordered_map v来存贮数据在a中的下标，可以实现O(1)的数据定位。
插入简单，删除的时候永远删掉“a中最后的数据”，如果目标数据不是最后的，只需要把它换到最后就好，注意map中存的下标值也随之改变了

 class RandomizedSet {

 public:

     vector<int> a;

     unordered_map<int,int> v;

     int n;

     /** Initialize your data structure here. */

     RandomizedSet() {

         a.clear();

         v.clear();

         srand(time(NULL));

         n=;

     }

     /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */

     bool insert(int val) {

         if(v.find(val)!=v.end())return false;

         a.push_back(val);

         v[val]=n++;

         return true;

     }

     /** Removes a value from the set. Returns true if the set contained the specified element. */

     bool remove(int val) {

         if(v.find(val)==v.end())return false;

         unordered_map<int,int>::iterator it=v.find(val);

         int ptr=it->second;

         if(ptr!=n-){

             v[a[n-]]=ptr;

             a[ptr]=a[n-];

         }

         v.erase(it);

         a.resize(--n);

         return true;

     }

     /** Get a random element from the set. */

     int getRandom() {

         int ptr=rand()%n;

         return a[ptr];

     }

 };

 /**

  * Your RandomizedSet object will be instantiated and called as such:

  * RandomizedSet obj = new RandomizedSet();

  * bool param_1 = obj.insert(val);

  * bool param_2 = obj.remove(val);

  * int param_3 = obj.getRandom();

  */

380

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

381讲的是
设计一个允许重复数据的数据结构，要求可以在O(1)的时间内完成以下操作
1，插入一个数字（如果存在的话返回false）
2，删除一个数字（如果存在的话返回true）
3，随机返回一个数字（要求已存在的数字被返回的概率均等）

我的思路
一开始感觉直接直接把380的代码改成multimap就行，结果交了一发发现行不通，a中最后一个数据不知道对应在map中的哪儿（因为可能有多个）
多个数据的话我们在map中使用vector来存储就可以，为了O(1)定位，我们在a中使用pair来存储val和map第二维的下标
思考后发现a.back()代表的val一定是相同值最后一次出现的，所以我们只要交换m.find(val).back()和m[a.back().val][a.back().index]就行

 class RandomizedCollection {

 public:

     /** Initialize your data structure here. */

     RandomizedCollection() {

     }

     /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */

     bool insert(int val) {

         auto result = m.find(val) == m.end();

         m[val].push_back(nums.size());

         nums.push_back(pair<int, int>(val, m[val].size() - ));

         return result;

     }

     /** Removes a value from the collection. Returns true if the collection contained the specified element. */

     bool remove(int val) {

         auto result = m.find(val) != m.end();

         if(result)

         {

             auto last = nums.back();

             m[last.first][last.second] = m[val].back();

             nums[m[val].back()] = last;

             m[val].pop_back();

             if(m[val].empty()) m.erase(val);

             nums.pop_back();

         }

         return result;

     }

     /** Get a random element from the collection. */

     int getRandom() {

         return nums[rand() % nums.size()].first;

     }

 private:

     vector<pair<int, int>> nums;

     unordered_map<int, vector<int>> m;

 };

code from the other people

 class RandomizedCollection {

 private:

     vector<pair<int,int>> a;

     unordered_map<int,vector<int> > m;

     int n;

 public:

     /** Initialize your data structure here. */

     RandomizedCollection() {

         a.clear();

         m.clear();

         srand(time(NULL));

     }

     /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */

     bool insert(int val) {

         bool result=(m.find(val)==m.end());

         m[val].push_back(a.size());

         a.push_back(pair<int,int>(val,m[val].size()-));

         return result;

     }

     /** Removes a value from the collection. Returns true if the collection contained the specified element. */

     bool remove(int val) {

         bool result=(m.find(val)!=m.end());

         if(result){

             pair<int,int> last=a.back();

             if(a.back().first!=val){

                 m[last.first][last.second]=m[val].back();

                 a[m[val].back()]=a.back();

             }

             a.pop_back();

             m[val].pop_back();

             if(m[val].empty())m.erase(val);

         }

         return result;

     }

     /** Get a random element from the collection. */

     int getRandom() {

         if(!a.size())return -;

         int ptr=rand()%a.size();

         return a[ptr].first;

     }

 };

 /**

  * Your RandomizedCollection object will be instantiated and called as such:

  * RandomizedCollection obj = new RandomizedCollection();

  * bool param_1 = obj.insert(val);

  * bool param_2 = obj.remove(val);

  * int param_3 = obj.getRandom();

  */

My Code

RE一万年，发现是忽略了“remove时如果m[val]已经被删空，应该erase掉”这种情况

还是挺有趣的一道题目。

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

532讲的是
输入n个数字a[i]（无序，-1e7<=a[i]<=1e7，n<=1e4）和一个数字k，问你其中有多少不同的数对。
数对的定义：(i,j)是数对当且仅当abs(i-j)==k

我的思路
暴力的话就是排序去重，然后一个个压到hash中判断加减k是否有数据。O(nlogn)
后来想了想，感觉O{n}也可以，永远用后进入的数字来匹配之前的，就可以保证不重复。（如果有重复的数字要进入，就跳过）。
然后发现k居然可以等于0，丧心病狂，分开处理好了。。。

 class Solution {

 public:

     int findPairs(vector<int>& nums, int k) {

         int ans=;

         int n=nums.size();

         if(n<)return ;

         unordered_map<int,int> m;

         if(k){

             if(k<)return ;

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

                 int temp=nums[i],aim;

                 if(m.find(temp)!=m.end())continue;

                 aim=temp+k;

                 if(m.find(aim)!=m.end())ans++;

                 aim=temp-k;

                 if(m.find(aim)!=m.end())ans++;

                 m[temp]=;

             }

         }else{

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

                 int temp=nums[i];

                 if(m.find(temp)!=m.end()){

                     if(m[temp]==){

                         ans++;

                         m[temp]++;

                     }

                 }else{

                     m[temp]=;

                 }

             }

         }

         return ans;

     }

 };

532

又是一道可以用python一行解决的题目（害怕）

 def findPairs(self, nums, k):

        return len(set(nums)&{n+k for n in nums}) if k>0 else sum(v>1 for v in collections.Counter(nums).values()) if k==0 else 0

展开是这样的

 def findPairs(self, nums, k):

         if k>0:

             return len(set(nums)&set(n+k for n in nums))

         elif k==0:

             return sum(v>1 for v in collections.Counter(nums).values())

         else:

             return 0

巴特西

2017-3-8 leetcode 380 381 532

最新文章

热门文章