整數數組的所有子部分的總和

給定數組{1,3,5,7}，其子部分定義爲{1357,135,137,157,357,13,15,17,35,37,57,1,3,5,7}。我必須在新數組中找到所有這些數字的總和。在這種情況下總結出來是2333. 請幫我找一個解決方案O(n)。我的O(n^2)解決方案超時。整數數組的所有子部分的總和

問題的鏈接是here或here。

我的當前的嘗試（在找到一個圖案）是

for(I=0 to len) //len is length of the array 
{ 
    for(j=0 to len-i) 
    { 
      sum+= arr[I]*pow(10,j)*((len-i) C i)*pow(2,i) 
    } 
}

在字 - LEN-I C I =（數目的整數的向右）C重量。（組合{從排列組合}） 2^I = 2的功率（整數數到左）

感謝

來源

2015-05-31 the_coder

也注意到陣列的長度可能很大。有關如何制定解決方案來保持時間和複雜性的任何提示？ –

您可以使用簡單遞歸輕鬆解決此問題。

def F(arr): 
    if len(arr) == 1: 
     return (arr[0], 1) 
    else: 
     r = F(arr[:-1]) 
     return (11 * r[0] + (r[1] + 1) * arr[-1], 2 * r[1] + 1)

那麼，它是如何工作的？很簡單。假設我們想要計算{1,3,5,7}的所有子部分的總和。假設我們知道{1,3,5}的組合數和{1,3,5}的子部分的總和，並且我們可以使用以下公式容易地計算{1,3,5,7}：

SUM_SUBPART（{1,3,5,7}）= 11 * SUM_SUBPART（{1,3,5}）+ NUMBER_COMBINATION（{1,3,5}）* 7 + 7

這個公式可以很容易地通過觀察得出。讓我們說我們有{1,3,5}

A = [135, 13, 15, 35, 1, 3, 5]

所有組合如果展開invisal的遞歸我們可以輕鬆地創建的{1,3,5,7}由

A = [135, 13, 15, 35, 1, 3, 5] + 
    [135 * 10 + 7, 
    13 * 10 + 7, 
    15 * 10 + 7, 
    35 * 10 + 7, 
    1 * 10 + 7, 
    3 * 10 + 7, 
    5 * 10 + 7] + [7]

來源

2015-05-31 12:58:20 invisal

非常感謝！：D 好的方法。 –

好了，你可以看看的子部分爲數字的總和：

1357 = 1000*1 + 100*3 + 10*5 + 1*7 
135 = 100*1 + 10*3 + 1*5 
137 = 100*1 + 10*3 + 1*7

等。

所以，你需要做的就是總結一下你的號碼，然後根據項目制定的數量是什麼乘數：

兩個數字[x, y]：

[x, y, 10x+y, 10y+x]

=>你的乘數是1 + 10 + 1 = 12

三個數字[x, y, z]：

[x, y, z, 
10x+y, 10x+z, 
10y+x, 10y+z, 
10z+x, 10z+y, 
100x+10y+z, 100x10z+y 
. 
. ]

=>你乘數是1 + 10 + 10 + 1 + 1 + 100 + 100 + 10 + 10 + 1 + 1 = 245

您可以很容易地計算出n數字的等式....

來源

2015-05-31 12:42:39

由於不允許重新排序，所有數字的乘數不會相同。看看7總是處於最後的位置？ – Joni

有一件事，對於兩個數字 - [x，y] ..我們得到：[x，y，10x + y] ..我們不要有10y + x或10z + x或10z + y等等。我試圖做出一個模式，但我不能做一個O（n）模式。我目前的是O（n^2）。 –

@Joni - 你是對的。我認爲我們正在處理這裏的所有選項。無論如何，這仍然可以用於每個數字。 –

列表解決方案，你得到這個明確的公式：

subpart sum = sum for k=0 to N-1: 11^(N-k) * 2^k * a[k]

這表明以下O（n）的算法：

multiplier = 1 
for k from 0 to N-1: 
    a[k] = a[k]*multiplier 
    multiplier = multiplier*2 

multiplier = 1 
sum = 0 
for k from N-1 to 0: 
    sum = sum + a[k]*multiplier 
    multiplier = multiplier*11

乘法和加法當然應該用模M來完成。

來源

2015-05-31 13:46:34 Joni

整數數組的所有子部分的總和

回答

相關問題