LeetCode多线程题目

吹梦到西洲
LeetCode

发布于：Jul 13, 2020
次浏览

LeetCode多线程题目

1114. 按序打印

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
我们提供了一个类：
public class Foo {
  public void one() { print("one"); }
  public void two() { print("two"); }
  public void three() { print("three"); }
}

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

线程 A 将会调用 one() 方法
线程 B 将会调用 two() 方法
线程 C 将会调用 three() 方法
请设计修改程序，以确保 two() 方法在 one() 方法之后被执行，three() 方法在 two() 方法之后被执行。

- 示例1
输入: [1,2,3]
输出: "onetwothree"
解释: 
有三个线程会被异步启动。
输入 [1,2,3] 表示线程 A 将会调用 one() 方法，线程 B 将会调用 two() 方法，线程 C 将会调用 three() 方法。
正确的输出是 "onetwothree"。

- 示例2
输入: [1,3,2]
输出: "onetwothree"
解释: 
输入 [1,3,2] 表示线程 A 将会调用 one() 方法，线程 B 将会调用 three() 方法，线程 C 将会调用 two() 方法。
正确的输出是 "onetwothree"。

Solution 1 - 原子类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Foo {

  private AtomicInteger firstJobDone = new AtomicInteger(0);
  private AtomicInteger secondJobDone = new AtomicInteger(0);

  public Foo() {}

  public void first(Runnable printFirst) throws InterruptedException {
    printFirst.run(); // "first"
    // 确保打印 first 的任务完成后进行原子增加
    firstJobDone.incrementAndGet();
  }

  public void second(Runnable printSecond) throws InterruptedException {
    while (firstJobDone.get() != 1) {
      // 如果 first 任务还未完成则进行等待
    }
    printSecond.run(); // "second"
    // 确保打印 second 的任务完成后进行原子增加
    secondJobDone.incrementAndGet();
  }

  public void third(Runnable printThird) throws InterruptedException {
    while (secondJobDone.get() != 1) {
      // 如果 second 任务还未完成则进行等待
    }
    printThird.run(); // "third"
  }
}

Solution 2 - synchronized

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Foo {

    private boolean firstDone;
    private boolean secondDone;
    private Object lock = new Object();

    public Foo() {}

    public void first(Runnable printFirst) throws InterruptedException {
        synchronized(lock) {
            // printFirst.run() outputs "first". Do not change or remove this line.
            printFirst.run();
            firstDone = true;
            lock.notifyAll();
        }
    }

    public void second(Runnable printSecond) throws InterruptedException {
        synchronized(lock) {
            while (!firstDone)
                lock.wait();
            // printSecond.run() outputs "second". Do not change or remove this line.
            printSecond.run();
            secondDone = true;
            lock.notifyAll();
        }
    }

    public void third(Runnable printThird) throws InterruptedException {
        synchronized(lock) {
            while (!secondDone)
                lock.wait();
            // printThird.run() outputs "third". Do not change or remove this line.
            printThird.run();
        }
    }
}

Solution 3 - volatile

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Foo {

   private volatile boolean firstJobDone = false;
   private volatile boolean secondJobDone = false;

    public Foo() {}

    public void first(Runnable printFirst) throws InterruptedException {
        // printFirst.run() outputs "first". Do not change or remove this line.
        printFirst.run();
        firstJobDone=true;
    }

    public void second(Runnable printSecond) throws InterruptedException {
         while (!firstJobDone){
            // 等待printFirst完成
        }
        // printSecond.run() outputs "second". Do not change or remove this line.
        printSecond.run();
        secondJobDone=true;
    }

    public void third(Runnable printThird) throws InterruptedException {
        while (!secondJobDone){
            // 等待printSecond完成
        }
        // printThird.run() outputs "third". Do not change or remove this line.
        printThird.run();
    }
}

Solution 4 - 可重入锁

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Foo {
    
    private Lock lock = new ReentrantLock();
    private Condition condition = lock.newCondition();
    private int count = 1;
    
    public Foo() {}
    
    public void first(Runnable printFirst) throws InterruptedException {
        lock.lock();
        printFirst.run();
        count = 2;
        condition.signalAll();
        lock.unlock();
    }
    
    public void second(Runnable printSecond) throws InterruptedException {
        lock.lock();
        if (count != 2)
            condition.await();
        printSecond.run();
        count = 3;
        condition.signal();
        lock.unlock();
    }
    
    public void third(Runnable printThird) throws InterruptedException {
        lock.lock();
        while (count != 3)
            condition.await();
        printThird.run();
        lock.unlock();
    }
}

Solution 4 - CountDownLatch

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class Foo {
    // 声明两个 CountDownLatch变量
    private CountDownLatch countDownLatch1;
    private CountDownLatch countDownLatch2;

    public Foo() {
        // 初始化每个CountDownLatch 的值为1，表示有一个线程执行完后，执行等待的线程
        countDownLatch01 = new CountDownLatch(1);
        countDownLatch02 = new CountDownLatch(1);
    }
    
    public void first(Runnable printFirst) throws InterruptedException {
            // 当前只有 first 线程没有任何的阻碍，其余两个线程都处于等待阶段
            // printFirst.run() outputs "first". Do not change or remove this line.
            printFirst.run();
            // 直到 CountDownLatch1 里面计数为 0 才执行因调用该 countDownCatch1.await() 而等待的线程
            countDownLatch1.countDown();
    }
    public void second(Runnable printSecond) throws InterruptedException {
            // 只有 countDownLatch1 为 0 才能通过，否则会一直阻塞
            countDownLatch1.await();
            // printSecond.run() outputs "second". Do not change or remove this line.
            printSecond.run();
            // 直到 CountDownLatch2 里面计数为 0 才执行因调用该 countDownCatch2.await() 而等待的线程
            countDownLatch2.countDown();
    }
    public void third(Runnable printThird) throws InterruptedException {
            // 只有 countDownLatch2 为 0 才能通过，否则会一直阻塞
            countDownLatch2.await();
            // printThird.run() outputs "third". Do not change or remove this line.
            printThird.run();
    }
}

Solution 5 - Semaphore

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class Foo03 {
    // 声明两个Semaphore 变量
    private Semaphore spa,spb;
    
    public Foo03() {
        // 初始化 Semaphore 为 0 的原因
        // 如果这个Semaphore 为零，如果另一线程调用(acquire)这个Semaphore就会产生阻塞
        // 便可以控制 second 和 third 线程的执行
        spa = new Semaphore(0);
        spb = new Semaphore(0);
    }
    
    public void first(Runnable printFirst) throws InterruptedException {
            // printFirst.run() outputs "first". Do not change or remove this line.
            printFirst.run();
            // 只有等first线程释放Semaphore后使Semaphore值为1,另外一个线程才可以调用（acquire）
            spa.release();
    }
    
    public void second(Runnable printSecond) throws InterruptedException {
            //只有spa为1才能执行acquire，如果为0就会产生阻塞
            spa.acquire();
            // printSecond.run() outputs "second". Do not change or remove this line.
            printSecond.run();
            spb.release();
    }
    
    public void third(Runnable printThird) throws InterruptedException {
            //只有spb为1才能通过，如果为0就会阻塞
            spb.acquire();
            // printThird.run() outputs "third". Do not change or remove this line.
            printThird.run();
    }
}

1115. 交替打印FooBar

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
我们提供一个类：

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" 将被输出两次。

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：http://raymond-zhao.top/2020/07/13/2020-07-13-LeetCode-Concurrency/

更新于：Jun 20, 2021

LeetCode多线程

评论