我正在做 TopCoder 上的 AB problem,我的代码通过了除一个外的所有系统测试用例。这是问题陈述:
给定两个整数:N 和 K。Lun 狗对满足以下条件的字符串感兴趣: - 字符串恰好有 N 个字符,每个字符都是 'A' 或 'B'。 - 字符串 s 恰好有 K 对 (i, j)(0 <= i < j <= N-1),使得 s[i] = 'A' 且 s[j] = 'B'。
如果存在满足条件的字符串,则找到并返回任意一个这样的字符串。否则,返回空字符串。
我的算法是从长度为
给定两个整数:N 和 K。Lun 狗对满足以下条件的字符串感兴趣: - 字符串恰好有 N 个字符,每个字符都是 'A' 或 'B'。 - 字符串 s 恰好有 K 对 (i, j)(0 <= i < j <= N-1),使得 s[i] = 'A' 且 s[j] = 'B'。
如果存在满足条件的字符串,则找到并返回任意一个这样的字符串。否则,返回空字符串。
我的算法是从长度为
N
的由所有A
组成的字符串开始。初始时,对数为0。遍历字符串时,如果对数小于K
,则从字符串末尾开始用B
替换最右边的A
。如果对数变得大于K
,则用B
替换字符串开头的A
。任何时候的对数都是countOfAs * countOfBs
。string createString(int n, int k) {
string result(n, 'A'); // "AAAA....A"
int i = 0, j = n - 1; // indexes to modify the string
int numPairs = 0; // number of pairs
int countA = n; // count of As in the string
int countB = 0; // count of Bs in the string
do {
if (numPairs > k) {
result[i++] = 'B';
}
else if (numPairs < k) {
result[j--] = 'B';
countB++;
}
else {
return result;
}
countA--;
numPairs = countA * countB;
} while (numPairs != 0); // numPairs will eventually go to 0 as more Bs are added
return "";
}
我遇到的测试用例失败是 N=13, K=29
。 由于K
是一个质数,因此不存在等于K
的countOfAs * countOfBs
。
示例答案给出了 "AAAABBBBBBABA"
作为答案(因为您可以从前4个A、前6个B、倒数第二个A和最后一个B中组成一对,即4*6 + 4*1 + 1*1=29
)
countOfAs * countOfBs == K
。它被称为countOfAs == K && countOfBs == 1
。确保你的代码包括这种情况。 - hyper-neutrino