Leetcode 838 Push Dominoes

发表于 |

图1

图2

分析：
就是一个超简单的推木板游戏，我是搞不懂为什么discuss里面那么多人还tle呢，直接遍历一遍就可以出结果，one pass solution,O(1) space, 要不是英文不太好就去发攻略了罒ω罒

思路：
用res存储最后的结果，遍历整个字符串，’.’直接跳过，当遍历到’L’时，看上一个出现的是’L’还是’R’,如果是’L’，全往左边倒，如果是’R’，计算距离一半R一半L；遍历到’R’同理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution(object):
    def pushDominoes(self, dominoes):
        """
        :type dominoes: str
        :rtype: str
        """
        res = ''
        i = 0
        # 上一个出现的关键点用last表示，初始为None，处理左边界情况
        last = None
        while i < len(dominoes):
            j = i
            # 遍历到'.'就不管，一直到找到一个'R或L'为止
            while j+1 < len(dominoes) and dominoes[j] == '.': j += 1 
            # 找到L的情况
            if dominoes[j] == 'L':
                if last == 'R':
                    res += (j-i)/2 * 'R' + (j-i)%2 * '.' + (j-i)/2 * 'L' + 'L'
                else:
                    res += 'L' * (j-i+1)
                last = 'L'
            # 找到R的情况
            elif dominoes[j] == 'R':
                if last == 'R':
                    res += (j-i+1) * 'R'
                else:
                    res += (j-i) * '.' + 'R'
                last = 'R'
            i = j + 1
        
        # 出来之后，处理右边界情况
        if last == 'R':
            res += 'R' * (len(dominoes)-len(res))
        else:
            res += '.' * (len(dominoes)-len(res))
        return res


36 / 36 test cases passed.
difficulty: medium
Runtime: 244 ms