What is the key approach to solving the Push Dominoes problem?

The key approach is to simulate the falling dominoes using dynamic programming, where each domino's state is updated based on its neighbors, and two pointers help optimize the solution.

How can dynamic programming be applied in this problem?

Dynamic programming is used to track the forces acting on each domino, allowing for efficient state transitions as dominoes fall over time.

What is the time complexity of the Push Dominoes problem?

The time complexity is typically O(N), where N is the number of dominoes, as the solution requires a single pass through the dominoes to simulate the falling process.

Can you explain the two-pointer approach for Push Dominoes?

The two-pointer approach processes the dominoes from both directions, updating their states efficiently and ensuring an optimal solution in linear time.

What are some common pitfalls in solving the Push Dominoes problem?

Common pitfalls include incorrect handling of the balance between forces acting on a domino and failing to optimize the solution for time complexity.

#838

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

推多米诺

n 张多米诺骨牌排成一行，将每张多米诺骨牌垂直竖立。在开始时，同时把一些多米诺骨牌向左或向右推。每过一秒，倒向左边的多米诺骨牌会推动其左侧相邻的多米诺骨牌。同样地，倒向右边的多米诺骨牌也会推动竖立在其右侧的相邻多米诺骨牌。如果一张垂直竖立的多米诺骨牌的两侧同时有多米诺骨牌倒下时，由于受力平衡， …

双指针字符串动态规划

题目描述

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' 或 '.'

lightbulb

解题思路

方法一：多源  BFS

把所有初始受到推力的骨牌（L  或  R）视作源点，它们会同时向外扩散各自的力。用队列按时间层级（0, 1, 2 …）进行  BFS：

我们定义 $\text{time[i]}$   记录第  i  张骨牌第一次受力的时刻，-1  表示尚未受力，定义 $\text{force[i]}$   是一个长度可变的列表，存放该骨牌在同一时刻收到的方向（'L'、'R'）。初始时把所有  L/R  的下标压入队列，并将它们的时间置  0。

当弹出下标  i 时，若   $\text{force[i]}$   只有一个方向，骨牌就会倒向该方向   $f$ 。设下一张骨牌下标为

j = \begin{cases} i - 1, & f = L,\\ i + 1, & f = R. \end{cases}

若   $0 \leq j < n$ ：

若 $\text{time[j]}=-1$ ，说明  j  从未受力，记录 $\text{time[j]}=\text{time[i]}+1$ 并入队，同时把   $f$ 写入   $\text{force[j]}$ 。
若 $\text{time[j]}=\text{time[i]}+1$ ，说明它在同一“下一刻”已受过另一股力，此时只把   $f$ 追加到   $\text{force[j]}$ ，形成对冲；后续因  len(force[j])==2，它将保持竖直。

队列清空后，所有   $\text{force[i]}$   长度为  1  的位置倒向对应方向；长度为  2  的位置保持 .。最终将字符数组拼接为答案。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是骨牌的数量。

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

class Solution:
    def pushDominoes(self, dominoes: str) -> str:
        n = len(dominoes)
        q = deque()
        time = [-1] * n
        force = defaultdict(list)
        for i, f in enumerate(dominoes):
            if f != '.':
                q.append(i)
                time[i] = 0
                force[i].append(f)
        ans = ['.'] * n
        while q:
            i = q.popleft()
            if len(force[i]) == 1:
                ans[i] = f = force[i][0]
                j = i - 1 if f == 'L' else i + 1
                if 0 <= j < n:
                    t = time[i]
                    if time[j] == -1:
                        q.append(j)
                        time[j] = t + 1
                        force[j].append(f)
                    elif time[j] == t + 1:
                        force[j].append(f)
        return ''.join(ans)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	O(N)

psychology

面试官常问的追问

外企场景

question_mark
Look for understanding of state transitions in dynamic systems.
question_mark
Check how well the candidate can optimize a problem involving multiple iterations over a large dataset.
question_mark
Evaluate the candidate's ability to apply dynamic programming or two pointers in a string manipulation context.

warning

常见陷阱

外企场景

error
Misunderstanding the force balance when both directions act on the same domino, leading to incorrect final states.
error
Failing to optimize the algorithm, leading to unnecessary time complexity when simulating the falling process.
error
Incorrect handling of edge cases like dominoes with no initial movement (all '.' characters).

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider variations where dominoes can be pushed in a random sequence instead of initially falling left or right.
arrow_right_alt
Simulate the scenario with additional constraints such as multiple groups of falling dominoes.
arrow_right_alt
Implement the solution with a different space complexity requirement, optimizing the algorithm further.

help

常见问题

外企场景

继续练习

#647 回文子串 #1048 最长字符串链 #1147 段式回文

推多米诺

题目描述

解题思路

方法一：多源 BFS

复杂度分析

面试官常问的追问

常见陷阱

进阶变体

常见问题

What is the key approach to solving the Push Dominoes problem?

How can dynamic programming be applied in this problem?

What is the time complexity of the Push Dominoes problem?

Can you explain the two-pointer approach for Push Dominoes?

What are some common pitfalls in solving the Push Dominoes problem?

方法一：多源  BFS