阅读 23

秋招复习(1) - 重要数据结构和算法的代码实现

1.堆排序

基本思路

父节点在数组里的序号为i,则两个子节点分别为2 i + 1 和 2 i + 1,利用这种方式将整个数组模拟成了一个二叉树。先对整个数组建堆,完成之后数组第一个元素nums[0]就是最大/最小,然后将其交换到数组nums[size-1],在对前size-1的数组元素建堆,再把nums[0]交换到nums[size-2]。重复这个过程,即可完成对整个数组的排序。时间复杂度O(nlogn).

代码实现:

//用户交换堆顶元素到数组末尾
void Swap(int& a, int& b) {
    int tmp = a;
    a = b;
    b = tmp;
}

// curLen表示当前用于构造大根堆的数组长度
void SortCore(vector<int>& nums, int curLen,int curPos) {
    if (curLen <= 1) return;
    bool isLeftExist = 2 * curPos + 1 < curLen;
    bool isRightExist = 2 * curPos + 2 < curLen;
    if (!isLeftExist && !isRightExist) return;
    // 存在左节点,则先调整左节点
    if(isLeftExist)
        SortCore(nums, curLen, 2 * curPos + 1);
    // 存在右节点,则先调整右节点
    if(isRightExist)
        SortCore(nums, curLen, 2 * curPos + 2);
    // 找到左右节点里最大的
    int changePos = 0;
    if (isLeftExist) {
        changePos = 2 * curPos + 1;
        if (isRightExist && nums[2 * curPos + 2] > nums[2 * curPos + 1]) {
            changePos = 2 * curPos + 2;
        }
    }
    else {
        changePos = 2 * curPos + 1;
    }
    
    // 如果最大的字节点大于父节点,则交换
    if (nums[changePos] > nums[curPos]) {
        Swap(nums[changePos], nums[curPos]);
    }
}
// 堆排序入口
void Sort(vector<int>& nums) {
    int size = nums.size();
    //每次调整堆都确定一个最大的元素
    for (int i = size; i > 1; --i) {
        Sort(nums,i,0); // 对数组0-i范围内的建堆
        Swap(nums[0], nums[i - 1]); // 完成之后将最大的nuns[0]交换到末尾
    }
}
复制代码

2.字典树(前缀树)

基本思路

实际就是保存当前节点的下一个所有可能的节点在一个数组中,为一颗26叉树(我这里只模拟了小写字符的前缀树,要模拟所有字符的话把数组增大到256就行了)。

代码实现

class TreeNode {
public:
    bool _isEnd; // 表示当前字母是不是字符串的最后一个
    TreeNode* _node[26]; // 保存当前字母的所有下一个字母节点
    static int newTimes; // 统计申请内存次数

public:
    TreeNode() {
        _isEnd = false;
        memset(_node, 0, sizeof(TreeNode*) * 26);
    }

    // 插入指定字符串
    void insert(string& s) {
        int size = s.size();
        TreeNode*  p = this;
        for (int i = 0; i < size; ++i) {
            if (p->_node[s[i] - 'a'] == NULL) {
                p->_node[s[i] - 'a'] = new TreeNode();
                ++newTimes;
                p = p->_node[s[i] - 'a'];
            }
            else {
                p = p->_node[s[i] - 'a'];
            }
        }
        p->_isEnd = true;
    }

    // 搜索指定字符串是否存在
    bool search(string& s) {
        int size = s.size();
        TreeNode* p = this;
        for (int i = 0; i < size; ++i) {
            if (p->_node[s[i] - 'a'] == nullptr) return false;
            p = p->_node[s[i] - 'a'];
        }
        return p->_isEnd == true;
    }

    // 判断指定字符串为前缀的字母是否存在
    bool isPrefix(string& s){
        int size = s.size();
        TreeNode* p = this;
        for (int i = 0; i < size; ++i) {
            if (p->_node[s[i] - 'a'] == nullptr) return false;
            p = p->_node[s[i] - 'a'];
        }
        return true;
    }

    // 清理内存
    bool clear() {
        for (int i = 0; i < 26; ++i) {
            if (_node[i]) {
                _node[i]->clear();
                delete _node[i];
                --newTimes;
            }
        }
        return TreeNode::newTimes == 0;
    }
};
int TreeNode::newTimes = 0;
复制代码

观察者模式

#include <iostream>
#include <list>
using namespace std;
 
class Observer
{
public:
    virtual void Update(int) = 0;
};
 
class Subject
{
public:
    virtual void Attach(Observer *) = 0;
    virtual void Detach(Observer *) = 0;
    virtual void Notify() = 0;
};
 
class ConcreteObserver : public Observer
{
public:
    ConcreteObserver(Subject *pSubject) : m_pSubject(pSubject){}
 
    void Update(int value)
    {
        cout << "ConcreteObserver get the update. New State:" << value << endl;
    }
 
private:
    Subject *m_pSubject;
};
 
class ConcreteObserver2 : public Observer
{
public:
    ConcreteObserver2(Subject *pSubject) : m_pSubject(pSubject){}
 
    void Update(int value)
    {
        cout << "ConcreteObserver2 get the update. New State:" << value << endl;
    }
 
private:
    Subject *m_pSubject;
};
 
class ConcreteSubject : public Subject
{
public:
// 目标用于和观察者之间建立联系和通知的三个函数
    void Attach(Observer *pObserver);
    void Detach(Observer *pObserver);
    void Notify();
 
    void SetState(int state)
    {
        m_iState = state;
    }
 
private:
    std::list<Observer *> m_ObserverList;
    int m_iState;
};
 
void ConcreteSubject::Attach(Observer *pObserver)
{
    m_ObserverList.push_back(pObserver);
}
 
void ConcreteSubject::Detach(Observer *pObserver)
{
    m_ObserverList.remove(pObserver);
}
 
void ConcreteSubject::Notify()
{
    std::list<Observer *>::iterator it = m_ObserverList.begin();
    while (it != m_ObserverList.end())
    {
        (*it)->Update(m_iState);
        ++it;
    }
}
 
int main()
{
    // Create Subject
    ConcreteSubject *pSubject = new ConcreteSubject();
 
    // Create Observer
    Observer *pObserver = new ConcreteObserver(pSubject);
    Observer *pObserver2 = new ConcreteObserver2(pSubject);
 
    // Change the state
    pSubject->SetState(2);
 
    // Register the observer
    pSubject->Attach(pObserver);
    pSubject->Attach(pObserver2);
 
    pSubject->Notify();
 
    // Unregister the observer
    pSubject->Detach(pObserver);
 
    pSubject->SetState(3);
    pSubject->Notify();
 
    delete pObserver;
    delete pObserver2;
    delete pSubject;
}
复制代码

LRU实现

#include <iostream>
#include <vector>
#include <map>
using namespace std;

struct Node {
    int key;
    int value;
    Node* pre, *next;
    Node(int k, int v) {
        key = k;
        value = v;
        pre = next = nullptr;
    }
};

class LRUCache {
    int _capacity;
    Node* _head;
    Node* _tail;
    map<int, Node*> mp;

public:

    LRUCache(int size) {
        _capacity = size;
        _head = _tail = nullptr;
    }

    //插入已有结点到头部
    void setHead(Node *node)
    {
        node->next = _head;
        node->pre = NULL;

        if (_head != NULL)
        {
            _head->pre = node;
        }
        _head = node;
        if (_tail == NULL)
        {
            _tail = _head;
        }
    }

    void remove(int k) {
        map<int, Node*>::iterator it = mp.find(k);
        if (it != mp.end()) {
            remove(it->second);
        }
    }

    //移除结点
    void remove(Node *node)
    {
        if (node->pre != NULL){
            node->pre->next = node->next;
        } else{
            _head = node->next;
        }

        if (node->next != NULL) {
            node->next->pre = node->pre;
        }
        else {
            _tail = node->pre;
        }
    }

    // 获取k对应的值并更新链表
    int get(int key)
    {
        map<int, Node*>::iterator it = mp.find(key);
        if (it != mp.end()) {
            Node* node = it->second;
            remove(node);
            setHead(node);
            return node->value;
        } else {
            return -1;
        }
    }

    // 插入元素
    void set(int key, int value)
    {
        map<int, Node *>::iterator it = mp.find(key);
        if (it != mp.end())
        {
            Node* node = it->second;
            node->value = value;
            remove(node);
            setHead(node);
        } else {
            Node* newNode = new Node(key, value);
            if (mp.size() >= _capacity)
            {
                map<int, Node*>::iterator iter = mp.find(_tail->key);
                remove(_tail);
                mp.erase(iter);
            }
            setHead(newNode);
            mp[key] = newNode;
        }
    }

    // 获取当前元素个数
    int getCurSizeAndShow() {
        Node* p = _head;
        int nums = 0;
        while (p) {
            ++nums;
            cout << p->value << " ";
            p = p->next;
        }
        cout << endl;
        return nums;
    }
};


int main() {
    LRUCache lru(5);
    lru.set(1, 11);
    lru.set(2, 22);
    lru.set(3, 33);
    lru.set(4, 44);
    lru.set(5, 55);

    cout << "原始链表为:" ;
    lru.getCurSizeAndShow();
    lru.get(4);
    cout << "获取key为4的元素之后的链表:";
    lru.getCurSizeAndShow();  

    lru.set(6, 66);
    cout << "新添加一个key为6之后的链表:";
    lru.getCurSizeAndShow();

    lru.remove(3);
    cout << "移除key=3的之后的链表";
    lru.getCurSizeAndShow();

    return 0;
}
复制代码