LeetCode 1226. 哲学家进餐

Categories:

题目描述
思路分析
1. 解法一：限制并发 + 互斥锁（推荐）
相似题目

题目描述

✅ 1226. 哲学家进餐

思路分析

解法一：限制并发 + 互斥锁（推荐）

核心思路：

使用一个容量为 4 的信号量限制最多 4 位哲学家同时尝试拿叉子。

每个叉子使用互斥锁保护，按固定顺序获取左右叉子。

拿到两把叉子后进餐并释放。

复杂度分析：

时间复杂度：O(1)，每次操作固定步骤。

空间复杂度：O(1)。

import java.util.concurrent.Semaphore;
import java.util.concurrent.locks.ReentrantLock;

class DiningPhilosophers {
    private final Semaphore room = new Semaphore(4);
    private final ReentrantLock[] forks = new ReentrantLock[5];

    public DiningPhilosophers() {
        for (int i = 0; i < 5; i++) {
            forks[i] = new ReentrantLock();
        }
    }

    public void wantsToEat(int philosopher,
                           Runnable pickLeftFork,
                           Runnable pickRightFork,
                           Runnable eat,
                           Runnable putLeftFork,
                           Runnable putRightFork) throws InterruptedException {
        int left = philosopher;
        int right = (philosopher + 1) % 5;

        room.acquire();
        forks[left].lock();
        forks[right].lock();

        pickLeftFork.run();
        pickRightFork.run();
        eat.run();
        putRightFork.run();
        putLeftFork.run();

        forks[right].unlock();
        forks[left].unlock();
        room.release();
    }
}

import "sync"

type DiningPhilosophers struct {
	room  chan struct{}
	forks []sync.Mutex
}

func Constructor() DiningPhilosophers {
	d := DiningPhilosophers{
		room:  make(chan struct{}, 4),
		forks: make([]sync.Mutex, 5),
	}
	return d
}

func (d *DiningPhilosophers) wantsToEat(philosopher int,
	pickLeftFork func(),
	pickRightFork func(),
	eat func(),
	putLeftFork func(),
	putRightFork func()) {
	left := philosopher
	right := (philosopher + 1) % 5

	d.room <- struct{}{}
	d.forks[left].Lock()
	d.forks[right].Lock()

	pickLeftFork()
	pickRightFork()
	eat()
	putRightFork()
	putLeftFork()

	d.forks[right].Unlock()
	d.forks[left].Unlock()
	<-d.room
}

相似题目

题目	难度	考察点
1226. 哲学家进餐	中等	并发控制
1114. 按序打印	简单	并发控制
1115. 交替打印 FooBar	中等	并发控制
1116. 打印零与奇偶数	中等	并发控制
1195. 交替打印字符串	中等	并发控制

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/67168940