跳至正文

每日一题——838. 推多米诺

838. 推多米诺

n 张多米诺骨牌排成一行,将每张多米诺骨牌垂直竖立。在开始时,同时把一些多米诺骨牌向左或向右推。

每过一秒,倒向左边的多米诺骨牌会推动其左侧相邻的多米诺骨牌。同样地,倒向右边的多米诺骨牌也会推动竖立在其右侧的相邻多米诺骨牌。

如果一张垂直竖立的多米诺骨牌的两侧同时有多米诺骨牌倒下时,由于受力平衡, 该骨牌仍然保持不变。

就这个问题而言,我们会认为一张正在倒下的多米诺骨牌不会对其它正在倒下或已经倒下的多米诺骨牌施加额外的力。

给你一个字符串 dominoes 表示这一行多米诺骨牌的初始状态,其中:

dominoes[i] = ‘L’,表示第 i 张多米诺骨牌被推向左侧,
dominoes[i] = ‘R’,表示第 i 张多米诺骨牌被推向右侧,
dominoes[i] = ‘.’,表示没有推动第 i 张多米诺骨牌。
返回表示最终状态的字符串。


我会觉得模拟的思路比较简单一点

就是多米诺骨牌最终状态是由两头决定的

同向就跟着同向

不同向我就竖着

只有一边倒另一边没有我就跟那一边倒的

那我就枚举每一个竖着的多米诺骨牌

然后看看他们两边是什么样子的

public class Solution {
    public string PushDominoes(string dominoes) {
        char[] s = dominoes.ToCharArray();
        int n = s.Length;
        int i = 0;
        char left = 'L';

        while(i<n)
        {
            int j = i;//在这里是枚举 每次都以这个来判断
            while(j<n && s[j] == '.')
            {
                j++;//没有被推的多米诺骨牌
            }
            char right = j<n ? s[j] : 'R';
            if(left == right)
            {
                while(i<j)
                {
                    s[i++] = right;//方向相同就导向同一方向
                }
            }
            else if(left == 'R' && right == 'L')
            {
                int k = j - 1;
                while(i<k)
                {
                    s[i++] = 'R';
                    s[k--] = 'L';//方向相对 从两侧向中间倒
                }
            }

            left = right;
            i = j + 1;
        }

        return new string(s);
    }
}

 

发表评论

您的电子邮箱地址不会被公开。