LEETCODE 1115. Print FooBar Alternately 解题思路分析

题目大意：

交替打印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 实例。其中一个线程将会调用 foo() 方法，另一个线程将会调用 bar() 方法。

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

示例 1:

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

输入: n = 2
输出: “foobarfoobar”
解释: “foobar” 将被输出两次。

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1115

解题思路分析：

这是一道多线程题，题目表述的也很清楚，即一个线程打印foo，另一个线程打印bar，分别打印n次，但要按照foo和bar交替的顺序打印出来。

如果是单线程很简单，顺序交替调用 foo() 和 bar() 各n次即可。但是在多线程中，每个线程被执行的时间点并不能被控制，谁先谁后完全没有规律，这就需要我们来对线程进行管理，控制他们的执行顺序才可以。

因此这里我们需要使用到 Java中Semaphore这个对象(对应C++中的mutex)。 Semaphore 主要有两个方法：acquire()和release()，分别代表获取运行权限和释放运行权限。在 C++ 这两个方法被称为lock()和unLock()

我们可以定义两个 Semaphore 对象s1和s2分别管理 foo() 和 bar() 的执行许可。当需要执行 foo() 时， s1 获取权限（s1.acquire），执行完打印操作后，为了不再继续执行 foo() 先不要释放s1的权限，而是释放s2的权限（s2.release）。轮到 bar() 方法时获取s2的权限，执行完打印之后再释放s1的权限，一直循环到结束。

具体的实现可以参照下面完整代码。

private int n;
Semaphore semaphoreFoo = new Semaphore(1);
Semaphore semaphoreBar = new Semaphore(0);
public FooBar(int n) {
    this.n = n;
}

public void foo(Runnable printFoo) throws InterruptedException {
    for (int i = 0; i < n; i++) {
        semaphoreFoo.acquire();
        // printFoo.run() outputs "foo". Do not change or remove this line.
        printFoo.run();
        semaphoreBar.release();
    }
}

public void bar(Runnable printBar) throws InterruptedException {
    for (int i = 0; i < n; i++) {
        semaphoreBar.acquire();
        // printBar.run() outputs "bar". Do not change or remove this line.
        printBar.run();
        semaphoreFoo.release();
    }
}

最后在简单的描述一下整个代码的执行顺序：

1. semaphoreFoo 的初始最大同时运行许可数为1。（new Semaphore(1)）
2. semaphoreBar 的初始最大同时运行许可数为0。（new Semaphore(0)）
3. foo和bar两个方法会同时被2个线程调用。此时bar方法中 semaphoreBar 的运行许可数为0，因此semaphoreBar.acquire()方法无法获取到权限，线程被挂起。同时另一个线程的foo方法中，semaphoreFoo拥有1个运行权限，因此，semaphoreFoo.acquire()可以获取到执行许可，printFoo.run()执行后，通过semaphoreBar.release()，为 semaphoreBar 释放了一个运行权限。
4. 此时，刚才被挂起的 semaphoreBar.acquire() 方法可以获得运行权限，并可以继续执行接下来的printBar.run()方法。与此同时，foo方法循环到第二次，由于此时 semaphoreFoo 还没有被释放，因此semaphoreFoo再次获取权限（semaphoreFoo.acquire()）失败，被临时挂起。当 printBar 执行完成之后，释放了semaphoreFoo（semaphoreFoo.release()）， foo 方法才可获得权限继续循环。

本解法用时16ms。

Runtime: 16 ms, faster than 83.17% of Java online submissions for Print FooBar Alternately.

Memory Usage: 36.7 MB, less than 100.00% of Java online submissions for Print FooBar Alternately.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1115-print-foobar-alternately-解题思路分析/