用K对创建二进制字符串 [英] Creating a binary string with K pairs

问题描述

我正在对TopCoder和我的代码进行 AB问题通过除一个之外的所有系统测试用例。这是问题陈述：

I'm doing the AB problem on TopCoder and my code passes all the system test cases except for one. This is the problem statement:

您将获得两个整数： N 和 K 。狗对Lun感兴趣的字符串满足以下条件：

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

• 字符串的正好为 N 个字符，每个字符都是'A'或'B'。


• 字符串 s 的字符串恰好是 K 对（i，j）（ 0< = i< j< = N- 1 ），这样 s [i] ='A'和 s [j] ='B'。

• 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 ，我将从字符串末尾开始的B替换最右边的A。如果对数大于 K ，那么我将字符串开头的As替换为Bs。任何给定时间的对数为 countOfAs * countOfBs 。

My algorithm was to start with a string of length N consisting of all As. Initially the number of pairs is 0. While traversing the string if the number of pairs is less than K I replace the rightmost As with Bs starting from the end of the string. If the number of pairs become greater than K then I replace the As at the beginning of the string with Bs. The number of pairs at any given time is 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 。

The test case which fails for me is N=13, K=29. K being a prime number there is no countOfAs * countOfBs that equals K.

示例答案给出了 AAAABBBBBBABA 作为答案（因为您可以从前4个As，前6个B，倒数第二个A和最后一个B，即 4 * 6 + 4 * 1 + 1 * 1 = 29 ）

The sample answer gave "AAAABBBBBBABA" as an answer (because you can make pairs from the first 4 As, the first 6 Bs, the second to last A, and the last B, i.e 4*6 + 4*1 + 1*1=29)

推荐答案

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

Here's a recursive method which creates a solution with the least number of B's:

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

Start with a string of all A's, and find the rightmost position for which placing a B will create at most K pairs; e.g.:

N=13, K=29  

0123456789ABC  
aaaaaaaaaaaab  <-  position 12 creates 12 pairs  

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

Then recurse with N = position, K = K - position + #B = 18 and #B = 1, where #B is the number of B's added so far. In the following steps, adding a B in position X will add X pairs, but also decrease the number of pairs created by the already added B's by #B; that's why we increase the required pairs K by #B at each step.

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

0123456789AB  
aaaaaaaaaaab  <-  position 11 adds 11 pairs  

然后递归N = 11，K = K-11 + #B = 9，#B = 2：

Then recurse with N = 11, K = K - 11 + #B = 9, #B = 2:

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

0123456789A  
aaaaaaaaaba  <-  position 9 creates 9 pairs  

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

We've reached the exact number of required pairs, so we can stop the recursion, and the complete solution is:

aaaaaaaaababb

如您所见，每个递归级别只有两种情况：K≥在递归之前将N和B添加到末尾，或者K < N和B放在位置K上，这便完成了解决方案。

As you see there are only two cases at every recursion level: either K ≥ N and a B is added to the end before recursing, or K < N and a B is put at postion K and this completes the solution.

如果您添加N / 2个B并且K的值仍大于零，则存在不是有效的解决方案；但是您可以通过检查（N / 2） ² 是否小于K来进行检查。

If you add N/2 B's and the value of K is still greater than zero, then there is no valid solution; but you can check this upfront by checking whether (N / 2)² is less than 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  

当然可以轻松地将这种转换合并到算法中。

这篇关于用K对创建二进制字符串的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！