leetcode解题思路分析（四十四）380 - 387 题

Dear 丶 2022-12-13 01:24 288阅读 0赞

  1. 常数时间插入、删除和获取随机元素
    设计一个支持在平均 时间复杂度 O(1) 下，执行以下操作的数据结构。
    insert(val)：当元素 val 不存在时，向集合中插入该项。
    remove(val)：元素 val 存在时，从集合中移除该项。
    getRandom：随机返回现有集合中的一项。每个元素应该有相同的概率被返回。

    class RandomizedSet {
    public:

    1. RandomizedSet() { }
    2. bool insert(int val) { 
    3.     if (m.count(val)) return false;
    4.     nums.push_back(val);
    5.     m[val] = nums.size() - 1;
    6.     return true;
    7. }
    8. bool remove(int val) { 
    9.     if (!m.count(val)) return false;
    10.     int last = nums.back();
    11.     m[last] = m[val];
    12.     nums[m[val]] = last;
    13.     nums.pop_back();
    14.     m.erase(val);
    15.     return true;
    16. }
    17. int getRandom() { 
    18.     return nums[rand() % nums.size()];
    19. }

    private:

    1. vector<int> nums;
    2. unordered_map<int, int> m;

    };

  1. /** * 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(); */

  1. O(1) 时间插入、删除和获取随机元素 - 允许重复
    设计一个支持在平均 时间复杂度 O(1) 下， 执行以下操作的数据结构。注意: 允许出现重复元素。
    insert(val)：向集合中插入元素 val。
    remove(val)：当 val 存在时，从集合中移除一个 val。
    getRandom：从现有集合中随机获取一个元素。每个元素被返回的概率应该与其在集合中的数量呈线性相关

    class RandomizedCollection {
    public:

    1. /** Initialize your data structure here. */
    3. // 删除功能则相对复杂一点，首先通过hash表O(1)地找到删除目标在vector中的位置，然后为了避免vector删除中间元素时平移后面元素所需的线性耗时，我们在删除操作前将需要删除的元素与vector最后一个元素进行位置交换，此时需要删除的元素处在vector的尾部，删除之即可
    5. // 这里保存某个值 和 储存这个值的 vector indices
    6. unordered_map<int, unordered_set<int> > ump;
    7. vector<int> recs;
    9. RandomizedCollection() { 
    11. }
    13. /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
    14. bool insert(int val) { 
    15.     recs.push_back(val);
    16.     bool res = ump.find(val) == ump.end();
    18.     int index = recs.size() - 1;
    19.     ump[val].insert(index);
    21.     return res;
    22. }
    24. /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    25. bool remove(int val) { 
    26.     // for(auto c: recs){ 
    27.     // cout << c << " ";
    28.     // }
    30.     bool res = ump.find(val) != ump.end() && ump[val].size() > 0; // 存在 val 
    31.     if(!res) return res; // false
    33.     int lastindex = recs.size() - 1;
    34.     int lastVal = recs.back();
    36.     // 从 val 对应的 index 集合总删除 首个元素
    37.     int deleteIndex = *ump[val].begin();
    38.     ump[val].erase(ump[val].begin() );
    39.     if(ump[val].size() == 0) ump.erase(val);
    41.     // 将vector最后一个元素 移动到 deleteIndex处(这里 应该多余一个元素)
    42.     if(deleteIndex != lastindex){ 
    43.         ump[lastVal].erase(lastindex);
    44.         ump[lastVal].insert(deleteIndex);
    45.         recs[deleteIndex] = lastVal;
    46.     }
    47.     recs.pop_back();
    49.     return res;        
    50. }
    52. /** Get a random element from the collection. */
    53. int getRandom() { 
    54.     if(recs.size() == 0) return -1;
    55.     int index = rand() % recs.size();
    56.     return recs[index];
    57. }

    };

    /* 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(); /

  2. 随机链表节点
    给定一个单链表，随机选择链表的一个节点，并返回相应的节点值。保证每个节点被选的概率一样。

蓄水池采样算法：访问第i个节点的概率为1/i，则可以保证总体概率相等。但是该方法不可以直接返回，必须要遍历全部节点（当且仅当后面的节点均不选中才为等概率）

  1. /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
  2. class Solution { 
  3. public:
  4.     /** @param head The linked list's head. Note that the head is guaranteed to be not null, so it contains at least one node. */
  5.     Solution(ListNode* head): head(head) { 
  7.     }
  9.     /** Returns a random node's value. */
  10.     int getRandom() { 
  11.         int i = 2;
  12.         ListNode* cur = head->next;
  13.         int val = head->val;
  14.         while(cur != nullptr) { 
  15.             if(rand() % i + 1 == 1) val = cur->val; //第 i 节点以 1/i 概率替换当前值
  16.             i++;
  17.             cur = cur->next;
  18.         }
  19.         return val;
  20.     }
  21. private:
  22.     ListNode* head;
  23. };
  25. /** * Your Solution object will be instantiated and called as such: * Solution* obj = new Solution(head); * int param_1 = obj->getRandom(); */
  1. 赎金信
    给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。

哈希表的简单应用

  1. class Solution { 
  2. public:
  3.     bool canConstruct(string ransomNote, string magazine) { 
  4.         unordered_map<char, int> map;
  5.         for (auto c : magazine)
  6.         { 
  7.             map[c]++;
  8.         }
  9.         for (auto c : ransomNote)
  10.         { 
  11.             if (map[c] > 0) 
  12.                 map[c]--;
  13.             else return false;
  14.         }
  15.         return true;
  16.     }
  17. };
  1. 打乱数组
    打乱一个没有重复元素的数组。

额外生成一个拷贝即可

  1. class Solution { 
  2.     vector<int> m_nums;
  3.     vector<int> copy;
  4. public:
  5.     Solution(vector<int>& nums) { 
  6.         m_nums = nums;
  7.         copy = nums;
  8.     }
  10.     /** Resets the array to its original configuration and return it. */
  11.     vector<int> reset()
  12.     { 
  13.         return copy;
  14.     }
  16.     /** Returns a random shuffling of the array. */
  17.     vector<int> shuffle() 
  18.     { 
  19.         for(int i = m_nums.size() - 1; i >= 0; i--) 
  20.         { 
  21.             int rd = rand() % (i + 1);          
  22.             swap(m_nums[rd], m_nums[i]);            
  23.         }
  24.         return m_nums;
  25.     }
  26. };
  28. /** * Your Solution object will be instantiated and called as such: * Solution* obj = new Solution(nums); * vector<int> param_1 = obj->reset(); * vector<int> param_2 = obj->shuffle(); */
  1. 迷你语法分析器
    给定一个用字符串表示的整数的嵌套列表，实现一个解析它的语法分析器。

栈的简单使用

  1. /** * // This is the interface that allows for creating nested lists. * // You should not implement it, or speculate about its implementation * class NestedInteger { * public: * // Constructor initializes an empty nested list. * NestedInteger(); * * // Constructor initializes a single integer. * NestedInteger(int value); * * // Return true if this NestedInteger holds a single integer, rather than a nested list. * bool isInteger() const; * * // Return the single integer that this NestedInteger holds, if it holds a single integer * // The result is undefined if this NestedInteger holds a nested list * int getInteger() const; * * // Set this NestedInteger to hold a single integer. * void setInteger(int value); * * // Set this NestedInteger to hold a nested list and adds a nested integer to it. * void add(const NestedInteger &ni); * * // Return the nested list that this NestedInteger holds, if it holds a nested list * // The result is undefined if this NestedInteger holds a single integer * const vector<NestedInteger> &getList() const; * }; */
  2. class Solution { 
  3. public:
  4.     NestedInteger deserialize(string s) { 
  5.         stack<NestedInteger*> stk;
  6.         string numStr;
  7.         for (char &c : s) { 
  8.             if (c == '[') { 
  9.                 NestedInteger *res = new NestedInteger();
  10.                 stk.push(res);
  11.             } else if (c == '-' || isdigit(c)) { 
  12.                 if (stk.empty()) return NestedInteger(stoi(s));
  13.                 else numStr.push_back(c);
  14.             } else if (c == ',') { 
  15.                 if (!numStr.empty()) { 
  16.                     stk.top()->add(NestedInteger(stoi(numStr)));
  17.                     numStr = "";
  18.                 }
  19.             } else { 
  20.                 if (!numStr.empty()) { 
  21.                     stk.top()->add(NestedInteger(stoi(numStr)));
  22.                     numStr = "";
  23.                 }
  24.                 NestedInteger *res = stk.top();
  25.                 stk.pop();
  26.                 if (stk.empty()) { 
  27.                     return *res;
  28.                 } else { 
  29.                     stk.top()->add(*res);
  30.                 }
  31.             }
  32.         }
  33.         return NestedInteger();
  34.     }
  35. };
  1. 字典序排数
    给定一个整数 n, 返回从 1 到 n 的字典顺序。

DFS常规运用

  1. class Solution 
  2. { 
  3.     vector<int> ans;
  4. public:
  5.     void dfs(int num, int& n) 
  6.     { 
  7.         if (num > n) return;
  8.         ans.push_back(num);
  9.         for (int i = 0; i <= 9; ++i) 
  10.             dfs(num * 10 + i, n);
  11.     }
  13.     vector<int> lexicalOrder(int n) 
  14.     { 
  15.         for (int i = 1; i <= 9; ++i) 
  16.             dfs(i, n);
  17.         return ans;
  18.     }
  19. };
  1. 字符串中的第一个唯一字符
    给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

哈希表遍历解决

  1. class Solution { 
  2. public:
  3.     int firstUniqChar(string s) { 
  4.         unordered_map<char, int> m_map;
  5.         for (auto c : s)
  6.         { 
  7.             m_map[c]++;
  8.         }
  9.         for (int i = 0; i < s.size(); i++)
  10.         { 
  11.             if (m_map[s[i]] == 1) return i;
  12.         }
  13.         return -1;
  14.     }
  15. };

发表评论

表情：
评论列表 （有 0 条评论，288人围观）

还没有评论，来说两句吧...

相关阅读