Deduct daily question 838 of a certain day

838. Push domino

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 .

harm Want to traverse with double pointers Then I thought for a long time and didn't write it out hhh

Refer to the idea of a boss in the comment area ：

1、LL All between L;
2、RR All between R;
3、LR unchanged ,RL In the middle ;
4、 There is one on the far left by default L, There is one on the far right by default R, It's easy to handle

This idea is much clearer in an instant

public static String pushDominoes(String dominoes) {
    
        //1、LL All between L;2、RR All between R;3、LR unchanged ,RL In the middle ;5、 There is one on the far left by default L, There is one on the far right by default R, It's easy to handle 
        dominoes = new StringBuilder("L").append(dominoes).append("R").toString();
        StringBuilder ans = new StringBuilder();
        // Initialize left and right pointers 
        int leftIndex = 0, rightIndex = 1;
        while (rightIndex < dominoes.length()) {
    
            while (rightIndex < dominoes.length() && dominoes.charAt(rightIndex) == '.') {
    
                rightIndex++;
            }
            char leftChar = dominoes.charAt(leftIndex);
            char rightChar = dominoes.charAt(rightIndex);
            if (leftChar == rightChar) {
    
                for (int i = leftIndex+1 ; i < rightIndex; i++) {
    
                    ans.append(leftChar);
                }
            } else if (leftChar == 'R' && rightChar == 'L') {
    
                 //  here as Calculate how many... Between the two  . 
                int as = rightIndex - leftIndex - 1; 
                for (int i = 0; i < as / 2 ; i++) {
    
                    ans.append('R');
                }
                //  If at present '.' If the number of is odd   We also need to add a middle vertical dominoes   namely R...L -> RR.LL
                if (as % 2 == 1) {
    
                    ans.append('.');
                }
                for (int i = 0; i < as / 2; i++) {
    
                    ans.append('L');
                }
            } else if(leftChar == 'L'&& rightChar == 'R'){
    
                for (int i = leftIndex + 1; i < rightIndex; i++) {
    
                    ans.append('.');
                }
            }
            // Take this time rightIndex Point to the char Add to ans in 
            ans.append(rightChar);
            // Update the position of the left and right pointers , Make it the next pair LR/RL/LL/RR  Move 
            leftIndex = rightIndex;
            rightIndex++;
        }
        // Remove the one added on the far right  R
        return ans.substring(0,ans.length() - 1).toString();
    }

See that many bosses in the comment area use bitwise operators , However, I don't seem to have used it … Make up for it

notes

The operator	Explain （ Arithmetic shift left and arithmetic shift right are mainly used to multiply signed numbers 、 halve ）
number << i	amount to number * 2i , Move arithmetic left AKA Logic shift left , High overflow , Low complement 0
number >> i	amount to number / 2i , Count right , Low overflow , High compensation 0
number >>> i	To move right without a sign , It's also called logical shift right , If the number is positive , Then the high position will be supplemented 0, And if the number is negative , After moving right, the high position will be filled as well 0

example



Picture source