內存分配問題

Question

Here是我的代碼爲problem。代碼在我的Code :: blocks上運行正常，但不在spoj站點和ideone.com.I上運行時發生錯誤。我猜想，spoj服務器無法分配所需的內存量。請提出一些建議。

http://paste.ubuntu.com/1277109/（我的代碼）

Answer 1

您的代碼聲明一個空字符串s，然後分配給它的元素...

... 
string s,res;int c=0; 
int sum,carry=0; 
for(int i=m-1;i>=0;i--) 
{ 
    sum=(a[i]-'0')*2+carry; 
    s[c]=sum%10+'0';   // This is undefined behavior, s is empty 
    carry=sum/10; 
    c++; 
} 
... 

Answer 2

這距離@ 6502的答案延伸。

它看起來像ostringstream將很適合你想要的。

ostringstream oss; 
string s,res; 
int c=0; 
int sum,carry=0; 

for(int i=m-1;i>=0;i--) 
{ 
    sum=(a[i]-'0')*2+carry; 
    oss << (sum%10) << '0'; //Were you trying to concatenate a '0' as well? 
    carry=sum/10; 
} 

s = oss.str(); 

Answer 3

這是對您的problem的可能答案，而不是您的問題。

我想這個問題有算法的味道，其目的是找到一個時間複雜度最低的解決方案（可能是一個線性時間解決方案） 。 對與最佳時間複雜性有關的問題做一些預處理是有幫助的。

所以我計算幾個時間步長（以下給出）產生的圖案：

step            pattern       no. consecutive zero pairs 

    1            01           0 

    2            1001           1 

    3            01101001          1 

    4           1001011001101001         3 

    5         01101001100101101001011001101001       5 

    6     1001011001101001011010011001011001101001100101101001011001101001   11 

    7     0110100110010110100101100110100110010110011010010110100110010110   21 
        1001011001101001011010011001011001101001100101101001011001101001 

    8     1001011001101001011010011001011001101001100101101001011001101001   43 
        0110100110010110100101100110100110010110011010010110100110010110  
        0110100110010110100101100110100110010110011010010110100110010110 
        1001011001101001011010011001011001101001100101101001011001101001 

    9     0110100110010110100101100110100110010110011010010110100110010110   85 
        1001011001101001011010011001011001101001100101101001011001101001 
        1001011001101001011010011001011001101001100101101001011001101001 
        0110100110010110100101100110100110010110011010010110100110010110 
        1001011001101001011010011001011001101001100101101001011001101001 
        0110100110010110100101100110100110010110011010010110100110010110 
        0110100110010110100101100110100110010110011010010110100110010110 
        1001011001101001011010011001011001101001100101101001011001101001 

其產生上述模式的代碼如下給出：

#include<iostream> 
using namespace std; 
main() 
{ 
string s,t=""; 
s="paste pattern produced in a time-step here"; 
int i,l,n=0; 
l=s.length(); 
cout <<"s.length - "<<l<<endl; 
    for(i=0;i<l;i++) 
    { 
     if(s[i]=='0') 
      {t+="10";} 
     else 
      {t+="01";} 
    } 
l*=2; 
     for(i=0;i<l-1;i++) 
     { 
      if(t[i]=='0' && t[i+1]=='0') 
      { 
      n+=1; 
      } 
     } 
cout <<"t - "<<t<<endl; 
cout <<"no. of consecutive zero pairs - "<<n<<endl; 
} 

幾個重要的觀察結果指出如下：

1）每個時間步的字符數是前一步的兩倍。

2）在前面的時間步驟中爲組合產生一對連續的零。

3）任何模式的後半部分將是其上半年的NOT。

現在來了有趣的部分。查看每步產生的連續零對數。如果我們將第一個步驟的結果，說n的零：

對於第2步，我們有其結果作爲N * 2 + 1，其中n是0。

對於步驟3，我們有其結果作爲N * 2 - 1，其中n是1。

對於步驟4，我們有其結果作爲N * 2 + 1，其中n是1。

對於步驟5中，我們有其結果作爲N * 2 - 1，其中n是3。

或一般的，我們有結果等於N * 2 - 1（奇數時間步長） 和結果等於N * 2 + 1（甚至時間步長）

這不會解決我們的問題， n是一個變量，我們需要 找到一個數學公式，它涉及初始結果（對於時間步驟1） 和任何時間步驟t的結果。

但我們有一個簡單的方法。

看數字0,1,1,3,5,11,21,43,85 ....

它構成了Jacobsthal sequence。

這是我們的解決方案。

1）通過輸入數字，找出最大。這需要O（n）時間。

2）創建Jacobsthal數字的查找表（LUT），最大爲，最大值爲。這需要 不超過O（n）時間，因爲您只需要當前Jacobsthal數的前兩個Jacobsthal數。 Jacobsthal數字的性質顯而易見。

3）再次遍歷輸入的數字，這次從LUT輸出相應的 序列號。查表需要O（1）次，而n個數字的總時間爲O（n）。

4）整個問題的時間複雜度爲O（n）。

這種方法的一個優點是我們不必處理大字符串。