第799题
题目描述：
我们把玻璃杯摆成金字塔的形状，其中 第一层 有 1 个玻璃杯， 第二层 有 2 个，依次类推到第 100 层，每个玻璃杯 (250ml) 将盛有香槟。
从顶层的第一个玻璃杯开始倾倒一些香槟，当顶层的杯子满了，任何溢出的香槟都会立刻等流量的流向左右两侧的玻璃杯。当左右两边的杯子也满了，就会等流量的流向它们左右两边的杯子，依次类推。（当最底层的玻璃杯满了，香槟会流到地板上）
例如，在倾倒一杯香槟后，最顶层的玻璃杯满了。倾倒了两杯香槟后，第二层的两个玻璃杯各自盛放一半的香槟。在倒三杯香槟后，第二层的香槟满了 - 此时总共有三个满的玻璃杯。在倒第四杯后，第三层中间的玻璃杯盛放了一半的香槟，他两边的玻璃杯各自盛放了四分之一的香槟。
| Level | AC rate |
| Medium | 43.0% |
题目解析：
如下图所示，可以总结得到，一个杯子流入的两个杯子满足这样的规律，它流入的左边的杯子行数比它多1，列数和它一样，流入的右边的杯子行数和列数均比它多1。
我们先将所有的酒倒入顶层的杯子里，暂且不考虑杯子的容量，然后将杯子里的酒减去1再除以2，若大于0则放进左下和右下两个杯子里，遍历所有杯子，直到需要返回结果的杯子。代码如下，需要注意的是，再返回杯子中的酒的时候，需要判断杯子内的酒是否大于1，若大于1则返回1即可。
class Solution {
public double champagneTower(int poured, int query_row, int query_glass) {
double[][] ml = new double[100][100];
ml[0][0] = poured;
for(int i = 0; i<=query_row;i++){
for(int j = 0; j<=i ;j++){
double sul = (ml[i][j]-1)/2;
if(sul>0&&i<99){
ml[i+1][j] += sul;
ml[i+1][j+1] += sul;
}
}
}
return Math.min(1,ml[query_row][query_glass]);
}
}这里还有一点需要注意，因为题目说了香槟塔最多有100层，所以当我们计算到最后一层时，已经没有下一层杯子来装多余的酒了，这个时候就不需要计算下一层杯子中的酒了，可以当做酒流到了地上。
执行用时：4 ms, 在所有 Java 提交中击败了68.40%的用户
内存消耗：42 MB, 在所有 Java 提交中击败了62.53%的用户
第16.04题 井字游戏
题目描述：
设计一个算法，判断玩家是否赢了井字游戏。输入是一个 N x N 的数组棋盘，由字符" "，"X"和"O"组成，其中字符" "代表一个空位。
以下是井字游戏的规则：
玩家轮流将字符放入空位（" "）中。
第一个玩家总是放字符"O"，且第二个玩家总是放字符"X"。
"X"和"O"只允许放置在空位中，不允许对已放有字符的位置进行填充。
当有N个相同（且非空）的字符填充任何行、列或对角线时，游戏结束，对应该字符的玩家获胜。
当所有位置非空时，也算为游戏结束。
如果游戏结束，玩家不允许再放置字符。
如果游戏存在获胜者，就返回该游戏的获胜者使用的字符（"X"或"O"）；如果游戏以平局结束，则返回 "Draw"；如果仍会有行动（游戏未结束），则返回 "Pending"。
| Level | AC rate |
| Medium | 46.6% |
题目解析：
很简单，因为这个游戏大家都是按规则来的，不存在不合理的情况。那么就只剩四个情况，"X"赢，"O"赢，平均，没下完。先设计一个方法判断是否存在行连续、列连续、斜线连续的"O"或"X"，若存在则返回对应的"O"或"X"，若没人赢那么只剩两个情况，没下完或者平手，则遍历整个棋盘，存在空位的话，则棋还没下完，若不存在则为平手。代码如下：
class Solution {
public String tictactoe(String[] board) {
int len = board.length;
if(win(board,'X',len))return "X";
if(win(board,'O',len))return "O";
if(empty(board,len))return "Pending";
else return "Draw";
}
boolean win(String[] board, char flag , int len){
int decide = 0;
for(int i = 0 ; i<len ; i++){
if(decide == 0){
for(int j = 0; j<len ; j++){
if(flag!=(board[i].charAt(j)))break;
if(j==len-1)decide=1;
}
for(int j = 0; j<len ; j++){
if(flag!=(board[j].charAt(i)))break;
if(j==len-1)decide=1;
}
for(int j = 0; j<len ; j++){
if(flag!=(board[j].charAt(j)))break;
if(j==len-1)decide=1;
}
for(int j = 0; j<len ; j++){
if(flag!=(board[j].charAt(len-1-j)))break;
if(j==len-1)decide=1;
}
}
}
return decide==1;
}
boolean empty(String[] board, int len){
for(int i = 0; i<len ; i++){
for(int j = 0; j<len ; j++){
if(board[i].charAt(j)==' ')return true;
}
}
return false;
}
}执行用时：1 ms, 在所有 Java 提交中击败了98.40%的用户
内存消耗：39.2 MB, 在所有 Java 提交中击败了75.47%的用户