如何將n個數字相加到數組中的給定範圍，並在O（n）時間內顛倒數組中的範圍？

Question

假設我們有一個數組L [] = {4,1,2,6}。我們需要做的是採取的線S由字符A，R，M作爲輸入，並應用如下算法：

for i from 1 to N do 

    if ith letter of S is 'R' 
     reverse L[i...N] 
    else if ith letter of S is 'A' 
     add A to all numbers of L[i..N]. 
    else if ith letter of S is 'M' 
     multiply B to all numbers of L[i..N]. 

    for all number in L[i..N], module them by C. 
print L[i] 

end 

，使其在O（n）的時間運行如何優化這個算法？數組的長度以及字符串的長度是n。 無論如何，在這個算法中的任何優化（比如去除僅用於加法和乘法的循環）都會受到歡迎。

Answer 1

這個答案很長，但是我已經用相當方便的方式寫了很多解釋，所以請耐心等待。

假設A和B都是整數，有可能在O(N)時間內解決此問題。否則，您可以在此停止閱讀。但我認爲有必要將算法分解成幾個不同的步驟，每個步驟都是O(N)。所以它總體上仍然是O(N)。

也許是問題的最困難的部分是要弄清楚如何使在線性時間這一步運行：

if ith letter of S is 'R' 
     reverse L[i...N] 

如果我們只是一味地在原來的算法盯着，我們將確信，即使其他步驟可以在線性時間內完成，這個步驟可以在線性時間內完成永不。但事實並非如此。我們該怎麼做呢？我想到的方式是從雙端隊列/ deque數據結構借鑑一個想法。由於我們知道數組L有多長，我們只保留3個變量，leftmost,rightmost和isReversed。

• leftmost將持有L陣列的當前最左邊的未使用的指標，所以leftmost被初始化爲1，因爲我們使用一個索引數組作爲你的問題陳述（術語「未使用」將在後面解釋）。
• rightmost將保存L數組當前最右邊未使用的索引，因此初始化爲N，長度爲L。
• isReversed用於指示數組是否被反轉。這初始化爲false。

我們的首要任務是在應用了所有reverse操作之後，計算出陣列L的原始元素的最終順序。我們不需要顛倒陣列一次即可獲得與倒車相同的效果。這可以通過遍歷輸入字符串S一次來完成，並找出在所有反向操作之後，陣列L中的哪個元素應該位於每個位置。爲了簡單起見，我們創建一個新的整數數組L'，它將在應用所有反向操作後保留L的最終原始元素，並嘗試填充L'。

假設我們在索引i和S[i] == 'R'，所以我們設置isReversed = true來表明我們正在倒轉子陣列[i..N]。當isReversed == true，我們知道子陣列[i..N]被顛倒，所以L'[i]的元素應該是最右邊未使用的元素，其索引是rightmost。因此，我們設置L'[i] = L[rightmost],遞減rightmost,1（rightmost = rightmost - 1）。相反，如果isReversed == false我們沒有反轉子陣列[i..N]，那麼L'[i]上的元素應該是最左邊的未使用元素，其索引爲leftmost。因此，我們設置了L'[i] = L[leftmost]和增量leftmost通過1（leftmost = leftmost - 1）。隨後的reverse將取消isReversed的值。

所以目前的算法是這樣的C++（我假設你確定使用C++，因爲你的問題的標籤之一是C++）：

// set up new array L' 
int Lprime[N+1]; 
int leftmost = 1; 
int rightmost = N; 
bool isReversed = false; 

for (int i = 1; i <= N; i++) { 
    if (S[i] == 'R') { 
     // negate isReversed 
     isReversed = !isReversed; 
    } 

    if (isReversed) { 
     Lprime[i] = L[rightmost]; 
     rightmost = rightmost - 1; 
    } else { 
     Lprime[i] = L[leftmost]; 
     leftmost = leftmost + 1; 
    } 
} 

請驗證這是否是正確的，但我相信它如此。

現在我們來看看原始算法的其餘部分：

else if ith letter of S is 'A' 
     add A to all numbers of L[i..N]. 
    else if ith letter of S is 'M' 
     multiply B to all numbers of L[i..N]. 

    for all number in L[i..N], module them by C. 

難的部分似乎是C在子陣[i..N]進行模數爲每指數i的需要。但基於我的理解有限，這是模算術，我們並不需要在子陣列[i..N]上爲每個i執行它。但不要聽我的話。我對數論的理解是非常簡單的。

不僅如此，加法和乘法的步驟也可以簡化。這裏的技巧是保留2個額外的變量，我們稱它們爲multiplicativeFactor和additiveConstant。 multiplicativeFactor用於保存一個常數，我們需要乘以L'[i]。這最初是1。顧名思義，additiveConstant變量用於存儲在L'[i]乘以multiplicativeFactor完成後我們需要添加到L'[i]的任何常數。 additiveConstant已啓動至0。

爲了更具體地瞭解這一點，我們設置A = 3，B = 5。假設S是字符串"AMMAAM"。這意味着以下（注：我們忽略模C現在）：

• 在指數1，設置L'[1] = L'[1] + 3;
• 在指數2，設置L'[2] = (L'[2] + 3) * 5;
• 在指數3，設置L'[3] = ((L'[3] + 3) * 5) * 5;
• 索引4，集L'[4] = (((L'[4] + 3) * 5) * 5) + 3;
• 在索引5，設置L'[5] = ((((L'[5] + 3) * 5) * 5) + 3) + 3
• 在索引6，設置L'[6] = (((((L'[6] + 3) * 5) * 5) + 3) + 3) * 5

觀察到現有的字符'A'和'M'的效應「結轉」（或級聯）插入的L'未來元件。讓我們來表達這些操作略有不同：

• L'[1] = L'[1] + 3
• L'[2] = 5 * L'[2] + (3 * 5)
• L'[3] = 5 * 5 * L'[3] + (3 * 5 * 5)
• L'[4] = 5 * 5 * L'[4] + (3 * 5 * 5 + 3)
• L'[5] = 5 * 5 * L'[5] + (3 * 5 * 5 + 3 + 3)
• L'[6] = 5 * 5 * 5 * L'[6] + (3 * 5 * 5 + 3 + 3) * 5

我們小號撻看到一些圖案。

• 乘法因子L'[i]始終爲B的乘方。添加A對此乘法因素無任何影響。乘法因數被存儲在我們上面
• 每次我們需要通過附加的B相乘L'[i]描述的multiplicativeConstant變量，有必要乘以所有的常數由B（從添加A發生）以獲得最終的常數加到L'[i]。這是上述變量additiveConstant的用途。
• 的L'[i]乘法應該加入additiveConstant到L'[i]

因此，每個L'[i]的最終值可被表示爲multiplicativeConstant * L'[i] + additiveConstant;之前完成，並且該算法的第二主要部分看起來像這樣：

int multiplicativeConstant = 1; 
int additiveConstant = 0; 
for (int i = 1; i <= N; i++) { 
    if (S[i] == 'A') { 
     additiveConstant += A; 
    } else if (S[i] == 'M') { 
     multiplicativeConstant *= B; 
     // need to multiply all the constants by B as well 
     additiveConstant *= B; 
    } 
    Lprime[i] = multiplicativeConstant * Lprime[i] + additiveConstant; 
} 

有一個告誡，我沒有談到。 整數溢出的multiplicativeConstant和additiveConstant，以及中間計算。如果L是int數組，我們很幸運，因爲我們可以使用long long來避免溢出。否則，我們必須小心中間計算不會溢出。

現在modulo C操作怎麼樣？實際上，他們在L'[i]範圍內的每個值都在[0..C-1]之間。根據我有限的數量理論的理解，我們可以這樣執行模運算來達到同樣的效果：

int multiplicativeConstant = 1; 
int additiveConstant = 0; 
for (int i = 1; i <= N; i++) { 
    if (S[i] == 'A') { 
     additiveConstant = (additiveConstant + (A % C)) % C; 
    } else if (S[i] == 'M') { 
     multiplicativeConstant = (multiplicativeConstant * (B % C)) % C; 
     // need to multiply all the constants by B as well 
     additiveConstant = (additiveConstant * (B % C)) % C; 
    } 
    Lprime[i] = ((multiplicativeConstant * (Lprime[i] % C)) % C + additiveConstant) % C; 
} 

這解決了multiplicativeConstant和additiveConstant變量的溢出問題（但並不妨礙中間計算的溢出和其他變量），並完成我們的算法。我相信這是正確的，但要自己覈實一下。我無法解釋模塊化算術的東西，因爲我只知道如何使用它，所以你必須自己查看它。在附註中，A % C和B % C零件可以完成一次，其結果存儲在變量中。

最後，把一切在一起：

// set up new array L' 
int Lprime[N+1]; 
int leftmost = 1; 
int rightmost = N; 
bool isReversed = false; 

for (int i = 1; i <= N; i++) { 
    if (S[i] == 'R') { 
     // negate isReversed 
     isReversed = !isReversed; 
    } 

    if (isReversed) { 
     Lprime[i] = L[rightmost]; 
     rightmost = rightmost - 1; 
    } else { 
     Lprime[i] = L[leftmost]; 
     leftmost = leftmost - 1; 
    } 
} 

int multiplicativeConstant = 1; 
int additiveConstant = 0; 
// factor out A % C and B % C 
int aModC = A % C; 
int bModC = B % C; 
for (int i = 1; i <= N; i++) { 
    if (S[i] == 'A') { 
     additiveConstant = (additiveConstant + aModC) % C; 
    } else if (S[i] == 'M') { 
     multiplicativeConstant = (multiplicativeConstant * bModC) % C; 
     // need to multiply all the constants by B as well 
     additiveConstant = (additiveConstant * bModC) % C; 
    } 
    Lprime[i] = ((multiplicativeConstant * (Lprime[i] % C)) % C + additiveConstant) % C; 
} 
// print Lprime 

這將運行在整體O(N)時間。

再次，如果你擔心整數溢出，假設L是int數組，你可以使用long long爲參與計算的所有變量，你應該罰款。