字符串连接查询-Java 学习之路

我有一个字符列表，比如x，用 b[1], b[2], b[3] ... b[x] 表示 . 在 x 之后，

b[x+1] 是该顺序中 b[1],b[2].... b[x] 的串联 . 同样的，
b[x+2] 是 b[2],b[3]....b[x],b[x+1] 的串联 .
所以，基本上， b[n] 将是 b[i] 的最后 x 项的连接，从右边开始 .
给出 p 和 q 作为查询的参数，如何找出 b[p] 中 b[p] 的 q 字符对应的哪个字符？

所有查询都修复 Note: x 和 b[1], b[2], b[3]..... b[x] .

我尝试了强制执行，但是对于大的x，字符串长度呈指数增长 . （x <= 100） .

Example:

当 x=3 时，

b[] = a, b, c, a b c, b c abc, c abc bcabc, abc bcabc cabcbcabc, //....  
//Spaces for clarity, only commas separate array elements

因此，对于 p=7 ， q=5 ，answer返回的查询将是 3 （对应于字符 'c' ） .

我只是很难搞清楚它背后的数学 . 语言没有问题

1 回答

1
当我想出来的时候，我写下了这个答案，所以请耐心等待 .

正如您所提到的，更容易找出 b[p][q] 中的字符来自原始 x 字符，而不是为大 p 生成 b[p] . 为此，我们将使用循环来查找当前 b[p][q] 的来源，从而减少 p ，直到它在 1 和 x 之间，并且 q 直到 1 为止 .

让我们看一下 x=3 的示例，看看我们是否可以得到一个公式：
```
p  N(p)  b[p]
-  ----  ----
1  1     a
2  1     b
3  1     c
4  3     a b c
5  5     b c abc
6  9     c abc bcabc
7  17    abc bcabc cabcbcabc
8  31    bcabc cabcbcabc abcbcabccabcbcabc
9  57    cabcbcabc abcbcabccabcbcabc bcabccabcbcabcabcbcabccabcbcabc
```
序列清晰： N(p) = N(p-1) + N(p-2) + N(p-3) ，其中 N(p) 是 b 的第p个元素中的字符数 . 给定 p 和 x ，您可以强制计算范围 [1, p] 的所有 N . 这将允许您找出 b b[p][q] 的哪个先前元素 .

为了说明，比如 x=3 ， p=9 和 q=45 .
- 上面的图表给出了 N(6)=9 ， N(7)=17 和 N(8)=31 . 自 45>9+17 以来，您知道 b[9][45] 来自 b[8][45-(9+17)] = b[8][19] .
- 迭代/递归地继续， 19>9+5 ，所以 b[8][19] = b[7][19-(9+5)] = b[7][5] .
- 现在 5>N(4) 但 5<N(4)+N(5) ，所以 b[7][5] = b[5][5-3] = b[5][2] .
- b[5][2] = b[3][2-1] = b[3][1]
- 自 3 <= x 以来，我们有终止条件， b[9][45] 是 c 来自 b[3] .
从 p ， q ， x 和 b 到 x 开始，可以非常容易地递归计算或者迭代计算这样的东西 . 我的方法需要 p 数组元素来计算整个序列的 N(p) . 如果递归地工作，这可以在数组中或在堆栈上分配 .

这是vanilla Python中的参考实现（没有外部导入，虽然numpy可能有助于简化这一点）：
```
def so38509640(b, p, q):
    """
    p, q are integers. b is a char sequence of length x.
    list, string, or tuple are all valid choices for b.
    """
    x = len(b)

    # Trivial case
    if p <= x:
        if q != 1:
            raise ValueError('q={} out of bounds for p={}'.format(q, p))
        return p, b[p - 1]

    # Construct list of counts
    N = [1] * p
    for i in range(x, p):
        N[i] = sum(N[i - x:i])
    print('N =', N)

    # Error check
    if q > N[-1]:
        raise ValueError('q={} out of bounds for p={}'.format(q, p))

    print('b[{}][{}]'.format(p, q), end='')

    # Reduce p, q until it is p < x
    while p > x:
        # Find which previous element character q comes from
        offset = 0
        for i in range(p - x - 1, p):
            if i == p - 1:
                raise ValueError('q={} out of bounds for p={}'.format(q, p))
            if offset + N[i] >= q:
                q -= offset
                p = i + 1
                print(' = b[{}][{}]'.format(p, q), end='')
                break
            offset += N[i]
    print()
    return p, b[p - 1]
```
调用 so38509640('abc', 9, 45) 产生
```
N = [1, 1, 1, 3, 5, 9, 17, 31, 57]
b[9][45] = b[8][19] = b[7][5] = b[5][2] = b[3][1]
(3, 'c') # <-- Final answer
```
同样，对于问题中的示例， so38509640('abc', 7, 5) 会产生预期结果：
```
N = [1, 1, 1, 3, 5, 9, 17]
b[7][5] = b[5][2] = b[3][1]
(3, 'c') # <-- Final answer
```
抱歉，我无法想出一个更好的函数名称:)这是一个简单的代码，它应该在Py2和3中同样有效，尽管 range 函数/类有差异 .

我很想知道是否存在针对此问题的非迭代解决方案 . 也许有一种方法可以使用模运算或其他方法来做到这一点......
回复于 2024-05-18T15:49:15+08:00

字符串连接查询

1 回答

相关问题