当前位置：首页 > article >正文

每日计划-1122

article 2024/11/24 8:31:51

1. 完成 146. LRU缓存机制

struct DLinkedNode {
    int key, value;
    DLinkedNode* prev;
    DLinkedNode* next;
    DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr) {}
    DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {}
};

class LRUCache {
private:
    unordered_map<int, DLinkedNode*> cache;
    DLinkedNode* head;
    DLinkedNode* tail;
    int size;
    int capacity;

public:
    LRUCache(int _capacity): capacity(_capacity), size(0) {
        // 使用伪头部和伪尾部节点
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head->next = tail;
        tail->prev = head;
    }
    
    int get(int key) {
        if (!cache.count(key)) {
            return -1;
        }
        // 如果 key 存在，先通过哈希表定位，再移到头部
        DLinkedNode* node = cache[key];
        moveToHead(node);
        return node->value;
    }
    
    void put(int key, int value) {
        if (!cache.count(key)) {
            // 如果 key 不存在，创建一个新的节点
            DLinkedNode* node = new DLinkedNode(key, value);
            // 添加进哈希表
            cache[key] = node;
            // 添加至双向链表的头部
            addToHead(node);
            ++size;
            if (size > capacity) {
                // 如果超出容量，删除双向链表的尾部节点
                DLinkedNode* removed = removeTail();
                // 删除哈希表中对应的项
                cache.erase(removed->key);
                // 防止内存泄漏
                delete removed;
                --size;
            }
        }
        else {
            // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
            DLinkedNode* node = cache[key];
            node->value = value;
            moveToHead(node);
        }
    }

    void addToHead(DLinkedNode* node) {
        node->prev = head;
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
    }
    
    void removeNode(DLinkedNode* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    void moveToHead(DLinkedNode* node) {
        removeNode(node);
        addToHead(node);
    }

    DLinkedNode* removeTail() {
        DLinkedNode* node = tail->prev;
        removeNode(node);
        return node;
    }
};

2. 八股部分

1) 移动语义和拷贝语义有什么区别？

拷贝语义（Copy Semantics）
- 定义：
  - 拷贝语义是指在对象赋值或传递给函数等操作时，会创建一个新的对象，这个新对象是源对象的一个副本。它通过拷贝构造函数和拷贝赋值运算符来实现。例如，当有class A，并且A a1; A a2 = a1;这种情况时，会调用拷贝构造函数来创建a2，使得a2和a1是两个独立的对象，它们在内存中有各自独立的存储区域，并且内容相同。
- 行为示例：
  - 假设我们有一个简单的Point类来表示二维空间中的点：

class Point {
public:
    int x;
    int y;
    Point(int _x = 0, int _y = 0) : x(_x), y(_y) {}
    // 拷贝构造函数
    Point(const Point& other) : x(other.x), y(other.y) {
        std::cout << "Copy constructor called." << std::endl;
    }
};
int main() {
    Point p1(1, 2);
    Point p2 = p1;
    return 0;
}

在这个例子中，当Point p2 = p1;执行时，拷贝构造函数被调用，p2会得到一个和p1完全相同的副本，包括x和y的值。p1和p2是两个独立的对象，它们在内存中的位置不同。
资源处理方式：
- 在拷贝语义下，对于包含资源（如动态分配的内存、文件句柄等）的对象，资源会被复制。例如，如果Point类内部有一个动态分配的数组来存储一些额外的数据，那么在拷贝构造函数中，需要为新对象也分配一块相同大小的内存，并将源对象内存中的数据复制到新对象的内存中。这可能会导致性能问题，特别是当对象包含大量资源时。

移动语义（Move Semantics）
- 定义：
  - 移动语义允许将一个对象的资源（如堆内存、文件句柄等）转移到另一个对象，而不是进行复制。它主要通过移动构造函数和移动赋值运算符来实现，这两个函数的参数是右值引用。当对象是一个右值（如临时对象、即将销毁的对象等）时，编译器可以选择调用移动构造函数或移动赋值运算符来高效地转移资源。
- 行为示例：
  - 考虑一个String类，它内部有一个字符指针来存储字符串：

class String {
public:
    char* data;
    String() : data(nullptr) {}
    String(const char* str) {
        if (str) {
            data = new char[strlen(str) + 1];
            strcpy(data, str);
        } else {
            data = nullptr;
        }
    }
    // 移动构造函数
    String(String&& other) : data(other.data) {
        other.data = nullptr;
        std::cout << "Move constructor called." << std::endl;
    }
};
int main() {
    String s1("Hello");
    String s2 = std::move(s1);
    return 0;
}

在这个例子中，当String s2 = std::move(s1);执行时，移动构造函数被调用。s1的data指针（指向存储 “Hello” 的内存）被转移到s2，然后s1的data指针被设置为nullptr。这里不是复制字符串内容，而是直接转移了资源的所有权。
资源处理方式：
- 对于包含资源的对象，移动语义可以避免资源的复制。以刚才的String类为例，如果是拷贝语义，当创建一个新的String对象时，需要为新对象重新分配内存并复制源对象中的字符串内容。而在移动语义下，只是简单地转移了指针，大大提高了效率，特别是对于资源占用较多的对象。