为什么我在编码中总是出现性能错误?

Question

我似乎总是在我做的几乎每个程序上都出现超时错误，尽管它似乎在语法上是正确的。例如，这是我的GenomicRangeQuery代码：

vector<int> solution(string &S, vector<int> &P, vector<int> &Q) {
int i, n, j, B;
int min;
n=P.size();
vector<int> C;
for(i=0; i<n; i++)
{
min=4;
for(j=P[i]; j<=Q[i]; j++)
{
switch(S[j])
{
case 'A':
B=1;
break;
case 'C':
B=2;
break;
case 'G':
B=3;
break;
case 'T':
B=4;
break;
}
if(B<min)
{
min=B;
}
}
C.push_back(min);
}
return C;
}

从语法上讲，这是正确的，但所有三种性能情况都会引发超时错误。

Answer 1

每个任务都有关于性能的要求;在大多数情况下，这与时间复杂度有关。上述GenomicRangeQuery并没有施加如此严格的限制，但它需要一个有效的解决方案。

对我来说，您的解决方案的第一个可能的优化是在第一次出现A时提前退出，因为这意味着整个序列的最小影响因子肯定会1。想象一个序列：ATTT[....]T(1 A 和 99,999 倍 T(。您可以在第一次A后退出，但影响仍然最小1.