aboutsummaryrefslogtreecommitdiff
path: root/push_dominoes.c
diff options
context:
space:
mode:
Diffstat (limited to 'push_dominoes.c')
-rw-r--r--push_dominoes.c47
1 files changed, 47 insertions, 0 deletions
diff --git a/push_dominoes.c b/push_dominoes.c
new file mode 100644
index 0000000..9dbaa65
--- /dev/null
+++ b/push_dominoes.c
@@ -0,0 +1,47 @@
+// 838. Push Dominoes
+#include "leetcode.h"
+
+/*
+ * there are 'n' dominoes in a line, and we place each domino vertically
+ * upright. in the beginning, we simultaneously push some of the dominoes either
+ * to the left or to the right. after each second, each domino that is falling
+ * to the left pushes the adjacent domino on the left. similarly, the dominoes
+ * falling to the right push their adjacent dominoes standing on the right. when
+ * a vertical domino has dominoes falling on it from both sides, it stays still
+ * due to the balance of the forces. for the purpose of this question, we will
+ * consider that a falling domino expends no additional force to a falling or
+ * already fallen domino.
+ */
+
+char *pushDominoes(char *dominoes) {
+ int n = strlen(dominoes), right = -1;
+ for (int i = 0; i < n; ++i) {
+ if (dominoes[i] == 'L') {
+ if (right == -1) {
+ for (int j = i - 1; j >= 0 && dominoes[j] == '.'; --j)
+ dominoes[j] = 'L';
+ } else {
+ for (int j = right + 1, k = i - 1; j < k; ++j, --k) {
+ dominoes[j] = 'R';
+ dominoes[k] = 'L';
+ }
+ right = -1;
+ }
+ } else if (dominoes[i] == 'R') {
+ if (right != -1)
+ for (int j = right + 1; j < i; ++j)
+ dominoes[j] = 'R';
+ right = i;
+ }
+ }
+ if (right != -1)
+ for (int i = right + 1; i < n; ++i)
+ dominoes[i] = 'R';
+ return dominoes;
+}
+
+int main() {
+ char *d1 = "RR.L", *d2 = ".L.R...LR..L..";
+ printf("%s\n", pushDominoes(d1)); // expect: RR.L
+ printf("%s\n", pushDominoes(d2)); // expect: .L.R...LR..L..
+}