题目大意：
哲学家进餐
5 个沉默寡言的哲学家围坐在圆桌前，每人面前一盘意面。叉子放在哲学家之间的桌面上。（5 个哲学家，5 根叉子）
所有的哲学家都只会在思考和进餐两种行为间交替。哲学家只有同时拿到左边和右边的叉子才能吃到面，而同一根叉子在同一时间只能被一个哲学家使用。每个哲学家吃完面后都需要把叉子放回桌面以供其他哲学家吃面。只要条件允许，哲学家可以拿起左边或者右边的叉子，但在没有同时拿到左右叉子时不能进食。
假设面的数量没有限制，哲学家也能随便吃，不需要考虑吃不吃得下。
设计一个进餐规则（并行算法）使得每个哲学家都不会挨饿；也就是说，在没有人知道别人什么时候想吃东西或思考的情况下，每个哲学家都可以在吃饭和思考之间一直交替下去。
哲学家从 0 到 4 按 顺时针 编号。请实现函数 void wantsToEat(philosopher, pickLeftFork, pickRightFork, eat, putLeftFork, putRightFork)：
- philosopher 哲学家的编号。
- pickLeftFork 和 pickRightFork 表示拿起左边或右边的叉子。
- eat 表示吃面。
- putLeftFork 和 pickRightFork 表示放下左边或右边的叉子。
- 由于哲学家不是在吃面就是在想着啥时候吃面，所以思考这个方法没有对应的回调。
给你 5 个线程，每个都代表一个哲学家，请你使用类的同一个对象来模拟这个过程。在最后一次调用结束之前，可能会为同一个哲学家多次调用该函数。
示例：
输入：n = 1
输出：[[4,2,1],[4,1,1],[0,1,1],[2,2,1],[2,1,1],[2,0,3],[2,1,2],[2,2,2],[4,0,3],[4,1,2],[0,2,1],[4,2,2],[3,2,1],[3,1,1],[0,0,3],[0,1,2],[0,2,2],[1,2,1],[1,1,1],[3,0,3],[3,1,2],[3,2,2],[1,0,3],[1,1,2],[1,2,2]]
解释:
n 表示每个哲学家需要进餐的次数。
输出数组描述了叉子的控制和进餐的调用，它的格式如下：
output[i] = a, b, c
a 哲学家编号。
b 指定叉子：{1 : 左边, 2 : 右边}.
c 指定行为：{1 : 拿起, 2 : 放下, 3 : 吃面}。
如 [4,2,1] 表示 4 号哲学家拿起了右边的叉子。 提示：
1 <= n <= 60
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1226
解题思路分析：
这又是一道多线程的题目，没做过相关题目的话，可以参考一下我之前的文章， LEETCODE 1115. Print FooBar Alternately 解题思路分析，其解题思路主要用到了Semaphore这个类(对应C++中的mutex)。 Semaphore 主要有两个方法：acquire()和release()，分别代表获取运行权限和释放运行权限。在 C++ 这两个方法被称为lock()和unLock()。
本题有5个哲学家，每人吃面时需要2个叉子，但桌上只有5把，也就是说相邻的两个人无法同时用餐，我们可以定义5个Semaphore控制5把叉子。哲学家0可以使用的叉子为0和1，哲学家1可以使用的叉子为1和2，以此类推。每把叉子最多拥有一个使用权限，当一个哲学家准备吃饭时，他先获得两把叉子的权限，以保证其他人无法使用，用完之后在释放权限即可。
实现代码如下：
Semaphore[] arr = new Semaphore[5]; // 定义5个Semaphore
public DiningPhilosophers() {
for(int i = 0;i<5;i++){ // 初始化每个Semaphore
arr[i] = new Semaphore(1);
}
}
// call the run() method of any runnable to execute its code
public void wantsToEat(int philosopher,
Runnable pickLeftFork,
Runnable pickRightFork,
Runnable eat,
Runnable putLeftFork,
Runnable putRightFork) throws InterruptedException {
// 得到左右两把叉子的index
int left = philosopher, right = (philosopher+1) % 5;
arr[left].acquire(); // 获得左叉子权限
arr[right].acquire(); // 获得右叉子权限
pickLeftFork.run(); // 拿起左叉子
pickRightFork.run(); // 拿起右叉子
eat.run(); // 吃面
putLeftFork.run(); // 放下左叉子
putRightFork.run(); // 放下左叉子
arr[left].release(); // 释放左叉子权限
arr[right].release(); // 释放右叉子权限
}这种解法可以通过，执行时间为9或者10ms左右。不过这种解法存在一定的bug，由于5位哲学家会被分配到5个线程，他们可能会同时执行wantsToEat方法，这时如果他们同时拿起左叉子的话，就会造成每个人手里都只有1把叉子进而任何一个人都不法吃面，同时Semaphore又没有机会被释放，从而造成死锁现象，为了解决这个问题，我们应该优化一下逻辑，让单数的人先拿右叉子，双数人先拿左叉子，这样程序开始后，哲学家0和1会同时抢夺1号叉子，哲学家2和3抢夺3号叉子，哲学家4去拿0号叉子，这样就不会发生死锁问题。修改后的代码如下：
Semaphore[] arr = new Semaphore[5];
public DiningPhilosophers() {
for(int i = 0;i<5;i++){
arr[i] = new Semaphore(1);
}
}
// call the run() method of any runnable to execute its code
public void wantsToEat(int philosopher,
Runnable pickLeftFork,
Runnable pickRightFork,
Runnable eat,
Runnable putLeftFork,
Runnable putRightFork) throws InterruptedException {
int left = philosopher, right = (philosopher+1) % 5;
if(philosopher % 2 == 0){
arr[left].acquire(); // 双数哲学家先拿左叉子
arr[right].acquire();
}else{
arr[right].acquire(); // 单数哲学家先拿右叉子
arr[left].acquire();
}
pickLeftFork.run();
pickRightFork.run();
eat.run();
putLeftFork.run();
putRightFork.run();
arr[left].release();
arr[right].release();
}本题解法执行时间为10ms。
Runtime: 10 ms, faster than 61.81% of Java online submissions for The Dining Philosophers.
Memory Usage: 41 MB, less than 100.00% of Java online submissions for The Dining Philosophers.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1226-the-dining-philosophers-解题思路分析/