算法的帮助是必要的(Codility) [英] Algorithm help is needed (Codility)
问题描述
在这个问题,我们只考虑字符串组成的小写英文字母(A-Z)。 字符串是回文如果读取刚好从左至右因为它从右到左的相同。
例如,这些字符串是回文:
氮杂
ABBA
abacaba
这些字符串不是回文:
扎扎
A B C D
abacada
鉴于长度为N的串S,S的切片是S的由一对整数(P,Q),以使得指定的一个子 0≤P&其中; Q< ñ
。字符串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< 1)
返回柜台;
的for(int i =在startIndex,J = endIndex的;我< 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<长度为1;我++)
{
计数器+ = palindrom(S,I,长度为1);
如果(柜>亿)返回-1;
}
返回柜台;
}
大串S.size()> 3000我总是得到运行时错误(指时间更多的则是3秒,但解决方案应该在更短的在2秒钟工作)!有什么建议?
OK!而主要的功能是一样的东西:
的main(){cout的<<解决方案(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屋!