leetcode 1114 按序打印 Print in Order

目录

1. 解答
   1. 解法一 信号量
   2. 解法二 循环 + sleep
   3. 解法三 队列
   4. 解法四
   5. 错误的解法

我们提供了一个类：

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”。

注意:

尽管输入中的数字似乎暗示了顺序，但是我们并不保证线程在操作系统中的调度顺序。

你看到的输入格式主要是为了确保测试的全面性。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/print-in-order
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解答

解法一 信号量

import threading
class Foo:
    def __init__(self):
        self.sem2 = threading.Semaphore(0)
        self.sem3 = threading.Semaphore(0)

    def first(self, printFirst: 'Callable[[], None]') -> None:
        # printFirst() outputs "first". Do not change or remove this line.
        printFirst()
        self.sem2.release()

    def second(self, printSecond: 'Callable[[], None]') -> None:
        self.sem2.acquire()
        # printSecond() outputs "second". Do not change or remove this line.
        printSecond()
        self.sem3.release()

    def third(self, printThird: 'Callable[[], None]') -> None:
        self.sem3.acquire()
        # printThird() outputs "third". Do not change or remove this line.
        printThird()

解法二 循环 + sleep

循环里不加 sleep 而是用 pass 的话会超时。可能判题的时候计算的是 cpu 时间。

import time
class Foo:
    def __init__(self):
        self.cur = 0

    def first(self, printFirst: 'Callable[[], None]') -> None:        
        # printFirst() outputs "first". Do not change or remove this line.
        printFirst()
        self.cur = 1

    def second(self, printSecond: 'Callable[[], None]') -> None:
        while self.cur < 1: time.sleep(0.01)
        # printSecond() outputs "second". Do not change or remove this line.
        printSecond()
        self.cur = 2

    def third(self, printThird: 'Callable[[], None]') -> None:
        while self.cur < 2: time.sleep(0.01)
        # printThird() outputs "third". Do not change or remove this line.
        printThird()

解法三 队列

import queue
class Foo:
    def __init__(self):
        self.q2 = queue.Queue()
        self.q3 = queue.Queue()

    def first(self, printFirst: 'Callable[[], None]') -> None:        
        # printFirst() outputs "first". Do not change or remove this line.
        printFirst()
        self.q2.put(1)

    def second(self, printSecond: 'Callable[[], None]') -> None:
        self.q2.get()
        # printSecond() outputs "second". Do not change or remove this line.
        printSecond()
        self.q3.put(1)

    def third(self, printThird: 'Callable[[], None]') -> None:
        self.q3.get()
        # printThird() outputs "third". Do not change or remove this line.
        printThird()

解法四

错误的解法

超时

class Foo:
    def __init__(self):
        self.cur = 0

    def first(self, printFirst: 'Callable[[], None]') -> None:        
        # printFirst() outputs "first". Do not change or remove this line.
        printFirst()
        self.cur = 1

    def second(self, printSecond: 'Callable[[], None]') -> None:
        while self.cur < 1: pass
        # printSecond() outputs "second". Do not change or remove this line.
        printSecond()
        self.cur = 2

    def third(self, printThird: 'Callable[[], None]') -> None:
        while self.cur < 2: pass
        # printThird() outputs "third". Do not change or remove this line.
        printThird()