使用K对生成二进制字符串

Question

我正在做 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的由所有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）

- template boy

---

但是有一个 countOfAs * countOfBs == K。它被称为 countOfAs == K && countOfBs == 1。确保你的代码包括这种情况。 - hyper-neutrino

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  

当然，这种转换可以很容易地融入算法中。

- m69 ''snarky and unwelcoming''

Answer 2

你可以注意到，在[0, N-1]的任何值上都可以形成一个字符串，方法是构建以下字符串：

B B B ... A B ... B
          ^
          index: N-1-K

你可以通过使用两个 A 将这个原则扩展到以下 K 值:

A B B ... A B ... B
          ^
          index: (N-1)-(K-(N-2)) = 2N-3-K

这个方案可以在区间[N, 2N-4]内生成所有的K值。

如果使用pAs，则可以通过在左侧使用(p-1)As并将一个A从右向左移动来生成区间[(p-1)*(N-p), p*(N-p)]中所有的K值。

例如，如果N=19且K=23，则可以使用以下字符串：

A B B ... A B B B B B B
          ^
          index: 2N-3-K = 38-3-23 = 12

- fjardon

Answer 3

有一个简单的数学解决方案，可以产生最优的答案，以所需字符串长度为准：

for a given pair of positive integers, (a,b),
the highest product achievable when
sum(a,b) is fixed is when a ≈ b since
a^2 is necessarily greater than (a+1)*(a-1)

现在我们的问题可以简单地概括为：

a*b + a_0*b_0 + a_1*b_1 ... = K,
where a + b + a_0 + a_1 ... <= N
(meaning only the first b term is included in the second sum)

但是任何数字K都可以表示为：

K = p*p' + 1*m, where p ≈ p' and m <= max(p, p')

当这个表达式最小化固定的总和时，

p + p' + 1
(remember the 1*m represents our a_0*b_0 above, 
where only the a_0 is summed and b_0, which is m, is ignored)

因此，需要最少字符串长度的解决方案是:

let A = round(sqrt(K))
let B = floor(K / A)
let M = remainder(K / A)

min(A,B) 'a's
followed by max(A, B) 'b's
with an additional 'a' inserted M 'b's back
for a total of A + B + 1 characters
(the rest can be filled with 'a's)

例子：

N = 13
K = 29

A = round(sqrt(29)) = 5
B = floor(29 / 5) = 5
M = remainder(29 / 5) = 4

aaaaa
aaaaabbbbb
aaaaababbbb (5 + 5 + 1 = 11 characters)
       <--M 'b's back 

Solution: aaaaababbbbaa

- גלעד ברקן