-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathPushDominoes.java
More file actions
111 lines (94 loc) · 3.02 KB
/
PushDominoes.java
File metadata and controls
111 lines (94 loc) · 3.02 KB
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
package com.leetcode_new.editor.cn;
//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.."
//
//
//
//
// 提示：
//
//
// n == dominoes.length
// 1 <= n <= 10⁵
// dominoes[i] 为 'L'、'R' 或 '.'
//
// Related Topics 双指针 字符串 动态规划 👍 242 👎 0
/**
* 838 推多米诺
* @date 2022-02-21 23:19:28
* @author shang.liang
*/
public class PushDominoes{
public static void main(String[] args){
Solution soution = new PushDominoes().new Solution();
}
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public String pushDominoes(String dominoes) {
dominoes = "L" + dominoes + "R";
StringBuilder res = new StringBuilder();
int l = 0;
for (int r = 1; r < dominoes.length(); r++) {
if (dominoes.charAt(r) == '.') {
continue;
}
int mid = r - l - 1;
if (l != 0) {
res.append(dominoes.charAt(l));
}
if (dominoes.charAt(r) == dominoes.charAt(l)) {
for (int i = 0; i < mid; i++) {
res.append(dominoes.charAt(r));
}
} else if (dominoes.charAt(l) == 'L' && dominoes.charAt(r) == 'R') {
for (int i = 0; i < mid; i++) {
res.append(".");
}
} else {
for (int i = 0; i < mid / 2; i++) {
res.append('R');
}
if (mid % 2 == 1) {
res.append(".");
}
for (int i = 0; i < mid / 2; i++) {
res.append("L");
}
}
l = r;
}
return res.toString();
}
}
//leetcode submit region end(Prohibit modification and deletion)
}