diff options
-rw-r--r-- | push_dominoes.c | 47 | ||||
-rw-r--r-- | push_dominoes.py | 32 |
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..")) |