我的博客

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
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解答

解法一 信号量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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 时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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()

解法三 队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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()

解法四

错误的解法

超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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()

评论无需登录,可以匿名,欢迎评论!