題目資訊

題目編號: 838
題目連結: Push Dominoes
主題: Two Pointers, String, Dynamic Programming

題目敘述

有 n 個骨牌排成一列，我們將每個骨牌豎直放置。在開始時，我們同時推動一些骨牌，或向左，或向右。

每秒後，每個向左倒的骨牌都會推倒左邊相鄰的骨牌。類似地，向右倒的骨牌則會推倒右邊相鄰的骨牌。

當一個豎直的骨牌受到來自兩邊的倒下力量時，由於力的平衡，它保持不動。

就這個問題而言，我們將認為一個倒下的骨牌對另一個倒下或已倒下的骨牌不再施加額外的力量。

給定一個代表初始狀態的字串 dominoes，其中：

dominoes[i] = 'L'，如果第 $i$ 個骨牌被推向左，
dominoes[i] = 'R'，如果第 $i$ 個骨牌被推向右，
dominoes[i] = '.'，如果第 $i$ 個骨牌未被推。

返回 代表最終狀態的字串。

範例 1:

輸入: dominoes = “RR.L”
輸出: “RR.L”
解釋: 第一個骨牌對第二個骨牌不施加額外的力量。

範例 2:

domino image
輸入: dominoes = “.L.R…LR..L..”
輸出: “LL.RR.LLRRLL..”

約束條件:

$n == \text{dominoes.length}$
$1 \leq n \leq 10^5$
dominoes[i] 是 'L'、'R' 或 '.' 中的其中一個。

直覺

這個問題本質上是在模擬骨牌根據初始推動情況傾倒的過程，推動可以是向左 (‘L’) 或向右 (‘R’)。每個骨牌要麼在兩邊施加的力相等時保持原位，要麼朝著較強的一側繼續傾倒。通過理解並模擬這些推動，並允許後續的連鎖反應，我們可以預測骨牌的最終狀態。考慮到限制，一個有效的解法需要系統地遍歷骨牌序列，捕捉從左到右的’L’和’R’骨牌之間的相互作用，同時避免重複處理相同的條件。

解法

初始化：在dominoes字符串的開頭加上’L’，尾部加上’R’，以簡化邊界條件，這樣可以確保每個骨牌都會在兩端受到明確的影響力。這使得我們的模擬在考慮轉變時不需對序列的開始和結尾進行特殊處理。
狀態跟蹤：使用兩個指針，lastIdx記錄在遍歷骨牌字符串時最近的’L’或’R’的位置，以索引i從左到右進行遍歷。
模擬過程：
- 當我們遍歷字符串中的每個字元時:
  - 如果在位置i遇到了’L’：
    - 檢查最近的影響骨牌是否是’R’。如果是，則在lastIdx + 1到i - 1之間的空隙中填入’R’和’L’，向內推進直到它們碰面。
    - 如果最近的影響骨牌也是’L’（或沒有影響的’R’），則從lastIdx + 1到i填入’L’，因為沒有相反的力量。
  - 如果遇到’R’，且最近的影響骨牌是’R’，則在lastIdx + 1到i之間完全填入’R’，因為沒有相反的左向力干擾。
完成：繼續這個過程，直到到達人為附加的’R’。根據骨牌效應規則應用所有的力量後，除去附加的端部保護字符。
結果構建：構建並返回最終的骨牌排列，排除為簡化邊界條件而添加的額外’L’和’R’。

這個方法保證了所有的相互作用都在一次遍歷中處理，時間複雜度為$O(n)$，這是有效的，符合問題的限制條件。

程式碼

C++

class Solution {
public:
    string pushDominoes(string dominoes) {
        // 在開頭加入 'L' 以及結尾加入 'R' 以處理邊界情況
        dominoes = 'L' + dominoes + 'R';

        int lastIdx = 0;  // 'L' 或 'R' 的最後一個位置
        int len = dominoes.size();

        for (int i = 1; i < len; ++i) {
            char current = dominoes[i];
            
            if (current == 'L') {
                if (dominoes[lastIdx] == 'R') {
                    // 之前有 'R' 現在出現 'L'，所以向內推
                    int low = lastIdx + 1, high = i - 1;
                    while (low < high) {
                        dominoes[low++] = 'R';
                        dominoes[high--] = 'L';
                    }
                } else {
                    // 將從最後一個 'L' 或開頭到當前 'L' 之間的所有骨牌填入 'L'
                    fill(dominoes.begin() + lastIdx + 1, dominoes.begin() + i, 'L');
                }
                lastIdx = i;
            } else if (current == 'R') {
                if (dominoes[lastIdx] == 'R') {
                    // 將從最後一個 'R' 到當前 'R' 之間的所有骨牌填入 'R'
                    fill(dominoes.begin() + lastIdx + 1, dominoes.begin() + i, 'R');
                }
                lastIdx = i;
            }
        }

        // 返回去掉添加的 'L' 和 'R' 的結果
        return dominoes.substr(1, len - 2);
    }
};

Python

class Solution:
    def pushDominoes(self, dominoes: str) -> str:
        # 在開頭添加 'L' 和結尾添加 'R' 以處理邊緣情況
        dominoes = 'L' + dominoes + 'R'

        lastIdx = 0  # 最近的 'L' 或 'R' 的位置
        len_dominoes = len(dominoes)

        for i in range(1, len_dominoes):
            current = dominoes[i]
            
            if current == 'L':
                if dominoes[lastIdx] == 'R':
                    # 前面有 'R' 現在有 'L'，所以向內推
                    low = lastIdx + 1
                    high = i - 1
                    while low < high:
                        dominoes = dominoes[:low] + 'R' + dominoes[low + 1:]
                        dominoes = dominoes[:high] + 'L' + dominoes[high + 1:]
                        low += 1
                        high -= 1
                else:
                    # 將從最後一個 'L' 或開始到當前 'L' 之間的所有多米諾改為 'L'
                    dominoes = dominoes[:lastIdx + 1] + 'L' * (i - lastIdx - 1) + dominoes[i:]
                lastIdx = i
            elif current == 'R':
                if dominoes[lastIdx] == 'R':
                    # 將從最後一個 'R' 到當前 'R' 之間的所有多米諾改為 'R'
                    dominoes = dominoes[:lastIdx + 1] + 'R' * (i - lastIdx - 1) + dominoes[i:]
                lastIdx = i

        # 返回結果，去掉添加的 'L' 和 'R'
        return dominoes[1:len_dominoes - 1]

複雜度分析

時間複雜度: $O(n)$
該演算法對包含多米諾骨牌的字符串進行單次通過處理，精確檢查每一個字符。這通過一個從字符串開頭遍歷到結尾的迴圈實現，導致相對於字符串長度 $n$ 的線性時間複雜度。在迴圈內，操作如設置字符串內的字符或用特定字符填充範圍都是常數時間操作，這樣總體複雜度為 $O(n)$。
空間複雜度: $O(n)$
空間複雜度由用於保存經修改的多米諾骨牌字符串的存儲需求所驅動。為了處理邊界情況，演算法將原始字符串擴展了兩個字符（在開頭添加 ‘L’，在結尾添加 ‘R’）。因此，需要的空間與 $n + 2$ 成正比，而在考慮漸進複雜度時簡化為 $O(n)$。這一額外空間使用是最小的，並且隨著輸入大小線性擴展。

CS Note
En

Leetcode 838. Push Dominoes

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析