leetcode
leetcode 1001 ~ 1050
交替打印 FooBar

交替打印 FooBar

难度:

标签:

题目描述

代码结果

运行时间: 36 ms, 内存: 17.0 MB


/* 思路:
 * 使用 Java Stream 来实现该功能虽然不常见,但可以通过并行流和同步机制结合来实现。
 * 我们依然使用锁和条件变量来确保线程同步,并结合 Java Stream 的并行处理能力。
 */

import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
import java.util.stream.IntStream;

public class FooBarStream {
    private int n;
    private Lock lock = new ReentrantLock();
    private Condition fooCondition = lock.newCondition();
    private Condition barCondition = lock.newCondition();
    private boolean fooTurn = true;

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

    public void foo() throws InterruptedException {
        IntStream.range(0, n).parallel().forEach(i -> {
            lock.lock();
            try {
                while (!fooTurn) {
                    fooCondition.await();
                }
                System.out.print("foo");
                fooTurn = false;
                barCondition.signal();
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            } finally {
                lock.unlock();
            }
        });
    }

    public void bar() throws InterruptedException {
        IntStream.range(0, n).parallel().forEach(i -> {
            lock.lock();
            try {
                while (fooTurn) {
                    barCondition.await();
                }
                System.out.print("bar");
                fooTurn = true;
                fooCondition.signal();
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            } finally {
                lock.unlock();
            }
        });
    }
}

解释

方法:

该题解采用了线程同步的方法来保证'foo'和'bar'按顺序交替打印。具体地,使用了两个互斥锁(fooLock和barLock)来控制打印的顺序。在初始化时,fooLock被锁定,而barLock是打开的。这样一来,在foo线程开始时,它会因为fooLock被锁定而等待,直到bar线程释放fooLock。同样,bar线程会因为barLock被锁定而等待,直到foo线程释放barLock。这样就实现了foo和bar的交替打印。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
在初始化时,为什么要先锁定fooLock而不是barLock,这样的顺序有什么特别的意义吗?
在初始化时先锁定fooLock而不是barLock是为了确保'foo'首先打印。该程序设计要求'foo'和'bar'交替打印,从'foo'开始。因此,通过先锁定fooLock,初始化时保证了foo线程在开始打印前必须等待bar线程释放fooLock,而bar线程在开始时会检查fooLock是否释放,从而阻止bar线程先于foo线程运行。这确保了打印顺序始终以'foo'开头。
🦆
线程同步中使用互斥锁可能会导致死锁,此解决方案中有什么机制来防止死锁的发生?
在这个特定的解决方案中,死锁的风险被有效地避免了,因为锁的获取和释放是以严格交替的方式进行的。具体来说,foo线程和bar线程各自持有一个锁,并且只在对方线程释放其锁之后才尝试获取锁。这种交替方式(foo获取fooLock后释放barLock,bar获取barLock后释放fooLock)避免了循环等待条件,这是死锁的必要条件之一。因此,只要遵循这种严格的顺序,就不会发生死锁。
🦆
为什么选择使用互斥锁而不是其他同步机制,例如信号量或条件变量?
互斥锁在这种情况下是简单且有效的选择,因为它们提供了一种易于理解和实现的方式来保证两个线程之间的严格交替执行。虽然信号量和条件变量也可以用于线程同步,但互斥锁在这个问题的上下文中提供了直接的控制和较少的开销。使用互斥锁可以直接控制线程的执行顺序,而信号量或条件变量通常用于更复杂的同步场景,如控制对一组资源的访问或当多个条件需要同时满足时。
🦆
在foo和bar方法中,锁的获取与释放顺序是否会影响程序的正确性,如果影响,是如何影响的?
在foo和bar方法中,锁的获取与释放顺序对程序的正确性至关重要。如果更改了获取或释放锁的顺序,可能会导致程序无法按预期工作,比如打印顺序错误或发生死锁。在当前实现中,foo方法先获取barLock,完成打印后释放fooLock;bar方法先获取fooLock,完成打印后释放barLock。这种顺序保证了每个线程在执行打印操作后会释放另一个线程需要的锁,从而使得打印操作能够交替进行。如果更改顺序,例如foo方法释放barLock之前尝试获取fooLock,将造成死锁,因为它们都在等待对方释放锁。

相关问题

按序打印

给你一个类:

public class Foo {
  public void first() { print("first"); }
  public void second() { print("second"); }
  public void third() { print("third"); }
}

三个不同的线程 A、B、C 将会共用一个 Foo 实例。

  • 线程 A 将会调用 first() 方法
  • 线程 B 将会调用 second() 方法
  • 线程 C 将会调用 third() 方法

请设计修改程序,以确保 second() 方法在 first() 方法之后被执行,third() 方法在 second() 方法之后被执行。

提示:

  • 尽管输入中的数字似乎暗示了顺序,但是我们并不保证线程在操作系统中的调度顺序。
  • 你看到的输入格式主要是为了确保测试的全面性。

 

示例 1:

输入:nums = [1,2,3]
输出:"firstsecondthird"
解释:
有三个线程会被异步启动。输入 [1,2,3] 表示线程 A 将会调用 first() 方法,线程 B 将会调用 second() 方法,线程 C 将会调用 third() 方法。正确的输出是 "firstsecondthird"。

示例 2:

输入:nums = [1,3,2]
输出:"firstsecondthird"
解释:
输入 [1,3,2] 表示线程 A 将会调用 first() 方法,线程 B 将会调用 third() 方法,线程 C 将会调用 second() 方法。正确的输出是 "firstsecondthird"。

 

提示:
  • nums[1, 2, 3] 的一组排列

打印零与奇偶数

现有函数 printNumber 可以用一个整数参数调用,并输出该整数到控制台。

  • 例如,调用 printNumber(7) 将会输出 7 到控制台。

给你类 ZeroEvenOdd 的一个实例,该类中有三个函数:zeroevenoddZeroEvenOdd 的相同实例将会传递给三个不同线程:

  • 线程 A:调用 zero() ,只输出 0
  • 线程 B:调用 even() ,只输出偶数
  • 线程 C:调用 odd() ,只输出奇数

修改给出的类,以输出序列 "010203040506..." ,其中序列的长度必须为 2n

实现 ZeroEvenOdd 类:

  • ZeroEvenOdd(int n) 用数字 n 初始化对象,表示需要输出的数。
  • void zero(printNumber) 调用 printNumber 以输出一个 0 。
  • void even(printNumber) 调用printNumber 以输出偶数。
  • void odd(printNumber) 调用 printNumber 以输出奇数。

 

示例 1:

输入:n = 2
输出:"0102"
解释:三条线程异步执行,其中一个调用 zero(),另一个线程调用 even(),最后一个线程调用odd()。正确的输出为 "0102"。

示例 2:

输入:n = 5
输出:"0102030405"

 

提示:

  • 1 <= n <= 1000