Ich habe ein Problem:C++ - Code-Optimierung
Sie eine Sequenz gegeben sind, in Form einer Zeichenkette mit Zeichen ‚0‘, ‚1‘, und nur ‚?‘. Angenommen, es gibt k '?' S. Dann gibt es 2^k Wege, jedes '?' Durch eine '0' oder eine '1' zu ersetzen, was 2^k verschiedene 0-1 Sequenzen ergibt (0-1 Sequenzen sind Sequenzen mit nur Nullen und Einsen).
Definieren Sie für jede 0-1-Sequenz die Anzahl der Inversionen als Mindestanzahl an benachbarten Swaps, die zum Sortieren der Sequenz in nicht abnehmender Reihenfolge erforderlich sind. Bei diesem Problem wird die Sequenz genau in nicht abnehmender Reihenfolge sortiert, wenn alle Nullen vor allen Einsen auftreten. Zum Beispiel hat die Sequenz 11010 5 Inversionen. Wir können es durch die folgenden Schritte sortieren: 11010 →→ 11001 →→ 10101 →→ 01101 →→ 01011 →→ 00111.
Finden Sie die Summe der Anzahl von Umkehrungen der 2^k Sequenzen, Modulo 1000000007 (10^9 + 7).
Zum Beispiel:
Eingang: ?? 01 -> Ausgabe: 5
Eingabe: 0? -> Ausgang: 3
Hier ist mein Code:
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <math.h>
using namespace std;
void ProcessSequences(char *input)
{
int c = 0;
/* Count the number of '?' in input sequence
* 1??0 -> 2
*/
for(int i=0;i<strlen(input);i++)
{
if(*(input+i) == '?')
{
c++;
}
}
/* Get all possible combination of '?'
* 1??0
* -> ??
* -> 00, 01, 10, 11
*/
int seqLength = pow(2,c);
// Initialize 2D array of integer
int **sequencelist, **allSequences;
sequencelist = new int*[seqLength];
allSequences = new int*[seqLength];
for(int i=0; i<seqLength; i++){
sequencelist[i] = new int[c];
allSequences[i] = new int[500000];
}
//end initialize
for(int count = 0; count < seqLength; count++)
{
int n = 0;
for(int offset = c-1; offset >= 0; offset--)
{
sequencelist[count][n] = ((count & (1 << offset)) >> offset);
// cout << sequencelist[count][n];
n++;
}
// cout << std::endl;
}
/* Change '?' in former sequence into all possible bits
* 1??0
* ?? -> 00, 01, 10, 11
* -> 1000, 1010, 1100, 1110
*/
for(int d = 0; d<seqLength; d++)
{
int seqCount = 0;
for(int e = 0; e<strlen(input); e++)
{
if(*(input+e) == '1')
{
allSequences[d][e] = 1;
}
else if(*(input+e) == '0')
{
allSequences[d][e] = 0;
}
else
{
allSequences[d][e] = sequencelist[d][seqCount];
seqCount++;
}
}
}
/*
* Sort each sequences to increasing mode
*
*/
// cout<<endl;
int totalNum[seqLength];
for(int i=0; i<seqLength; i++){
int num = 0;
for(int j=0; j<strlen(input); j++){
if(j==strlen(input)-1){
break;
}
if(allSequences[i][j] > allSequences[i][j+1]){
int temp = allSequences[i][j];
allSequences[i][j] = allSequences[i][j+1];
allSequences[i][j+1] = temp;
num++;
j = -1;
}//endif
}//endfor
totalNum[i] = num;
}//endfor
/*
* Sum of all Num of Inversions
*/
int sum = 0;
for(int i=0;i<seqLength;i++){
sum = sum + totalNum[i];
}
// cout<<"Output: "<<endl;
int out = sum%1000000007;
cout<< out <<endl;
} //end of ProcessSequences method
int main()
{
// Get Input
char seq[500000];
// cout << "Input: "<<endl;
cin >> seq;
char *p = &seq[0];
ProcessSequences(p);
return 0;
}
die Ergebnisse direkt für kleine Größe eingegeben wurden, aber für größere Größe Eingabe habe ich Zeit CPU Zeitlimit> 1 Sekunde. Ich habe auch Speichergröße überschritten. Wie man es schneller und optimalen Speicherverbrauch macht? Welchen Algorithmus sollte ich verwenden und welche bessere Datenstruktur sollte ich verwenden? Danke.
Sie zeigen Ihren Code in der Frage nicht (so ist Ihre Frage sehr unklar). Und wenn Sie Ihren Code zeigen würden, würde Ihre Frage zu einer * fix-my-code * -Frage werden. –
@BasileStarynkevitch Aktualisiert, sorry, ich habe vergessen, meinen Code zu posten. –
@BasileStarynkevitch, ach ja, es gibt eine Frage zu meinem festen Code, sorry, wusste das nicht. –