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

常数时间插入、删除和获取随机元素 设计一个支持在平均 时间复杂度 O(1) 下，执行以下操作的数据结构。 insert(val)：当元素 val 不存在时，向集合中插入该项。 remove(val)：元素 val 存在时，从集合中移除该项。 getRandom：随机返回现有集合中的一项。每个元素应该有相同的概率被返回。 class RandomizedSet { public: RandomizedSet() {} bool insert(int val) { if (m.count(val)) return false; nums.push_back(val); m[val] = nums.size() - 1; return true; } bool remove(int val) { if (!m.count(val)) return false; int last = nums.back(); m[last] = m[val]; nums[m[val]] = last; nums.pop_back(); m.erase(val); return true; } int getRandom() { return nums[rand() % nums.size()]; } private: vector<int> nums; unordered_map<int, int> m; }; /** * 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(); */ O(1) 时间插入、删除和获取随机元素 - 允许重复 设计一个支持在平均 时间复杂度 O(1) 下， 执行以下操作的数据结构。注意: 允许出现重复元素。 insert(val)：向集合中插入元素 val。 remove(val)：当 val 存在时，从集合中移除一个 val。 getRandom：从现有集合中随机获取一个元素。每个元素被返回的概率应该与其在集合中的数量呈线性相关 class RandomizedCollection { public: /** Initialize your data structure here. */ // 删除功能则相对复杂一点，首先通过hash表O(1)地找到删除目标在vector中的位置，然后为了避免vector删除中间元素时平移后面元素所需的线性耗时，我们在删除操作前将需要删除的元素与vector最后一个元素进行位置交换，此时需要删除的元素处在vector的尾部，删除之即可 // 这里保存某个值 和 储存这个值的 vector indices unordered_map<int, unordered_set<int> > ump; vector<int> recs; RandomizedCollection() { } /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */ bool insert(int val) { recs.push_back(val); bool res = ump.find(val) == ump.end(); int index = recs.size() - 1; ump[val].insert(index); return res; } /** Removes a value from the collection. Returns true if the collection contained the specified element. */ bool remove(int val) { // for(auto c: recs){ // cout << c << " "; // } bool res = ump.find(val) != ump.end() && ump[val].size() > 0; // 存在 val if(!res) return res; // false int lastindex = recs.size() - 1; int lastVal = recs.back(); // 从 val 对应的 index 集合总删除 首个元素 int deleteIndex = *ump[val].begin(); ump[val].erase(ump[val].begin() ); if(ump[val].size() == 0) ump.erase(val); // 将vector最后一个元素 移动到 deleteIndex处(这里 应该多余一个元素) if(deleteIndex != lastindex){ ump[lastVal].erase(lastindex); ump[lastVal].insert(deleteIndex); recs[deleteIndex] = lastVal; } recs.pop_back(); return res; } /** Get a random element from the collection. */ int getRandom() { if(recs.size() == 0) return -1; int index = rand() % recs.size(); return recs[index]; } }; /** * 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(); */ 随机链表节点 给定一个单链表，随机选择链表的一个节点，并返回相应的节点值。保证每个节点被选的概率一样。

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

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

哈希表的简单应用

class Solution { public: bool canConstruct(string ransomNote, string magazine) { unordered_map<char, int> map; for (auto c : magazine) { map[c]++; } for (auto c : ransomNote) { if (map[c] > 0) map[c]--; else return false; } return true; } }; 打乱数组 打乱一个没有重复元素的数组。

额外生成一个拷贝即可

class Solution { vector<int> m_nums; vector<int> copy; public: Solution(vector<int>& nums) { m_nums = nums; copy = nums; } /** Resets the array to its original configuration and return it. */ vector<int> reset() { return copy; } /** Returns a random shuffling of the array. */ vector<int> shuffle() { for(int i = m_nums.size() - 1; i >= 0; i--) { int rd = rand() % (i + 1); swap(m_nums[rd], m_nums[i]); } return m_nums; } }; /** * 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(); */ 迷你语法分析器 给定一个用字符串表示的整数的嵌套列表，实现一个解析它的语法分析器。

栈的简单使用

/** * // 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; * }; */ class Solution { public: NestedInteger deserialize(string s) { stack<NestedInteger*> stk; string numStr; for (char &c : s) { if (c == '[') { NestedInteger *res = new NestedInteger(); stk.push(res); } else if (c == '-' || isdigit(c)) { if (stk.empty()) return NestedInteger(stoi(s)); else numStr.push_back(c); } else if (c == ',') { if (!numStr.empty()) { stk.top()->add(NestedInteger(stoi(numStr))); numStr = ""; } } else { if (!numStr.empty()) { stk.top()->add(NestedInteger(stoi(numStr))); numStr = ""; } NestedInteger *res = stk.top(); stk.pop(); if (stk.empty()) { return *res; } else { stk.top()->add(*res); } } } return NestedInteger(); } }; 字典序排数 给定一个整数 n, 返回从 1 到 n 的字典顺序。

DFS常规运用

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

哈希表遍历解决

class Solution { public: int firstUniqChar(string s) { unordered_map<char, int> m_map; for (auto c : s) { m_map[c]++; } for (int i = 0; i < s.size(); i++) { if (m_map[s[i]] == 1) return i; } return -1; } };