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

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

1.  常数时间插入、删除和获取随机元素  
    设计一个支持在平均 时间复杂度 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(); */

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

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

**蓄水池采样算法：访问第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(); */

1.  赎金信  
    给定一个赎金信 (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;
        }
    };

1.  打乱数组  
    打乱一个没有重复元素的数组。

**额外生成一个拷贝即可**

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

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

1.  字典序排数  
    给定一个整数 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.  字符串中的第一个唯一字符  
    给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -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;
        }
    };