番茄小说客户端模拟面试报告

#include <bits/stdc++.h>
using namespace std;

class LRUCache {
    struct DLinkedNode {
        int key;
        int value;
        DLinkedNode* prev;
        DLinkedNode* next;

        DLinkedNode() : key(0), value(0), prev(nullptr), next(nullptr) {}
        DLinkedNode(int k, int v)
            : key(k), value(v), prev(nullptr), next(nullptr) {}
    };

    int capacity;
    int currentSize;
    unordered_map<int, DLinkedNode*> cache;
    DLinkedNode* head; // 虚拟头节点：head->next 是最新节点
    DLinkedNode* tail; // 虚拟尾节点：tail->prev 是最旧节点

    // 把 node 插入虚拟头节点后面
    void addToHead(DLinkedNode* node) {
        node->prev = head;
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
    }

    // 把 node 从当前链表位置摘除，但暂时不 delete
    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* oldest = tail->prev;
        removeNode(oldest);
        return oldest;
    }

public:
    explicit LRUCache(int cap) : capacity(cap), currentSize(0) {
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head->next = tail;
        tail->prev = head;
    }

    // 释放虚拟节点和缓存中剩余的全部真实节点，避免内存泄漏
    ~LRUCache() {
        DLinkedNode* node = head;
        while (node != nullptr) {
            DLinkedNode* next = node->next;
            delete node;
            node = next;
        }
    }

    LRUCache(const LRUCache&) = delete;
    LRUCache& operator=(const LRUCache&) = delete;

    int get(int key) {
        auto it = cache.find(key); // 只进行一次哈希查找
        if (it == cache.end()) return -1;

        DLinkedNode* node = it->second;
        moveToHead(node);           // 被访问过，更新为最近使用
        return node->value;
    }

    void put(int key, int value) {
        auto it = cache.find(key);

        if (it != cache.end()) {
            // key 已存在：更新值并移动到链表头
            DLinkedNode* node = it->second;
            node->value = value;
            moveToHead(node);
            return;
        }

        // key 不存在：创建新节点并插入链表头
        DLinkedNode* node = new DLinkedNode(key, value);
        cache[key] = node;
        addToHead(node);
        ++currentSize;

        if (currentSize > capacity) {
            DLinkedNode* oldest = removeTail();
            cache.erase(oldest->key);
            delete oldest;
            --currentSize;
        }
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int capacity, q;
    cin >> capacity >> q;
    LRUCache cache(capacity);
    while (q--) {
        string op; int key, value;
        cin >> op >> key;
        if (op == "get") cout << cache.get(key) << '\n';
        else { cin >> value; cache.put(key, value); }
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s; cin >> s;
    vector<int> last(256, -1);
    int left = 0, ans = 0;
    for (int right = 0; right < (int)s.size(); ++right) {
        unsigned char c = s[right];
        left = max(left, last[c] + 1);
        last[c] = right;
        ans = max(ans, right - left + 1);
    }
    cout << ans << '\n';
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, target;
    cin >> n >> m >> target;
    vector<vector<int>> a(n, vector<int>(m));
    for (auto &row : a) for (int &x : row) cin >> x;
    int r = 0, c = m - 1;
    while (r < n && c >= 0) {
        if (a[r][c] == target) { cout << 1 << '\n'; return 0; }
        if (a[r][c] > target) --c;
        else ++r;
    }
    cout << 0 << '\n';
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

struct Node { long long val; int left, right; };
vector<Node> tree;
long long answer = LLONG_MIN;

long long dfs(int u) {
    if (u == -1) return 0;
    long long leftGain = max(0LL, dfs(tree[u].left));
    long long rightGain = max(0LL, dfs(tree[u].right));
    answer = max(answer, tree[u].val + leftGain + rightGain);
    return tree[u].val + max(leftGain, rightGain);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    tree.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> tree[i].val >> tree[i].left >> tree[i].right;
        if (tree[i].left != -1) --tree[i].left;
        if (tree[i].right != -1) --tree[i].right;
    }
    dfs(0);
    cout << answer << '\n';
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k; cin >> n >> k;
    unordered_map<int, int> freq;
    for (int i = 0, x; i < n; ++i) { cin >> x; ++freq[x]; }
    vector<pair<int,int>> items(freq.begin(), freq.end());
    sort(items.begin(), items.end(), [](auto &a, auto &b) {
        if (a.second != b.second) return a.second > b.second;
        return a.first < b.first;
    });
    k = min(k, (int)items.size());
    for (int i = 0; i < k; ++i)
        cout << items[i].first << (i + 1 == k ? '\n' : ' ');
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

struct Item {
    int value, arrayId, index;
    bool operator>(const Item &o) const { return value > o.value; }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int k; cin >> k;
    vector<vector<int>> a(k);
    priority_queue<Item, vector<Item>, greater<Item>> pq;
    for (int i = 0, len; i < k; ++i) {
        cin >> len; a[i].resize(len);
        for (int &x : a[i]) cin >> x;
        if (len) pq.push({a[i][0], i, 0});
    }
    bool first = true;
    while (!pq.empty()) {
        auto cur = pq.top(); pq.pop();
        if (!first) cout << ' ';
        first = false; cout << cur.value;
        int next = cur.index + 1;
        if (next < (int)a[cur.arrayId].size())
            pq.push({a[cur.arrayId][next], cur.arrayId, next});
    }
    cout << '\n';
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

class BlockingQueue {
    queue<long long> q;
    size_t cap;
    mutex m;
    condition_variable notFull, notEmpty;
public:
    explicit BlockingQueue(size_t capacity) : cap(capacity) {}
    void push(long long value) {
        unique_lock<mutex> lock(m);
        notFull.wait(lock, [&] { return q.size() < cap; });
        q.push(value);
        lock.unlock();
        notEmpty.notify_one();
    }
    long long pop() {
        unique_lock<mutex> lock(m);
        notEmpty.wait(lock, [&] { return !q.empty(); });
        long long value = q.front(); q.pop();
        lock.unlock();
        notFull.notify_one();
        return value;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int capacity, producers, consumers, each;
    cin >> capacity >> producers >> consumers >> each;
    BlockingQueue q(capacity);
    atomic<long long> count{0}, sum{0};
    vector<thread> cs, ps;
    for (int c = 0; c < consumers; ++c) cs.emplace_back([&] {
        while (true) {
            long long x = q.pop();
            if (x == -1) break;
            ++count; sum += x;
        }
    });
    for (int p = 0; p < producers; ++p) ps.emplace_back([&, p] {
        for (int i = 1; i <= each; ++i) q.push(1LL * p * each + i);
    });
    for (auto &t : ps) t.join();
    for (int i = 0; i < consumers; ++i) q.push(-1);
    for (auto &t : cs) t.join();
    cout << count.load() << ' ' << sum.load() << '\n';
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

class ThreadSafeLRU {
    struct Node {
        int key;
        shared_ptr<const string> value;
        Node* prev;
        Node* next;

        Node(int k = 0, shared_ptr<const string> v = {})
            : key(k), value(move(v)), prev(nullptr), next(nullptr) {}
    };

    size_t capacity;
    size_t currentSize = 0;
    unordered_map<int, Node*> cache;
    Node* head;
    Node* tail;
    mutex m; // 同时保护 cache、链表指针和 currentSize

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

    void removeNode(Node* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

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

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

public:
    explicit ThreadSafeLRU(size_t cap) : capacity(cap) {
        head = new Node();
        tail = new Node();
        head->next = tail;
        tail->prev = head;
    }

    ~ThreadSafeLRU() {
        // 析构时应由外部保证已经没有线程继续访问该缓存
        Node* node = head;
        while (node != nullptr) {
            Node* next = node->next;
            delete node;
            node = next;
        }
    }

    ThreadSafeLRU(const ThreadSafeLRU&) = delete;
    ThreadSafeLRU& operator=(const ThreadSafeLRU&) = delete;

    shared_ptr<const string> get(int key) {
        lock_guard<mutex> lock(m);
        auto it = cache.find(key);
        if (it == cache.end()) return {};

        Node* node = it->second;
        moveToHead(node);

        // 在锁内复制 shared_ptr。返回后即使节点被淘汰，value 仍然有效。
        return node->value;
    }

    void put(int key, string value) {
        // 构造大对象不需要占用缓存的全局锁
        auto object = make_shared<const string>(move(value));
        lock_guard<mutex> lock(m);

        auto it = cache.find(key);
        if (it != cache.end()) {
            Node* node = it->second;
            node->value = move(object);
            moveToHead(node);
            return;
        }

        Node* node = new Node(key, move(object));
        cache[key] = node;
        addToHead(node);
        ++currentSize;

        if (currentSize > capacity) {
            Node* oldest = removeTail();
            cache.erase(oldest->key);
            delete oldest; // 只删除节点；value 是否释放由 shared_ptr 决定
            --currentSize;
        }
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int capacity, qn; cin >> capacity >> qn;
    ThreadSafeLRU cache(capacity);
    while (qn--) {
        string op; int key; cin >> op >> key;
        if (op == "get") {
            auto value = cache.get(key);
            cout << (value ? *value : "NULL") << '\n';
        } else {
            string value; cin >> value;
            cache.put(key, move(value));
        }
    }
    return 0;
}