Leetcode838: push domino (medium)

Catalog

1. Title Description

2. Problem solving analysis

2.1 Topic meaning and example explanation

2.2 The main points of         

2.3 Algorithm ideas

3. Code implementation

---

1. Title Description

n A row of dominoes , Erect each domino vertically . At the beginning , At the same time, push some dominoes to the left or right .
Every second , The dominoes falling to the left will push the dominoes adjacent to the left . similarly , The dominoes on the right will also push the adjacent dominoes on the right .
If a vertically erected dominoes is falling on both sides at the same time , Because of the balance of forces , The dominoes remain the same .
As far as this is concerned , We would assume that a falling domino does not exert additional force on other falling or fallen dominoes .
Give you a string dominoes Indicates the initial state of this row of dominoes , among ：

dominoes[i] = 'L', It means the first one i A domino is pushed to the left ,
dominoes[i] = 'R', It means the first one i A domino is pushed to the right ,
dominoes[i] = '.', It means that the third party has not been promoted i Dominoes .
Returns a string representing the final state .

Example 1：
Input ：dominoes = "RR.L"
Output ："RR.L"
explain ： The first dominoes didn't put extra force on the second one .

Example 2：
Input ：dominoes = ".L.R...LR..L.."
Output ："LL.RR.LLRRLL.."
 
Tips ：
n == dominoes.length
1 <= n <= 10^5
dominoes[i] by 'L'、'R' or '.'

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/push-dominoes

2. Problem solving analysis

2.1 Topic meaning and example explanation

         Supplementary notes on the meaning of the title :

         The string of the final state is still in 'L','R','.' Express , They mean to fall to the left 、 Guide to the right and keep vertical . Note the subtle difference between this and which side is pushed in the initial state .

         In addition, in the Title Description “ As far as this is concerned , We would assume that a falling domino does not exert additional force on other falling or fallen dominoes .”... At first glance, this sentence may feel unintelligible , Let's look at it with examples , Refer to the following example 1 The explanation of .

        Example 1 The explanation of ：dominoes = "RR.L". The first 3 The left card is reversed to the right , The one on the right falls to the left . Because of the balance of pressure from the left and right , So it will remain the same . Sharp eyed friends may feel XOR , There are two cards upside down to the right on the left , There is only one card upside down to the left on the right , Is there more pressure to the right , It will lead to the second 3 Cards are reversed to the right ？ At this time, we can see the meaning of the above sentence . The first 1 Zhang fell to the right , The first 2 Zhang also fell to the right , According to the assumption of this sentence , The first 1 A card reversed to the right does not turn to the 2 A card reversed to the right exerts extra force , Therefore, there will be no 3 A card passes to pressure . therefore , The first 3 A card will not be affected by the 1 Effect of cards ！ therefore , The first 3 A card will remain stationary .

        Example 2 The explanation of ：dominoes = ".L.R...LR..L..". The first 1 Zhangshoudi 2 Zhang's influence is reversed to the left , The first 3 Zhang is not affected , The first 4 Zhang fell to the right, resulting in 5 Zhang also fell to the right , The first 8 Zhang inverted to the left, resulting in 7 Zhang also fell to the left , But the first 6 Zhang keeps his balance under the pressure of the left and right sides ,... The rest is analogical

2.2 The main points of         

         Based on the above analysis , We can see that the key point of this problem is that the initial force is '.' The card of . For each card ：

        case1: If its initial force is not '.', Then its final state is the same as the initial stress direction

        case2: If its initial force is '.', Look at the nearest non - '.' The card of ：

            case2-1: If the nearest non '.' The cards of are in the same force direction , Then the final state must be in this direction

            case2-2: If the nearest non '.' The cards are in different directions , But the left is inverted to the left , The right side is inverted to the right , The card will not be affected , So the final state is to remain upright

            case2-3: If the nearest non '.' The cards are in different directions , And the left side is inverted to the right , The right side is inverted to the left , Its final state is not '.' The distance of the card ： If the distance between two sides is equal, keep it upright , If you don't wait , It is the same as the force direction of the nearest one . 

2.3 Algorithm ideas

         Traverse the entire card sequence from beginning to end , Determine that each is composed of two initial forces '.' The interval separated by cards , Then, according to the above rules, determine the initial force of each piece in the interval as '.' The initial state of a card .

        use begin and end Respectively represent the initial force on the left card of each interval ,end Indicates the initial stress of the right card , You must also remember the corresponding card serial number for calculating the distance .

        Because it traverses from left to right , therefore begin Is initialized to 'L'. Search for the first non '.' The card of is the first interval end. After each interval is processed ,end Assign to begin Then continue to search for the next end... After traversing all the cards, you will finally end The assignment is 'R', For the processing of the last interval -- In this way, it is convenient to package the process of determining the final state in the interval into a function to realize the regularization process .

3. Code implementation

class Solution:
    def pushDominoes(self, dominoes: str) -> str:
        d_list = list(dominoes)
        print(d_list)
        begin = tuple(('L', -1))
        end   = None

        def finalState(begin,end):
            print('finalState: ',begin,end)
            if end[0] == begin[0]:
                for k in range(begin[1]+1,end[1]):
                    d_list[k] = begin[0]
            elif begin[0] == 'R' and end[0] == 'L':
                for k in range(begin[1]+1,end[1]):
                    if (k-begin[1]) < (end[1]-k):
                        d_list[k] = 'R'
                    elif (k-begin[1]) > (end[1]-k):
                        d_list[k] = 'L'
                    # else: keep unchanged.                            
            # else: keep unchanged.            
        
        for k in range(len(d_list)):
            if d_list[k] != '.':
                print(k,d_list)
                end = tuple((d_list[k], k))
                # Decide the final state of the segment between the current begin and end
                finalState(begin,end)
                begin = end
        if begin[1] < len(d_list) - 1:
            end = ('R', len(d_list))
            finalState(begin,end)

        return ''.join(d_list)            
            
if __name__ == '__main__':        
    
    sln = Solution()

    dominoes = "RR.L"
    print(sln.pushDominoes(dominoes))                 
                
    dominoes = ".L.R...LR..L.."
    print(sln.pushDominoes(dominoes))