LeetCode高级算法之设计问题

我不是女神ヾ 2022-12-28 07:29 94阅读 0赞

[146. LRU Cache][]

设计一个LRU机制的缓存， 要求获取key 和 设置key的时间复杂度为常数级别， 并且要将最近使用过的key的权重调整，

首先想到要在常数时间内获取一个key那只能是用hash表，

但是每次要更新当前的数据结构并且时间复杂度为常数， 顺序存储的结构如vector在这里就不能用了， 只能使用链表， 由于涉及头部删除，尾部添加， 随机删除，

在O（1）复杂度能完成的只有双向链表， C++里的deque底层是用数组实现的， 所以我们要自己写一个DoubleLinkedList; 并且为了删除和添加方便， 在头部尾部各加一个哨兵节点

代码如下：

struct myDeque{
            int key;    // unordered_map 根据key来获得索引
            int value;
            myDeque* pre;
            myDeque* next;
            myDeque():key(0), value(0), pre(nullptr), next(nullptr){}
            myDeque(int k, int v): key(k), value(v), pre(nullptr), next(nullptr) {}
        };

[208. Implement Trie (Prefix Tree)][208. Implement Trie _Prefix Tree]

实现前缀树， 在不了解这个之前觉得很高大上的数据结构， 学习了之后发现不过如此， 核心在于将一个个字母转换成vector数组的下标， 如果字符数目过多， 可以改用成unordered\_map来维护

同时还有一个变量isend来表示当前单词是否是词典里的某一个单词的结尾，通过这个可以判断是否能找到词典里的单词，

起初以为还要有一个char类型的变量来维持当前字母， 后来发现不用，在一层层的迭代过程中它在vector的下标或者unordered\_map的key都已经预示了当前的字母是多少

代码如下：

class Trie {
    public:
        /** Initialize your data structure here. */
        bool isend;
        vector<Trie*> next;        // 这里有个小tip， 如果成员变量在这里初始化的话编译器可能无法判断这是个变量还是个成员函数， 因此还是建议在构造函数里对之进行赋值
        Trie() {
            isend = false;
            next.assign(26, nullptr);
        }
        
        /** Inserts a word into the trie. */
        void insert(string word) {
            Trie* temp = this;
            for(char c:word)
            {
                if(temp->next[c-'a']==nullptr)
                {
                    temp->next[c-'a'] = new Trie();
                    
                }
                temp = temp->next[c-'a'];
            }
            temp->isend = true;
    
        }
        
        /** Returns if the word is in the trie. */
        bool search(string word) {
            Trie* temp = this;
            for (char c:word)
            {
                if (temp->next[c-'a'] == nullptr) return false;
                temp = temp->next[c-'a'];
            }
            return temp->isend;
        }
        
        /** Returns if there is any word in the trie that starts with the given prefix. */
        bool startsWith(string prefix) {
            Trie* temp = this;
            for (char c:prefix)
            {
                if (temp->next[c-'a']==nullptr) return false;
                temp = temp->next[c-'a'];
            }
            return true;
    
        }
    };
    
    /**
     * Your Trie object will be instantiated and called as such:
     * Trie* obj = new Trie();
     * obj->insert(word);
     * bool param_2 = obj->search(word);
     * bool param_3 = obj->startsWith(prefix);
     */

[341. Flatten Nested List Iterator][]

这题一开始没看明白是怎么回事， 后来发现有可以用的API调， 那么实现的难度就降了一大截， 核心在于递归铺平，

还有一个进阶点， 如果一开始就把整个list铺平的话， 空间复杂度会比较高， 一次只铺平一个就会相对好一点，

但是给的参数是存放在一个vector里， 如果从头一个一个铺平的话就要涉及在头部增加数据，时间复杂度就爆了， 解决方法就是把原来的vector里的数据存到其他便于在头部或者尾部增删数据的数据结构里

这里可以用链表也可以用栈，代码放一个简单无脑的直接铺平

/**
     * // This is the interface that allows for creating nested lists.
     * // You should not implement it, or speculate about its implementation
     * class NestedInteger {
     *   public:
     *     // 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;
     *
     *     // 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 NestedIterator {
    public:
        int iter;
        int size;
        vector<int>ans;
        void flatten(const NestedInteger& ni)    // 之前手贱在后面加了一个const, debug半天，函数尾部加const 表示是常成员函数， 就不能更改成员变量了
        {
            if (ni.isInteger())
            {
                int x = ni.getInteger();
                ans.push_back(x);
            }
            else
            {
                auto next = ni.getList();
                for (int i=0; i<next.size(); ++i)
                {
                    flatten(next[i]);
                }
            }
        }
        NestedIterator(vector<NestedInteger> &nestedList) {
            for (int i=0; i<nestedList.size(); ++i) flatten(nestedList[i]);
            iter = 0;
            size = ans.size();
        }
        
        int next() {
            return ans[iter++];
        }
        
        bool hasNext() {
            return iter < size;
        }
    };
    
    /**
     * Your NestedIterator object will be instantiated and called as such:
     * NestedIterator i(nestedList);
     * while (i.hasNext()) cout << i.next();
     */

[295. Find Median from Data Stream][]

找数据流中的中位数， 翻译一下就是找第k大元素， 一般涉及到第K大元素的优先会想到用堆来实现，

一开始用一个堆发现只能处理固定个数的元素的K大元素， 对于持续不断添加元素的数据流就得用两个堆来实现，

两个堆一个大顶堆一个小顶堆， 维护大顶堆的最大元素小于小顶堆的最小元素，并且要求小顶堆的size - 大顶堆的size小于2；最后要求的中位数就是大顶堆的堆顶元素或者两个堆堆顶元素的平均值

class MedianFinder {
    public:
        /** initialize your data structure here. */
        priority_queue<int, vector<int>, less<int>>pque1;
        priority_queue<int, vector<int>, greater<int>>pque2;
        MedianFinder() {
            
        }
        
        void addNum(int num) {
            pque1.push(num);
            if(pque1.size()-pque2.size()>=2) 
            {
                pque2.push(pque1.top()); pque1.pop();
            }
            while (!pque2.empty() && pque1.top() > pque2.top())
            {
                int num1 = pque1.top(); pque1.pop();
                int num2 = pque2.top(); pque2.pop();
                pque2.push(num1);
                pque1.push(num2);
            }
            return;
        }
        
        double findMedian() {
            if (pque1.size() == pque2.size()) return (pque1.top() + pque2.top())/2.0;
            else return pque1.top();
        }
    };
    
    /**
     * Your MedianFinder object will be instantiated and called as such:
     * MedianFinder* obj = new MedianFinder();
     * obj->addNum(num);
     * double param_2 = obj->findMedian();
     */

[146. LRU Cache]: https://leetcode-cn.com/problems/lru-cache/
[208. Implement Trie _Prefix Tree]: https://leetcode-cn.com/problems/implement-trie-prefix-tree/
[341. Flatten Nested List Iterator]: https://leetcode-cn.com/problems/flatten-nested-list-iterator/
[295. Find Median from Data Stream]: https://leetcode-cn.com/problems/find-median-from-data-stream/