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.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1115-print-foobar-alternately-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , 标签。将固定链接加入收藏夹。

LEETCODE 1115. Print FooBar Alternately 解题思路分析》有3条回应

  1. Pingback引用通告: LEETCODE 1117. Building H2O 解题思路分析 - LEETCODE从零刷LEETCODE从零刷

  2. Pingback引用通告: LEETCODE 1226. The Dining Philosophers 解题思路分析 - LEETCODE从零刷LEETCODE从零刷

  3. Pingback引用通告: LEETCODE 1195. Fizz Buzz Multithreaded 解题思路分析 - LEETCODE从零刷LEETCODE从零刷

发表评论

您的电子邮箱地址不会被公开。