aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--push_dominoes.c47
-rw-r--r--push_dominoes.py32
2 files changed, 79 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..
+}
diff --git a/push_dominoes.py b/push_dominoes.py
new file mode 100644
index 0000000..a33dd56
--- /dev/null
+++ b/push_dominoes.py
@@ -0,0 +1,32 @@
+# 838. Push Dominoes
+
+"""
+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.
+"""
+
+
+class Solution(object):
+ def pushDominoes(self, dominoes):
+ """
+ :type dominoes: str
+ :rtype: str
+ """
+ while "R." in dominoes or ".L" in dominoes:
+ dominoes = (
+ dominoes.replace("R.L", "xxx").replace(".L", "LL").replace("R.", "RR")
+ )
+ return dominoes.replace("xxx", "R.L")
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.pushDominoes(dominoes="RR.L"))
+ print(obj.pushDominoes(dominoes=".L.R...LR..L.."))