力扣1116题：多线程打印零与奇偶数

一、题目解读

力扣1116题要求实现一个多线程程序，按照特定顺序打印零与奇偶数。给定整数n，程序需要交替打印零和数字，打印顺序应为：零、奇数、零、偶数、零、奇数...直到所有数字打印完毕。这道题考察多线程同步和条件变量的使用，是并发编程的经典练习。

二、解题思路

本解法采用互斥锁(mutex)和条件变量(condition_variable)实现线程同步。核心思路是：

1. 使用next_type变量标记当前应该打印的类型(0:零,1:奇数,2:偶数)

2. 每个线程在打印前检查next_type是否符合自己的打印职责

3. 打印完成后更新next_type并通知其他线程

4. 使用条件变量避免忙等待，提高效率

三、解题步骤

1. 初始化：设置初始状态为打印零(next_type=0)

2. zero线程：循环n次，每次等待next_type=0时打印0，然后根据计数决定下一步打印奇数还是偶数

3. odd线程：等待next_type=1时打印当前计数(奇数)，然后设置为打印零

4. even线程：等待next_type=2时打印当前计数(偶数)，然后设置为打印零

5. 终止条件：当计数超过n时，所有线程退出

四、完整代码实现

class ZeroEvenOdd {
private:
    int n;
    int count;
    bool zero_flag;
    int next_type; // 0: zero, 1: odd, 2: even
    std::mutex mtx;
    std::condition_variable cv;

public:
    ZeroEvenOdd(int n) {
        this->n = n;
        count = 1;
        zero_flag = true;
        next_type = 0;
    }

    void zero(function<void(int)> printNumber) {
        for (int i = 0; i < n; ++i) {
            unique_lock<mutex> lock(mtx);
            cv.wait(lock, [this]{ return next_type == 0; });
            printNumber(0);
            next_type = (count % 2 == 1) ? 1 : 2;
            cv.notify_all();
        }
    }

    void even(function<void(int)> printNumber) {
        while (true) {
            unique_lock<mutex> lock(mtx);
            cv.wait(lock, [this]{ 
                return next_type == 2 || count > n; 
            });
            if (count > n) break;
            printNumber(count++);
            next_type = 0;
            cv.notify_all();
        }
    }

    void odd(function<void(int)> printNumber) {
        while (true) {
            unique_lock<mutex> lock(mtx);
            cv.wait(lock, [this]{ 
                return next_type == 1 || count > n; 
            });
            if (count > n) break;
            printNumber(count++);
            next_type = 0;
            cv.notify_all();
        }
    }
};

五、总结

本解法优雅地解决了多线程同步问题，通过互斥锁和条件变量确保打印顺序正确。代码结构清晰，逻辑严谨，是学习多线程编程的优秀范例。该方案时间复杂度为O(n)，空间复杂度为O(1)，效率较高。