算法的帮助是必要的（Codility） [英] Algorithm help is needed (Codility)

问题描述

在这个问题，我们只考虑字符串组成的小写英文字母（A-Z）。 字符串是回文如果读取刚好从左至右因为它从右到左的相同。

例如，这些字符串是回文：

 氮杂
ABBA
abacaba
 

这些字符串不是回文：

 扎扎
A B C D
abacada
 

鉴于长度为N的串S，S的切片是S的由一对整数（P，Q），以使得指定的一个子 0≤P＆其中; Q＆LT; ñ。字符串S的片（P，Q）是回文，如果由字母串 S [P]，S [P + 1]，...，S [Q] 是一个回文。

例如，在一个字符串 S = abbacada：

片（0,3）是回文，因为 ABBA 是一个回文，
片（6,7）是不是回文，因为大不是回文，
片（2,5）是不是回文，因为巴卡不是回文，
片（1,2）是回文，因为 BB 是一个回文。

---

写一个函数 INT溶液（常量字符串和放大器; S）; ，给定长度为N字母串S，返回S的的回文片数函数应该返回-1，如果这个数大于亿

例如，对于字符串 S = baababa 函数应该返回6，因为它的片整整6是回文;即：（0,3），（1,2），（2,4），（2,6），（3,5），（4,6）

假设：
- N是范围[0..20,000]内的整数;
- 串S仅由小写字母（A-Z）。

复杂性：
- 预计最坏情况下的时间复杂度为O（N）;
- 预计最坏情况下的空间复杂度为O（N）（不包括所需的输入参数的存储）。

下面是我的解决办法：

  INT palindrom（常量字符串和放大器; S，诠释了startIndex，诠释endIndex的，INT计数器= 0）
{
    布尔等于= TRUE;
    如果（endIndex的 - 在startIndex＆LT; 1）
        返回柜台;
    的for（int i =在startIndex，J = endIndex的;我＆LT; D​​]; ++我，--j）
    {
        等于= S [I] == S [J]。
        如果（等于！）破;
    }
    如果（等于）反++;
    计数器= palindrom（S，在startIndex，endIndex的-1，计数器）;
    返回柜台;
}

INT溶液（常量字符串和放大器; S）
{
    INT长度= S.size（）;
    INT计数器= 0;
    如果（长度GT; 20000）返回-1;
    的for（int i = 0; I＆LT;长度为1;我++）
    {
        计数器+ = palindrom（S，I，长度为1）;
        如果（柜＆GT;亿）返回-1;
    }
    返回柜台;
}
 

大串S.size（）> 3000我总是得到运行时错误（指时间更多的则是3秒，但解决方案应该在更短的在2秒钟工作）！有什么建议？

OK！而主要的功能是一样的东西：

 的main（）{cout的＆LT;＆LT;解决方案（aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa）;}
 

解决方案

它工作正常，我的电脑。 什么你实际上是在这里做的是检查原始字符串的每个子字符串，并运行一个递归函数权。 正如@PeterT提到你很可能达到你的卡的最大深度。

我会做的是不使用调用堆栈，但无论是用我自己的卡，或者使用一些简单的字符串功能，如：

 的std ::字符串s =ABA;
标准::字符串S1 =标准::字符串（s.rbegin（），s.rend（））;
如果（S == S1）
{
/// ...
}
 

为例。

对于时间复杂度 - 因为你可以阅读<一个href="http://stackoverflow.com/questions/2560262/generate-all-unique-substrings-for-given-string">here你不能检查他们都在O（N）。

In this problem we consider only strings consisting of lower-case English letters (a−z). A string is a palindrome if it reads exactly the same from left to right as it does from right to left.

For example, these strings are palindromes:

aza
abba
abacaba

These strings are not palindromes:

zaza
abcd
abacada

Given a string S of length N, a slice of S is a substring of S specified by a pair of integers (p, q), such that 0 ≤ p < q < N. A slice (p, q) of string S is palindromic if the string consisting of letters S[p], S[p+1], ..., S[q] is a palindrome.

For example, in a string S = abbacada:

slice (0, 3) is palindromic because abba is a palindrome,
slice (6, 7) is not palindromic because da is not a palindrome,
slice (2, 5) is not palindromic because baca is not a palindrome,
slice (1, 2) is palindromic because bb is a palindrome.

---

Write a function int solution(const string &S); that, given a string S of length N letters, returns the number of palindromic slices of S. The function should return −1 if this number is greater than 100,000,000.

For example, for string S = baababa the function should return 6, because exactly six of its slices are palindromic; namely: (0, 3), (1, 2), (2, 4), (2, 6), (3, 5), (4, 6).

Assume that:
- N is an integer within the range [0..20,000];
- string S consists only of lower-case letters (a−z).

Complexity:
- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

Here is my solution:

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;
}

with big strings S.size()>3000 I always get runtime error(means time is more then 3 sec but solution should work in less then 2 seconds)! Any suggestions?

ok! and main function is something like:

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

解决方案

It works fine on my PC. What you are actually doing here is checking every sub string of the original string and run a recursive function over it. As @PeterT mentioned you probably reach the max depth of your stuck.

What I would do is not use the call stack, but either use my own stuck, or use some simple string functions like:

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

for an example.

Regarding the time complexity - as you can read here you can't check them all in o(n).

这篇关于算法的帮助是必要的（Codility）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！