如何将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为参与计算的所有变量，你应该罚款。