### 题目描述 n 张多米诺骨牌排成一行，将每张多米诺骨牌垂直竖立。在开始时，同时把一些多米诺骨牌向左或向右推。 每过一秒，倒向左边的多米诺骨牌会推动其左侧相邻的多米诺骨牌。同样地，倒向右边的多米诺骨牌也会推动竖立在其右侧的相邻多米诺骨牌。 如果一张垂直竖立的多米诺骨牌的两侧同时有多米诺骨牌倒下时，由于受力平衡， 该骨牌仍然保持不变。 就这个问题而言，我们会认为一张正在倒下的多米诺骨牌不会对其它正在倒下或已经倒下的多米诺骨牌施加额外的力。 给你一个字符串 dominoes 表示这一行多米诺骨牌的初始状态，其中： - dominoes[i] = 'L'，表示第 i 张多米诺骨牌被推向左侧， - dominoes[i] = 'R'，表示第 i 张多米诺骨牌被推向右侧， - dominoes[i] = '.'，表示没有推动第 i 张多米诺骨牌。 返回表示最终状态的字符串。 ### 输入输出 #### 示例1 ``` 输入：dominoes = "RR.L" 输出："RR.L" 解释：第一张多米诺骨牌没有给第二张施加额外的力。 ``` #### 示例2 ``` 输入：dominoes = ".L.R...LR..L.." 输出："LL.RR.LLRRLL.." ``` ### 题目解答 #### 思路 - 采用模拟的方式，每次模拟1秒钟骨牌的情况，直到骨牌的状态不再发生变化，那么此时就是骨牌最终的状态。 - 对于每1秒钟的状态变化，分成如下情况： 1. 对于状态L的骨牌，如果其左侧为直立骨牌，同时再往左不是状态R的骨牌。那么这张牌就可以将左侧直立牌放倒，将其置为L。 2. 对于状态R的骨牌，如果其右侧是直立骨牌，同时再往右不是状态L的骨牌。那么这张牌就可以将右侧直立骨牌放倒，将其置为R。 需要注意的是，在代码实现状态变化的时候，copy一个数组出来，再进行变化，避免从左到右遍历的时候，出现连锁的变化情况。 **算法复杂度** 时间复杂度：模拟每次推进1秒钟，如果为R.....这种情况，需要模拟数组长度次数，因此复杂度为O(N) 空间复杂度：需要开辟与骨牌情况相同的数组记录情况，一个骨牌数组，一个tmp数组，空间复杂度O(N) #### 代码实现 ```java class Solution { public String pushDominoes(String dominoes) { char[] cc = dominoes.toCharArray(); char[] tmp = new char[cc.length]; System.arraycopy(cc, 0, tmp, 0, cc.length); int change = 0; do{ change=0; for(int i=0;i<cc.length;i++){ if(cc[i]=='L' && i>=1 && cc[i-1] == '.'){ if(i<2 || cc[i-2]!='R'){ tmp[i-1] = 'L'; change++; } } else if(cc[i]=='R' && i<cc.length-1 && cc[i+1] == '.'){ if(i>=cc.length-2 || cc[i+2]!='L'){ tmp[i+1] = 'R'; change++; } } } System.arraycopy(tmp, 0, cc, 0, cc.length); System.out.println(new String(cc)); }while(change > 0); return new String(cc); } } ``` 最后编辑：2024年04月23日 ©著作权归作者所有 赞 0 分享
最新回复