string - 用 K 对创建二进制字符串

Question

我正在做 AB problem在 TopCoder 上，我的代码通过了除一个之外的所有系统测试用例。这是问题陈述:

You are given two ints: N and K. Lun the dog is interested in strings that satisfy the following conditions:

• The string has exactly N characters, each of which is either 'A' or 'B'.
• The string s has exactly K pairs (i, j) (0 <= i < j <= N-1) such that s[i] = 'A' and s[j] = 'B'.

If there exists a string that satisfies the conditions, find and return any such string. Otherwise, return an empty string

我的算法是从一个长度为 N 的字符串开始由所有 A 组成秒。最初对数为 0。如果对数小于 K，则遍历字符串。我从字符串末尾开始用 Bs 替换最右边的 As。如果对数变得大于 K然后我用 Bs 替换字符串开头的 As。在任何给定时间的对数是 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作为质数，没有 countOfAs * countOfBs等于 K .

示例答案为 "AAAABBBBBBABA"作为答案(因为您可以将前 4 个 A、前 6 个 B、倒数第二个 A 和最后一个 B 配对，即 4*6 + 4*1 + 1*1=29)

Answer 1

这是一个递归方法，它创建一个 B 数最少的解决方案:

从所有 A 的字符串开始，找到放置 B 最多会创建 K 对的最右边的位置；例如:

N=13, K=29  

0123456789ABC  
aaaaaaaaaaaab  <-  position 12 creates 12 pairs  

然后递归 N = position，K = K - position + #B = 18 和 #B = 1，其中 #B 是到目前为止添加的 B 的数量。在下面的步骤中，在位置 X 添加 B 将添加 X 对，但也会减少已添加的 B 所创建的对数#B；这就是为什么我们在每一步都将所需的对 K 增加#B。

N=12, K=18, #B=1  

0123456789AB  
aaaaaaaaaaab  <-  position 11 adds 11 pairs  

然后递归 N = 11, K = K - 11 + #B = 9, #B = 2:

N=11, K=9, #B=2  

0123456789A  
aaaaaaaaaba  <-  position 9 creates 9 pairs  

我们已经达到了所需对的确切数量，因此我们可以停止递归，完整的解决方案是:

aaaaaaaaababb

如您所见，每个递归级别只有两种情况:要么 K ≥ N 并且在递归之前将 B 添加到末尾，要么 K < N 并且将 B 放在位置 K 并完成解决方案。

如果加上N/2个B，K的值仍然大于零，则无有效解；但是您可以通过检查 (N/2)² 是否小于 K 来预先检查这一点。

function ABstring(N, K, B) {
    if (B == undefined) {                     // top-level recursion
        if ((N / 2) * (N / 2) < K) return ""; // return if impossible
        B = 0;
    }
    if (K >= N) return ABstring(N - 1, K - (N - 1) + B + 1, B + 1) + 'B';
    var str = "";
    for (var i = 0; i < N; i++) str += (K && i == K) ? 'B' : 'A';
    return str;
}
document.write(ABstring(13, 29));

我最初将此方法创建的解决方案描述为字典序最小的解决方案，但这并不正确。它创建了一个 B 数量最少的解决方案，并将每个 B 放在最右边的位置，但是这样的解决方案:

aaaabaaaabbbb  

当然可以通过将第一个 B 向右移动并通过将第二个 B 向左移动进行补偿来使字典序更小:

aaaabaaaabbbb  
aaaaabaababbb  
aaaaaabbaabbb  

这个转换当然可以很容易地合并到算法中。