第799题 香槟塔+第16.04题 井字游戏

发布于:2023-01-04 ⋅ 阅读:(230) ⋅ 点赞:(0)

第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%的用户


网站公告

今日签到

点亮在社区的每一天
去签到