gpt4 book ai didi

c++ - 需要算法帮助(Codility)

转载 作者:塔克拉玛干 更新时间:2023-11-03 00:44:40 25 4
gpt4 key购买 nike

<分区>

在这个问题中,我们只考虑由小写英文字母 (a−z) 组成的字符串。如果字符串从左到右的读法与从右到左的读法完全相同,则该字符串是回文。

例如,这些字符串是回文:

aza
abba
abacaba

这些字符串不是回文:

zaza
abcd
abacada

给定一个长度为 N 的字符串 S,S 的一个切片是由一对整数 (p, q) 指定的 S 的子串,使得 0 ≤ p < q < N .如果字符串由字母 S[p], S[p+1], ..., S[q] 组成,则字符串 S 的切片 (p, q) 是回文的是回文。

例如,在一个字符串中 S = abbacada:

切片 (0, 3) 是回文因为 abba是回文,
切片 (6, 7) 不是回文因为 da不是回文,
切片 (2, 5) 不是回文因为 baca不是回文,
切片 (1, 2) 是回文因为 bb是一个回文。


写一个函数int solution(const string &S);即,给定长度为 N 个字母的字符串 S,返回 S 的回文切片的数量。如果该数字大于 100,000,000,则该函数应返回 -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(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()>3000 我总是遇到运行时错误(意味着时间超过 3 秒,但解决方案应该在不到 2 秒内工作)!有什么建议吗?

好的!和主要功能是这样的:

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

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com