Algoritma yardımı gerekli (Kodlama)

Question

Bu problemde sadece küçük harfli İngilizce harflerden oluşan dizeleri ele alacağız (a − z). Bir dize, sağdan sola olduğu gibi tam olarak aynı soldan sağa okursa palindromdur. Uzunluk^N 'bir dizisi G Verilen

zaza 
abcd 
abacada 

, S, bir dilim belirtilen S de bir alt:

aza 
abba 
abacaba 

Bu şeritler palindrom değildir:

Örneğin, bu şeritler palindrom olan 0 ≤ p < q < N gibi bir çift sayıyla (p, q). S[p], S[p+1], ..., S[q] harflerinden oluşan dizgenin bir palindrom olması durumunda, S dizisinin bir dilimi (p, q) palindromiktir. da bir palindrom,
dilim olmadığı için abba bir palindrom,
dilim için örneğin

bir dizge içinde S = abbacada:

dilim (0, 3) palindromik (6, 7) palindromik olmayan (2, 5) palindromik değildir çünkü baca palindrom değildir,
dilim (1, 2) palindromiktir, çünkü bb bir palindromdur.

---

bir işlev uzunluğu N, bir harf dizisi S tarafından, işlev döndürmelidir -1 bu sayı 100,000,000 daha büyük ise S. palindromik dilim sayısı ile döner, int solution(const string &S); yazın. Örneğin, S = baababa dizgisi için işlev, 6 karakterini döndürmelidir, çünkü dilimlerinin tam altı tanesi palindromiktir; yani: (0, 3), (1, 2), (2, 4), (2, 6), (3, 5), (4, 6).

Varsayalım:
- N, [0..20.000] aralığında bir tamsayıdır;
- Dize S sadece küçük harflerden (a − z) oluşur.

Karmaşıklık:
- beklenen en kötü durum zaman karmaşıklığı O (N);
- beklenen en kötü durum alanı karmaşıklığı O (N) (giriş bağımsız değişkenleri için gerekli depolamayı saymaz).

İşte benim çözümdür: Büyük dizeleri ile

int palindrom(const string &S, int startIndex,int endIndex, int counter=0) 
{ 
    bool equals = true; 
    if (endIndex - startIndex < 1) 
     return counter; 
    for(int i = startIndex,j = endIndex;i<j; ++i, --j) 
    { 
     equals = S[i] == S[j]; 
     if (!equals) break; 
    } 
    if (equals) counter++; 
    counter = palindrom(S,startIndex,endIndex-1,counter); 
    return counter; 
} 

int solution(const string &S) 
{ 
    int length = S.size(); 
    int counter = 0; 
    if (length > 20000) return -1; 
    for(int i=0; i < length-1; i++) 
    { 
     counter += palindrom(S,i,length-1); 
     if (counter > 100000000) return -1; 
    } 
    return counter; 
} 

S.size()> Hep çalışma zamanı hatası alıyorum 3000 (süresi 3 saniye ama çözüm az sonra 2 saniye içinde çalışması gerekir daha sonra demektir)! Baska öneri?

tamam! özyineleme olmadan

main(){cout<<solution("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa");} 

Answer 1

yapardım

#include <string> 
#include <iostream> 

typedef std::string::const_iterator P; 

bool is_palindrom(P begin, P end) { 
    while (begin < end) { 
     if (*begin != *end) 
      return false; 
     ++begin; 
     --end; 
    } 
    return true; 
} 

int count_palindroms(const std::string &s) { 
    int c = 0; 
    P left = s.begin(); 
    while (left < s.end()) { 
     P right = left + 1; // because length palindrome > 1 
     while (right < s.end()) { 
      if (is_palindrom(left, right)) { 
       //std::cout << left - s.begin() << ' ' << right - s.begin() << std::endl; 
       c++; 
       if (c > 100000000) 
        return -1; 
      } 
      ++right; 
     } 
     ++left; 
    } 
    return c; 
} 

int main(int , char *[]) 
{ 
    std::cout << count_palindroms("baababa") << std::endl; 
    return 0; 
} 

Answer 2

Benim PC'de çalışıyor: ve ana işlevi gibi bir şeydir. Aslında burada yaptığınız şey, orijinal dizenin her bir alt dizesini kontrol etmek ve bunun üzerinde yinelemeli bir işlev çalıştırmaktır. @PeterT'den bahsetmişseniz, muhtemelen takılı kaldığınız maksimum derinliğe ulaşmış olursunuz.

Ne çağrı yığını kullanmak değildir yapacağını, ancak ya benim kendi sıkışmış kullanın veya benzeri bazı basit dize işlevlerini kullanın: Örnek

std::string s = "aba"; 
std::string s1 = std::string(s.rbegin(), s.rend()); 
if (s == s1) 
{ 
///... 
} 

. Zaman karmaşıklığı İlişkin

- Eğer o (n) 'de hepsini kontrol edemez here okuyabilir olarak.

Answer 3

ben sadece (algoritma küçük değişiklikle) özyinelemeye silmek olacaktır:

int palindrom(const string &S, int startIndex, int endIndex, int counter = 0) 
{ 
    for (int k = endIndex; k > startIndex; --k) { 
     bool equals = true; 
     for (int i = startIndex, j = k; i < j; ++i, --j) 
      if (S[i] != S[j]) { 
       equals = false; 
       break; 
      } 
     if (equals) 
      counter++; 
    } 
    return counter; 
}