交替打印 FooBar

1115. 交替打印 FooBar

给你一个类：

class FooBar {
  public void foo() {
    for (int i = 0; i < n; i++) {
      print("foo");
    }
  }

  public void bar() {
    for (int i = 0; i < n; i++) {
      print("bar");
    }
  }
}

两个不同的线程将会共用一个 FooBar 实例：

线程 A 将会调用 foo() 方法，而
线程 B 将会调用 bar() 方法

请设计修改程序，以确保 "foobar" 被输出 n 次。

示例 1：

输入：n = 1
输出："foobar"
解释：这里有两个线程被异步启动。其中一个调用 foo() 方法, 另一个调用 bar() 方法，"foobar" 将被输出一次。

示例 2：

输入：n = 2
输出："foobarfoobar"
解释："foobar" 将被输出两次。

提示：

1 <= n <= 1000

相似题目

按序打印

打印零与奇偶数

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class FooBar { private: int n; public: FooBar(int n) { this->n = n; } void foo(function<void()> printFoo) { for (int i = 0; i < n; i++) { // printFoo() outputs "foo". Do not change or remove this line. printFoo(); } } void bar(function<void()> printBar) { for (int i = 0; i < n; i++) { // printBar() outputs "bar". Do not change or remove this line. printBar(); } } };

cpp 解法, 执行用时: 188 ms, 内存消耗: 8.3 MB, 提交时间: 2023-10-28 10:46:28

#include <semaphore.h> // 需要手动包含信号量头文件

// 信号量
class FooBar {
private:
    int n;
    sem_t foo_done, bar_done;
public:
    FooBar(int n) : n(n) {
        sem_init(&foo_done, 0 , 0);
        sem_init(&bar_done, 0 , 1);
    }

    void foo(function<void()> printFoo) {
        for (int i = 0; i < n; i++) {
            sem_wait(&bar_done);
            printFoo();
            sem_post(&foo_done);
        }
    }

    void bar(function<void()> printBar) {
        for (int i = 0; i < n; i++) {
            sem_wait(&foo_done);
            printBar();
            sem_post(&bar_done);
        }
    }
};



// 原子操作
class FooBar1 {
private:
    int n;
    atomic<bool> foo_done = false;
public:
    FooBar1(int n) : n(n) {}

    void foo(function<void()> printFoo) {
        for (int i = 0; i < n; i++) {
            while (foo_done) {
                this_thread::yield();
            }
            printFoo();
            foo_done = true;
        }
    }

    void bar(function<void()> printBar) {
        for (int i = 0; i < n; i++) {
            while (!foo_done) {
                this_thread::yield();
            }
            printBar();
            foo_done = false;
        }
    }
};

// 互斥锁+条件变量
class FooBar2 {
private:
    int n;
    mutex mtx;
    condition_variable cv;
    bool foo_done = false;
public:
    FooBar2(int n) : n(n) {}

    void foo(function<void()> printFoo) {
        for (int i = 0; i < n; i++) {
            unique_lock<mutex> lock(mtx);
            cv.wait(lock, [&]() { return !foo_done; });
            printFoo();
            foo_done = true;
            cv.notify_one();
        }
    }

    void bar(function<void()> printBar) {
        for (int i = 0; i < n; i++) {
            unique_lock<mutex> lock(mtx);
            cv.wait(lock, [&]() { return foo_done; });
            printBar();
            foo_done = false;
            cv.notify_one();
        }
    }
};

java 解法, 执行用时: 17 ms, 内存消耗: 41.4 MB, 提交时间: 2023-10-28 10:44:06

//手太阴肺经 BLOCKING Queue
class FooBar {
    private int n;
    private BlockingQueue<Integer> bar = new LinkedBlockingQueue<>(1);
    private BlockingQueue<Integer> foo = new LinkedBlockingQueue<>(1);
    public FooBar(int n) {
        this.n = n;
    }
    public void foo(Runnable printFoo) throws InterruptedException {
        for (int i = 0; i < n; i++) {
            foo.put(i);
            printFoo.run();
            bar.put(i);
        }
    }

    public void bar(Runnable printBar) throws InterruptedException {
        for (int i = 0; i < n; i++) {
            bar.take();
            printBar.run();
            foo.take();
        }
    }
}

//手阳明大肠经CyclicBarrier 控制先后
class FooBar6 {
    private int n;

    public FooBar6(int n) {
        this.n = n;
    }

    CyclicBarrier cb = new CyclicBarrier(2);
    volatile boolean fin = true;

    public void foo(Runnable printFoo) throws InterruptedException {
        for (int i = 0; i < n; i++) {
            while(!fin);
            printFoo.run();
            fin = false;
            try {
                cb.await();
            } catch (BrokenBarrierException e) {}
        }
    }

    public void bar(Runnable printBar) throws InterruptedException {
        for (int i = 0; i < n; i++) {
            try {
                cb.await();
            } catch (BrokenBarrierException e) {}
            printBar.run();
            fin = true;
        }
    }
}

//手少阴心经 自旋 + 让出CPU
class FooBar5 {
    private int n;

    public FooBar5(int n) {
        this.n = n;
    }

    volatile boolean permitFoo = true;

    public void foo(Runnable printFoo) throws InterruptedException {     
        for (int i = 0; i < n; ) {
            if(permitFoo) {
        	    printFoo.run();
            	i++;
            	permitFoo = false;
            }else{
                Thread.yield();
            }
        }
    }

    public void bar(Runnable printBar) throws InterruptedException {       
        for (int i = 0; i < n; ) {
            if(!permitFoo) {
        	printBar.run();
        	i++;
        	permitFoo = true;
            }else{
                Thread.yield();
            }
        }
    }
}



//手少阳三焦经 可重入锁 + Condition
class FooBar4 {
    private int n;

    public FooBar4(int n) {
        this.n = n;
    }
    Lock lock = new ReentrantLock(true);
    private final Condition foo = lock.newCondition();
    volatile boolean flag = true;
    public void foo(Runnable printFoo) throws InterruptedException {
        for (int i = 0; i < n; i++) {
            lock.lock();
            try {
            	while(!flag) {
                    foo.await();
                }
                printFoo.run();
                flag = false;
                foo.signal();
            }finally {
            	lock.unlock();
            }
        }
    }

    public void bar(Runnable printBar) throws InterruptedException {
        for (int i = 0; i < n;i++) {
            lock.lock();
            try {
            	while(flag) {
                    foo.await();
            	}
                printBar.run();
                flag = true;
                foo.signal();
            }finally {
            	lock.unlock();
            }
        }
    }
}

//手厥阴心包经 synchronized + 标志位 + 唤醒
class FooBar3 {
    private int n;
    // 标志位，控制执行顺序，true执行printFoo，false执行printBar
    private volatile boolean type = true;
    private final Object foo=  new Object(); // 锁标志

    public FooBar3(int n) {
        this.n = n;
    }
    public void foo(Runnable printFoo) throws InterruptedException {
        for (int i = 0; i < n; i++) {
            synchronized (foo) {
                while(!type){
                    foo.wait();
                }
                printFoo.run();
                type = false;
                foo.notifyAll();
            }
        }
    }

    public void bar(Runnable printBar) throws InterruptedException {
        for (int i = 0; i < n; i++) {
            synchronized (foo) {
                while(type){
                    foo.wait();
                }
                printBar.run();
                type = true;
                foo.notifyAll();
            }
        }
    }
}


//手太阳小肠经 信号量 适合控制顺序
class FooBar2 {
    private int n;
    private Semaphore foo = new Semaphore(1);
    private Semaphore bar = new Semaphore(0);
    public FooBar2(int n) {
        this.n = n;
    }

    public void foo(Runnable printFoo) throws InterruptedException {
        for (int i = 0; i < n; i++) {
            foo.acquire();
        	printFoo.run();
            bar.release();
        }
    }
    public void bar(Runnable printBar) throws InterruptedException {
        for (int i = 0; i < n; i++) {
            bar.acquire();
        	printBar.run();
            foo.release();
        }
    }
}

python3 解法, 执行用时: 60 ms, 内存消耗: 15.2 MB, 提交时间: 2022-08-12 11:10:53

import threading

'''
解题思路

import threading

s=threading.Semaphore(1) #1代表计数器
s.acquire() #p操作，减一，如果小于0阻塞
s.release() #v操作，加一，如果大于等于0则说明有线程在等待

'''

class FooBar:
    def __init__(self, n):
        self.n = n
        self.s1=threading.Semaphore(1)
        self.s2=threading.Semaphore(0)


    def foo(self, printFoo: 'Callable[[], None]') -> None:
        
        for i in range(self.n):
            
            # printFoo() outputs "foo". Do not change or remove this line.
            self.s1.acquire()
            printFoo()
            self.s2.release()


    def bar(self, printBar: 'Callable[[], None]') -> None:
        
        for i in range(self.n):
            
            # printBar() outputs "bar". Do not change or remove this line.
            self.s2.acquire()
            printBar()
            self.s1.release()

python3 解法, 执行用时: 60 ms, 内存消耗: 15.1 MB, 提交时间: 2022-08-12 11:09:46

import threading
from threading import Lock

# python3 交替锁，线程负责锁自己及为另一个线程解锁
class FooBar:
    def __init__(self,n):
        self.n=n
        self.LockFoo = Lock()
        self.LockBar = Lock()
        self.LockBar.acquire()


    def foo(self, printFoo: 'Callable[[], None]') -> None:
        for i in range(self.n):
            self.LockFoo.acquire()
            printFoo()
            self.LockBar.release()        


    def bar(self, printBar: 'Callable[[], None]') -> None:
        for i in range(self.n):
            self.LockBar.acquire()
            printBar()
            self.LockFoo.release()

上一题

下一题

详情