数据结构-经典算法设计（期中备考用）

每个算法都有简单的思路，但并非算法思想，只是记录一些经典的算法设计。

1. 合并两个有序链表

题目描述

写一个函数，将两个升序链表合并成一个新的升序链表，返回新链表的头指针。

算法步骤

1. 创建一个结点 dummy（头指针占位）。
2. 使用一个指针 tail 指向合并链表的末尾。
3. 每次比较两个链表当前节点的值，将较小的一个链接到 tail。
4. 将 tail 向后移动，源链表指针也前进。
5. 当一个链表走完后，将另一个链表剩余部分直接接到 tail 后面。

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};
//结构体构建，可写可不写，最重要的是下面的这个算法函数。


ListNode* merge(ListNode* l1, ListNode* l2) {
    ListNode dummy(0), *tail = &dummy;
    while (l1 && l2) {
        if (l1->val < l2->val) tail->next = l1, l1 = l1->next;
        else tail->next = l2, l2 = l2->next;
        tail = tail->next;
    }
    tail->next = l1 ? l1 : l2;
    return dummy.next;
}

时间复杂度：O(m + n)，m 和 n 是两个链表的长度 空间复杂度：O(1)（原地合并，不开额外数组）

2. 用栈实现队列

题目描述

使用两个栈实现一个队列的入队和出队操作。

算法步骤

用两个栈 in 和 out：

• 入队时直接压入 in
• 出队时：
  • 若 out 非空，直接弹出
  • 若 out 为空，将 in 所有元素倒入 out，再弹出

class MyQueue {
private:
    stack<int> inStack, outStack;

    void transfer() {
        while (!inStack.empty()) {
            outStack.push(inStack.top()); //把入栈倒入出栈
            inStack.pop();
        }
    }

public:
//这里其实也只要写push和pop函数，记得把transfer函数套到pop里即可。
    void push(int x) {
        inStack.push(x);
    }//压入队列

    void pop() {
        if (outStack.empty()) transfer();
        if (!outStack.empty()) outStack.pop();
    }//弹出队列

    int front() {
        if (outStack.empty()) transfer();
        return outStack.top();
    }

    bool empty() {
        return inStack.empty() && outStack.empty();
    }
};

时间复杂度：O(1) 每个元素最多被移动两次。 空间复杂度： O(n) 两个栈，最多 n 个元素在栈中。

3. 队列模拟任务调度

题目描述

队列中每个任务有一个编号，顺序入队，按顺序处理。可能会出现“插队”（比如优先任务）。模拟这个过程。

一些常见题目变形

• 循环队列实现多进程
• 某任务执行完后重新入队（多轮轮转）
• 实现带优先级的调度（双端队列 / 优先队列）

基本思路

• 普通调度：使用普通队列 queue<T>
• 插队：用 deque<T>，高优先级任务从队首插入
• 模拟时间片轮转：每次处理一个任务，将其放回队尾

//这个是没有插队的普通版本
void simulateQueue(vector<int>& tasks) {
    queue<int> q;

    for (int t : tasks) {
        q.push(t);  // 初始入队
    }

    while (!q.empty()) {
        int current = q.front(); q.pop();
        // 假设部分任务重新排入队尾
        if (current % 2 == 0) {
            q.push(current);  // 模拟需要再次处理
        }
    }
} 

//这个使用插队，需要使用双端队列，让任务可以push的时候直接到push_front()
void simulateTaskQueue(const vector<Task>& tasks) {
    deque<int> q;

    for (const Task& task : tasks) {
        if (task.urgent) { 
        //如果任务优先为true
            q.push_front(task.id);  // 插队
        } else {
            q.push_back(task.id);   // 正常排队
        }
    }
	//当然也可以在出队上用做文章，不过这里不多写了，怕有bug
    while (!q.empty()) {
        int current = q.front(); q.pop_front();
        
         if (current % 2 == 0) {
            q.push(current);  // 模拟需要再次处理
        }
    }
}

使用STL的话，时间复杂度只是O(1) 而已。

当然，如果题目涉及任务有权重什么的，一般我们实现是直接用 STL 的 priority_queue…不过这里也提供 heap 的算法模拟，最大堆。这种涉及数学方法分割的我一般都不怎么会…

void down(int i) { // 下滤
    int t = i;
    if (2 * i <= heapSize && heap[2 * i] > heap[t]) t = 2 * i;
    if (2 * i + 1 <= heapSize && heap[2 * i + 1] > heap[t]) t = 2 * i + 1;
    if (t != i) {
        swap(heap[i], heap[t]);
        down(t);
    }
}

void up(int i) { // 上滤
    while (i > 1 && heap[i] > heap[i / 2]) {
        swap(heap[i], heap[i / 2]);
        i /= 2;
    }
}

void insert(int x) {
    heap[++heapSize] = x;
    up(heapSize);
}

void pop() {
    heap[1] = heap[heapSize--];
    down(1);
}

4. 中序 + 后序构造二叉树，输出层序遍历

这道题其实还可以类比那些知道中序+前序遍历求后序遍历的题目，可以见经典的 洛谷 P1827这类题型。

基本思路

• 后序的最后一个元素是当前根节点
• 在中序中找到这个根节点的位置，这个根节点左侧是左子树所有节点，右侧是右子树所有节点
• 使用递归构建左右子树
• 构建完毕后使用 queue进行简单的入队push出队pop来递归层序遍历。

//还原树
TreeNode* buildTreeHelper(vector<int>& in, vector<int>& post, int inL, int inR, int postL, int postR) {
    if (inL > inR) return nullptr;

    int rootVal = post[postR];
    TreeNode* root = new TreeNode(rootVal);

    int k = inL;
    //如果是string的话，我们直接可以str.find(rootVal)找到中序遍历中根节点的位置。
    //这和那道 p1827 思路其实是一致的。
    while (in[k] != rootVal) ++k;
    int leftSize = k - inL;

    root->left = buildTreeHelper(in, post, inL, k - 1, postL, postL + leftSize - 1);
    root->right = buildTreeHelper(in, post, k + 1, inR, postL + leftSize, postR - 1);

    return root;
}

//层序遍历
void levelOrder(TreeNode* root) {
    if (!root) return;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* cur = q.front(); q.pop();
        cout << cur->val << " ";
        if (cur->left) q.push(cur->left);
        if (cur->right) q.push(cur->right);
    }
    cout << endl;
}

时间复杂度： O(n) 构建二叉树和层序遍历都是访问树所有节点，因此时间复杂度一致。 空间复杂度： O(n)

更新施工中…