Leetcode 多线程部分
1114. 按序打印
题目大意：三个线程公用一个Foo实例，不论调用顺序如何，每次都按顺序打印出onetwothree。
class Foo {
public Foo() {
}
int flag = 0;
public synchronized void first(Runnable printFirst) throws InterruptedException {
// printFirst.run() outputs "first". Do not change or remove this line.
printFirst.run();
flag = 1;
notifyAll();
}
public synchronized void second(Runnable printSecond) throws InterruptedException {
// printSecond.run() outputs "second". Do not change or remove this line.
while( flag != 1) wait();
printSecond.run();
flag = 2;
notifyAll();
}
public synchronized void third(Runnable printThird) throws InterruptedException {
// printThird.run() outputs "third". Do not change or remove this line.
while( flag != 2) wait();
printThird.run();
flag = 3;
}
}1226. 哲学家进餐
题目大意：五个哲学家围坐着吃面，要左手右手各一个叉子才能开吃，每人点了可能不止一碗面，要求协调运作他们吃面。
我一直寻思着为啥吃面要两个叉子而且还是共用的。 预先检测死锁，若会产生死锁则使线程阻塞等待。
class DiningPhilosophers {
public DiningPhilosophers() {
}
int status[] = new int[5]; // 状压表示每个哲学家手中叉子的状态：0-空，1-左手，2-右手，3-双手
// call the run() method of any runnable to execute its code
public synchronized void wantsToEat(int philosopher,
Runnable pickLeftFork,
Runnable pickRightFork,
Runnable eat,
Runnable putLeftFork,
Runnable putRightFork) throws InterruptedException {
int id = philosopher;
if( isLeftFree(id)) {
while( forcast(id, 1)) wait(); // 若预测左手拿起就会死锁，则阻塞等待
pickLeftFork.run();
status[id] |= 1;
}
if( isRightFree(id)) {
while( forcast(id, 2)) wait();
pickRightFork.run();
status[id] |= 2;
}
assert( status[id] == 3);
eat.run();
putLeftFork.run();
status[id] ^= 1;
putRightFork.run();
status[id] ^= 2;
notifyAll(); // 释放双手叉子后通知其他哲学家
}
private boolean isLeftFree(int id) {
int lid = (id+1) %5;
return (status[lid] & 2) == 0;
}
private boolean isRightFree(int id) {
int rid = (id-1+5) %5;
return (status[rid] & 1) == 0;
}
private boolean isDeadLock()
{
boolean flag = true;
for( int i = 0; i < 5; i++)
if(status[i] != 1) flag = false;
if(flag == true) return true;
flag = true;
for( int i = 0; i < 5; i++)
if( status[i] != 2) flag = false;
return flag;
}
private boolean forcast(int id, int s) // 预测这个哲学家左手或右手拿了叉子会不会造成死锁
{
status[id] |= s;
boolean ret = isDeadLock();
status[id] ^= s;
return ret;
}
}1116. 打印零与奇偶数
题目大意：打印0,打印奇数，打印偶数的三个线程协调进行，最后输出 0102030405..0n
class ZeroEvenOdd {
private int n;
public ZeroEvenOdd(int n) {
this.n = n;
}
int flag = 0; // 0-0, 1-odd, 2-even
// printNumber.accept(x) outputs "x", where x is an integer.
public synchronized void zero(IntConsumer printNumber) throws InterruptedException
{
for( int i = 1; i <= n; i++)
{
while(flag != 0) wait();
printNumber.accept(0);
flag = (i &1) == 0? 2: 1;
notifyAll();
}
}
public synchronized void even(IntConsumer printNumber) throws InterruptedException
{
for( int x = 2; x <= n; x+=2)
{
while( flag != 2) wait();
printNumber.accept(x);
flag = 0;
notifyAll();
}
}
public synchronized void odd(IntConsumer printNumber) throws InterruptedException
{
for( int x = 1; x <= n; x+=2)
{
while( flag != 1) wait();
printNumber.accept(x);
flag = 0;
notifyAll();
}
}
}1188. 设计有限阻塞队列
题目大意：设计一个阻塞队列，当队满插入时等待其他线程为队列排出元素；当队空出队时等待其他线程为队列添加元素。
class BoundedBlockingQueue
{
private int arr[];
private int capacity;
private int tail = 0, len = 0; // 循环队列
public BoundedBlockingQueue(int capacity) {
this.capacity = capacity;
arr = new int[capacity];
}
public synchronized void enqueue(int element) throws InterruptedException
{
while( len == capacity) wait();
tail = (tail+1) %capacity;
arr[tail] = element; len ++;
notifyAll();
}
public synchronized int dequeue() throws InterruptedException
{
while( len == 0) wait();
int head = (tail-len-- +1+capacity) %capacity;
notifyAll();
return arr[head];
}
public synchronized int size() {
return len;
}
}1195. 交替打印字符串
题目大意：对1到n之间数字进行判断，能被3整除的输出’Fizz’，能被5整除的输出’Buzz’，既能被3整除又能被5整除的输出’FizzBuzz’，若都不是则输出这个数字。
class FizzBuzz {
private int n;
public FizzBuzz(int n) {
this.n = n;
}
int gx = 1;
// printFizz.run() outputs "fizz".
public synchronized void fizz(Runnable printFizz) throws InterruptedException
{
while( gx <= n)
{
while(gx %3 != 0) {
wait();
if( gx > n) return ; // 不及时终止就会造成错误
}
printFizz.run();
gx ++;
notifyAll();
}
}
// printBuzz.run() outputs "buzz".
public synchronized void buzz(Runnable printBuzz) throws InterruptedException
{
while( gx <= n)
{
while(gx %5 != 0) {
wait();
if( gx > n) return ;
}
printBuzz.run();
gx ++;
notifyAll();
}
}
// printFizzBuzz.run() outputs "fizzbuzz".
public synchronized void fizzbuzz(Runnable printFizzBuzz) throws InterruptedException
{
while( gx <= n)
{
while(gx %3 != 0 || gx %5 != 0) {
wait();
if( gx > n) return ;
}
printFizzBuzz.run();
gx ++;
notifyAll();
}
}
// printNumber.accept(x) outputs "x", where x is an integer.
public synchronized void number(IntConsumer printNumber) throws InterruptedException
{
while( gx <= n) {
while( gx %3 == 0 || gx %5 == 0) {
wait();
if( gx > n) return ;
}
printNumber.accept(gx++);
notifyAll();
}
}
}1115. 交替打印FooBar
题目大意：交替打印n次多线程打印’foo’和’bar’。
class FooBar {
private int n;
public FooBar(int n) {
this.n = n;
}
boolean flag = false; // 0-foo, 1-bar
public synchronized void foo(Runnable printFoo) throws InterruptedException {
for (int i = 0; i < n; i++) {
// printFoo.run() outputs "foo". Do not change or remove this line.
while( flag) wait();
printFoo.run();
flag = true;
notifyAll();
}
}
public synchronized void bar(Runnable printBar) throws InterruptedException {
for (int i = 0; i < n; i++) {
// printBar.run() outputs "bar". Do not change or remove this line.
while( !flag) wait();
printBar.run();
flag = false;
notifyAll();
}
}
}1117. H2O 生成
题目大意：将两个氢原子和一个氧原子合成一个水分子，捕获原子的操作是多线程的。
class H2O {
public H2O() {
}
int cnth = 0, cnto = 0;
public synchronized void hydrogen(Runnable releaseHydrogen) throws InterruptedException {
// releaseHydrogen.run() outputs "H". Do not change or remove this line.
while(cnth == 2 && cnto == 0) wait();
releaseHydrogen.run(); cnth++;
merge();
notify();
}
public synchronized void oxygen(Runnable releaseOxygen) throws InterruptedException {
// releaseOxygen.run() outputs "O". Do not change or remove this line.
while(cnto == 1) wait();
releaseOxygen.run(); cnto++;
merge();
notify();
}
private void merge()
{
if( cnth == 2 && cnto == 1)
cnth = cnto = 0;
}
}1279. 红绿灯路口
题目大意：在一个十字路口上，控制红绿灯让车辆通行。
开一辆车就开一次灯就行，很迷的一题。
class TrafficLight {
public TrafficLight() {
}
boolean lightA = true;
public void carArrived(
int carId, // ID of the car
int roadId, // ID of the road the car travels on. Can be 1 (road A) or 2 (road B)
int direction, // Direction of the car
Runnable turnGreen, // Use turnGreen.run() to turn light to green on current road
Runnable crossCar // Use crossCar.run() to make car cross the intersection
) {
synchronized (this)
{
if( roadId == 1)
{
if( !lightA) {
turnGreen.run();
lightA = true;
}
crossCar.run();
}
else
{
if( lightA) {
turnGreen.run();
lightA = false;
}
crossCar.run();
}
}
}
}1242. 多线程网页爬虫
题目大意：给出起点，遍历一个有向图，其中域名不同的节点不可达（不考虑端口和协议），每次获得邻接节点有15ms以内的延迟。
因为获取邻接节点会有延迟所以跑单线程会T，每次递归下一个节点时开多线程并锁住公共资源遍历一张有向图就行。
/**
* // This is the HtmlParser's API interface.
* // You should not implement it, or speculate about its implementation
* interface HtmlParser {
* public List<String> getUrls(String url) {}
* }
*/
class Solution
{
Map<String, Boolean> vis = new HashMap<>();
List<String> gans = new ArrayList<>();
static HtmlParser htmlparser;
private List<String> getNextVertixes(String u) {
return htmlparser.getUrls(u);
}
public List<String> crawl(String startUrl, HtmlParser htmlParser) {
this.htmlparser = htmlParser;
dfs(startUrl);
return gans;
}
private boolean isSameHost(String u, String v) {
return u.split("/")[2].equals(v.split("/")[2]);
}
private void dfs(String u)
{
synchronized (vis) {
if( vis.containsKey(u)) return ;
vis.put(u, true);
}
synchronized (gans) {
gans.add(u);
}
List<String> nexts = getNextVertixes(u);
List<Thread> threads = new ArrayList<>();
for( String v: nexts) {
if( !isSameHost(u, v)) continue;
Thread t = new Thread(()-> dfs(v));
threads.add(t); t.start();
}
try { for( Thread t :threads) t.join(); }
catch(InterruptedException e)
{ e.printStackTrace(); }
}
}目前题目就出了这么多。