Massive Algorithms: LeetCode 838

LeetCode 838 - Push Dominoes

https://leetcode.com/problems/push-dominoes/description/

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 purposes of this question, we will consider that a falling domino expends no additional force to a falling or already fallen domino.

Given a string "S" representing the initial state. S[i] = 'L', if the i-th domino has been pushed to the left; S[i] = 'R', if the i-th domino has been pushed to the right; S[i] = '.', if the i-th domino has not been pushed.

Return a string representing the final state.

Example 1:

Input: ".L.R...LR..L.."
Output: "LL.RR.LLRRLL.."

Example 2:

Input: "RR.L"
Output: "RR.L"
Explanation: The first domino expends no additional force on the second domino.

Note:

0 <= N <= 10^5
String dominoes contains only 'L', 'R' and '.'

Approach #1: Adjacent Symbols

Between every group of vertical dominoes ('.'), we have up to two non-vertical dominoes bordering this group. Since additional dominoes outside this group do not affect the outcome, we can analyze these situations individually: there are 9 of them (as the border could be empty). Actually, if we border the dominoes by 'L' and 'R', there are only 4 cases. We'll write new letters between these symbols depending on each case.

Algorithm

Continuing our explanation, we analyze cases:

If we have say "A....B", where A = B, then we should write "AAAAAA".
If we have "R....L", then we will write "RRRLLL", or "RRR.LLL" if we have an odd number of dots. If the initial symbols are at positions i and j, we can check our distance k-i and j-k to decide at position k whether to write 'L', 'R', or '.'.
(If we have "L....R" we don't do anything. We can skip this case.)

public String pushDominoes(String dominoes) {
int N = dominoes.length();
int[] indexes = new int[N+2];
char[] symbols = new char[N+2];
int len = 1;
indexes[0] = -1;
symbols[0] = 'L';

for (int i = 0; i < N; ++i)
if (dominoes.charAt(i) != '.') {
indexes[len] = i;
symbols[len++] = dominoes.charAt(i);
}

indexes[len] = N;
symbols[len++] = 'R';

char[] ans = dominoes.toCharArray();
for (int index = 0; index < len - 1; ++index) {
int i = indexes[index], j = indexes[index+1];
char x = symbols[index], y = symbols[index+1];
char write;
if (x == y) {
for (int k = i+1; k < j; ++k)
ans[k] = x;
} else if (x > y) { // RL
for (int k = i+1; k < j; ++k)
ans[k] = k-i == j-k ? '.' : k-i < j-k ? 'R' : 'L';
}
}

return String.valueOf(ans);
}

法2 计算受力，走两遍
Approach #2: Calculate Force

We can calculate the net force applied on every domino. The forces we care about are how close a domino is to a leftward 'R', and to a rightward 'L': the closer we are, the stronger the force.

Algorithm

Scanning from left to right, our force decays by 1 every iteration, and resets to N if we meet an 'R', so that force[i] is higher (than force[j]) if and only if dominoes[i] is closer (looking leftward) to 'R' (than dominoes[j]).

Similarly, scanning from right to left, we can find the force going rightward (closeness to 'L').

For some domino answer[i], if the forces are equal, then the answer is '.'. Otherwise, the answer is implied by whichever force is stronger.

public String pushDominoes(String S) {
char[] A = S.toCharArray();
int N = A.length;
int[] forces = new int[N];

int force = 0;
for (int i = 0; i < N; ++i) {
if (A[i] == 'R') force = N;
else if (A[i] == 'L') force = 0;
else force = Math.max(force - 1, 0);
forces[i] += force;
}

force = 0;
for (int i = N-1; i >= 0; --i) {
if (A[i] == 'L') force = N;
else if (A[i] == 'R') force = 0;
else force = Math.max(force - 1, 0);
forces[i] -= force;
}

StringBuilder ans = new StringBuilder();
for (int f: forces)
ans.append(f > 0 ? 'R' : f < 0 ? 'L' : 'V');
return ans.toString();
}
X.
http://storypku.com/2018/06/leetcode-question-838-push-dominoes/
https://www.cnblogs.com/seyjs/p/9071067.html

本题题目中有一点要求很关键，“we will consider that a falling domino expends no additional force to a falling or already fallen domino.”，正好对应题目中的例子2，要好好理解一下。因为输入的最大dominoes是10^5,所以要考虑性能问题。dominoes有三种状态:'R','L','.'。在最终状态里面，R和L是不会变的，只有'.'的状态可能会变成三种状态的任意一种。我的思路是把所有连续的'.'当做一个子序列，然后判断这个子序列左边和右边的dominoes是R还是L，这里分这么几种情况：

a.左右的dominoes方向相同，那么子序列所有的'.'的方向和左右方向相同；

b.左边的dominoes向右，右边的dominoes向左，如下图，那么要考虑子序列长度是奇偶性来决定最中间的'.'的取值。如下图，

c.子序列出现要头尾要单独考虑；

d.左边的dominoes向左，右边的dominoes向右，那么子序列所有的'.'的方向保持不变，还是为'.'；

https://buptwc.com/2018/05/22/Leetcode-838-Push-Dominoes/

    def pushDominoes(self, dominoes):
        """
        :type dominoes: str
        :rtype: str
        """
        res = ''
        i = 0
        # 上一个出现的关键点用last表示，初始为None，处理左边界情况
        last = None
        while i < len(dominoes):
            j = i
            # 遍历到'.'就不管，一直到找到一个'R或L'为止
            while j+1 < len(dominoes) and dominoes[j] == '.': j += 1 
            # 找到L的情况
            if dominoes[j] == 'L':
                if last == 'R':
                    res += (j-i)/2 * 'R' + (j-i)%2 * '.' + (j-i)/2 * 'L' + 'L'
                else:
                    res += 'L' * (j-i+1)
                last = 'L'
            # 找到R的情况
            elif dominoes[j] == 'R':
                if last == 'R':
                    res += (j-i+1) * 'R'
                else:
                    res += (j-i) * '.' + 'R'
                last = 'R'
            i = j + 1
        
        # 出来之后，处理右边界情况
        if last == 'R':
            res += 'R' * (len(dominoes)-len(res))
        else:
            res += '.' * (len(dominoes)-len(res))
        return res

X. Two Pointer
https://blog.csdn.net/fuxuemingzhu/article/details/82714928
如果理解了一个推倒了的牌只能对另一个站着的牌起作用这句话那么基本上就能做出来这个题了，否则是做不出来的。

我们对这个题的理解应该是找出最近的两个被推倒了的牌，然后判断这两个牌是什么样子的即可，不用考虑这个区间以外的牌，因为这两张牌被推倒了，而这个区间外的其他牌不会对推倒了的牌起作用。所以使用双指针的方式解决。

所以在两个被推倒了的区间里：

'R......R' => 'RRRRRRRR'
'R......L' => 'RRRRLLLL' or 'RRRR.LLLL'
'L......R' => 'L......R'
'L......L' => 'LLLLLLLL'
1
2
3
4
使用双指针即可解决掉。
https://leetcode.com/problems/push-dominoes/discuss/132332/C++JavaPython-Two-Pointers

Whether be pushed or not, depend on the shortest distance to 'L' and 'R'.
Also the direction matters.
Base on this idea, you can do the same thing inspired by this problem.
https://leetcode.com/problems/shortest-distance-to-a-character/discuss/125788/

Here is another idea that focus on 'L' and 'R'.
'R......R' => 'RRRRRRRR'
'R......L' => 'RRRRLLLL' or 'RRRR.LLLL'
'L......R' => 'L......R'
'L......L' => 'LLLLLLLL'

    public String pushDominoes(String d) {
        d = 'L' + d + 'R';
        StringBuilder res = new StringBuilder();
        for (int i = 0, j = 1; j < d.length(); ++j) {
            if (d.charAt(j) == '.') continue;
            int middle = j - i - 1;
            if (i > 0) res.append(d.charAt(i));
            if (d.charAt(i) == d.charAt(j))
                for (int k = 0; k < middle; k++) res.append(d.charAt(i));
            else if (d.charAt(i) == 'L' && d.charAt(j) == 'R')
                for (int k = 0; k < middle; k++) res.append('.');
            else {
                for (int k = 0; k < middle / 2; k++) res.append('R');
                if (middle % 2 == 1) res.append('.');
                for (int k = 0; k < middle / 2; k++) res.append('L');
            }
            i = j;
        }
        return res.toString();
    }

https://leetcode.com/problems/push-dominoes/discuss/132482/Java-one-pass-in-place-13ms

 public String pushDominoes(String dominoes) {
        char[] a = dominoes.toCharArray();
        int L = -1, R = -1;//positions of last seen L and R
        for (int i = 0; i <= dominoes.length(); i++)
            if (i == a.length || a[i] == 'R') {
                if (R > L)//R..R, turn all to R
                    while (R < i)
                        a[R++] = 'R';
                R = i;
            } else if (a[i] == 'L')
                if (L > R || (R == -1 && L == -1))//L..L, turn all to L
                    while (++L < i)
                        a[L] = 'L';
                else { //R...L
                    L = i;
                    int lo = R + 1, hi = L - 1;
                    while (lo < hi) { //one in the middle stays '.'
                        a[lo++] = 'R';
                        a[hi--] = 'L';
                    }
                }
        return new String(a);
    }

public String pushDominoes(String input) {

char[] dominoes = input.toCharArray();

ArrayDeque<Character> stack = new ArrayDeque<>();

List<Character> result = new ArrayList<>(dominoes.length);

for (int i = 0; i < dominoes.length; i++) {

// improve: save space, store index in the stack not element value

Character ch = dominoes[i];

if (ch == '.') {

stack.add(ch);

} else if (ch == 'R') {

// ..R or R or R ... (R)

// .. L .. R already handled L

if (!stack.isEmpty()) {

if (stack.peekFirst() == 'R') {

for (int k = 0; k < stack.size(); k++) {

result.add('R');

}

stack.clear();

} else {

while (!stack.isEmpty()) {

result.add(stack.removeFirst());

}

stack.add(ch);

} else {

// ch is L

// case in stack: ...L or R .. L or L

// LL or L..L not exist, first L already handled

if (!stack.isEmpty()) {

if (stack.peekFirst() == '.') {

for (int k = 0; k < stack.size(); k++) {

result.add('L');

}

stack.clear();

} else {

// case R .. L R ... L

int size = stack.size() - 1;

result.add('R');

for (int k = 0; k < size / 2; k++) {

result.add('R');

}

if (size % 2 == 1) {

result.add('.');

}

for (int k = 0; k < size / 2; k++) {

result.add('L');

}

stack.clear();

}

// add ch

result.add('L');

}

if (!stack.isEmpty()) {

// remaining in stack: .... or R ..

if (stack.peekFirst() == '.') {

for (int k = 0; k < stack.size(); k++) {

result.add('.');

}

} else {

for (int k = 0; k < stack.size(); k++) {

result.add('R');

}

return result.stream().map(String::valueOf).collect(Collectors.joining());

}

https://www.acwing.com/solution/LeetCode/content/757/
遍历一次字符串，如果当前字符是’.’，那么跳过，如果当前字符是’L’，判断上一次字符last是什么，如果last是’L’，那么就把last到当前字符位置的字符全部赋值为’L’，如果last是’R’，那么前面一半位置赋值为’R’,后面一半位置赋值为’L’，中间赋值为’.’，最后更新last为当前的字符。当前字符是’R’时，如果last是’R’,那么把last到当前字符位置全部赋值为’R’, 如果last是’L’，那么则不做处理（因为last向左倒，当前向右倒），最后更新last的字符和位置。

时间复杂度分析：需要扫描一遍数组，复杂度为O(n)O(n)

X. BFS, Queue
https://leetcode.com/problems/push-dominoes/discuss/132929/Naive-BFS-Easy-to-understand-and-could-be-used-as-first-solution

    public String pushDominoes(String dominoes) {
        char[] arr = new char[dominoes.length()];
        int[] left = new int[dominoes.length()];
        int[] right = new int[dominoes.length()];
        Queue<Integer> leftQ = new LinkedList<>();
        Queue<Integer> rightQ = new LinkedList<>();
        Arrays.fill(left, Integer.MAX_VALUE);
        Arrays.fill(right, Integer.MAX_VALUE);
        for (int i = 0; i < dominoes.length(); i++) {
            if (dominoes.charAt(i) == 'L') {
                leftQ.offer(i);
                left[i] = 0;
            }
            if (dominoes.charAt(i) == 'R') {
                rightQ.offer(i);
                right[i] = 0;
            }
        }
        int step = 0;
        while (leftQ.size() > 0 || rightQ.size() > 0) {
            step++;
            int leftSize = leftQ.size();
            while (leftSize > 0) {
                leftSize--;
                int pos = leftQ.poll();
                if (pos > 0 && left[pos - 1] == Integer.MAX_VALUE && dominoes.charAt(pos - 1) != 'R') {
                    leftQ.offer(pos - 1);
                    left[pos - 1] = step;
                }
            }
            int rightSize = rightQ.size();
            while (rightSize > 0) {
                rightSize--;
                int pos = rightQ.poll();
                if (pos + 1< dominoes.length() && right[pos + 1] == Integer.MAX_VALUE && dominoes.charAt(pos + 1) != 'L') {
                    rightQ.offer(pos + 1);
                    right[pos + 1] = step;
                }
            }
        }
        for (int i = 0; i < dominoes.length(); i++) {
            if (left[i] - right[i] == 0) {
                arr[i] = '.';
            }
            else if (left[i] - right[i] > 0) {
                arr[i] = 'R';
            }
            else {
                arr[i] = 'L';
            }
        }
        return new String(arr);
    }

https://code.dennyzhang.com/push-dominoes

LeetCode 838 - Push Dominoes

Labels

Popular Posts