[leetcode daily question] push domino

1 Bit and 2 Bit characters
difficulty ： secondary


I was wrong at first , The answer to the question is bfs To deal with it , Ideas as follows ：
When the time is 0 when , Some dominoes will be overturned by an initial left or right force . After that 1 Seconds later , These overturned dominoes exert a force on the dominoes around them . Specific performance: ：

• Dominoes overturned to the left , If it has an upright left next to the dominoes , A leftward force will be applied to the upright dominoes .
• Dominoes overturned to the right , If it has an upright right next to the dominoes , A rightward force will be applied to the upright dominoes .

Next, we need to analyze these 1 Second, the state of the stressed dominoes . If only one side of the force is applied , They fall to one side ; If you are subjected to two forces , Will maintain balance . In another 1 Seconds later , These newly overturned dominoes will exert force on other upright dominoes , It will not exert force on the dominoes that are overturning or have been overturned .
This idea is similar to breadth first search . We use one queue q Simulate the order of search ; Array time Record the time when the dominoes are overturned or determined not to be overturned , A overturned dominoes will not exert force on a dominoes that are overturning or have been overturned ; Array force Record the force on the dominoes , The dominoes will overturn only when subjected to a unilateral force .

The code is as follows ：

	public String pushDominoes(String dominoes) {
    
        int n = dominoes.length();
        Deque<Integer> queue = new ArrayDeque<Integer>();// Record the index of the dominoes to fall 
        int[] time = new int[n]; // Record the time when the dominoes of each index fell 
        Arrays.fill(time,-1); // Start all the time as -1, Indicates that the dominoes of the index have not fallen 
        List<Character>[] force = new List[n]; // Record the force of each index dominoes in different directions at a certain time 
        for(int i=0; i<n; i++){
     // Initialize the force list 
            force[i] = new ArrayList<Character>();
        }
        for(int i=0; i<n; i++){
    
            char f = dominoes.charAt(i);
            if( f != '.'){
     // Record the dominoes that will fall at the beginning 
                queue.offer(i);
                time[i]=0;
                force[i].add(f);
            }
        }
        char[] res = new char[n]; // Result array 
        Arrays.fill(res,'.');
        while( !queue.isEmpty()){
     // There are dominoes to fall 
            int i = queue.poll();
            if(force[i].size()==1){
     // When the dominoes are only subjected to a force in one direction at a certain time 
                char f = force[i].get(0); // Obtain the stress direction of the dominoes 
                res[i] = f; // Count into result array 
                int ni = f == 'L' ? i-1 : i+1; // View the adjacent dominoes under stress , Turn left to check the dominoes on the left , Reverse to the right to see the dominoes on the right 
                if( ni >= 0 && ni < n){
     // The adjacent dominoes index is legal 
                    int t = time[i];
                    if(time[ni] == -1){
     // The dominoes have not fallen 
                        queue.offer(ni); // At this time, the dominoes may also be subject to the force in the other direction , But it hasn't been detected yet , Therefore, it is necessary to determine whether the length of the force list is... Before counting into the result array 1, To ensure that the dominoes are only subjected to force in one direction 
                        time[ni] = t+1;
                        force[ni].add(f);
                    }else if(time[ni] == t+1){
     // At the same time, it is also subjected to a force in the other direction 
                        force[ni].add(f);
                    }
                }
            }
        }
        return new String(res);
    }

Execution results ： success