1

假设我有一个字符串，其字符只是 [0 - 9] 范围内的数字。例如：“2486”。现在我想找出所有数字之和可以被6整除的子序列。例如：在“2486”中，子序列是-“6”，“246”（2+ 4 + 6 = 12可以被6整除）， “486”（4 + 8 + 6 = 18 可被 6 整除）等。我知道生成所有 2^n 组合我们可以做到这一点。但这是非常昂贵的。最有效的方法是什么？

编辑：

我在quora的某个地方找到了以下解决方案。

int len,ar[MAXLEN],dp[MAXLEN][MAXN];

int fun(int idx,int m)

{

    if(idx==len)

        return (m==0);

    if(dp[idx][m]!=-1)

        return dp[idx][m];

    int ans=fun(idx+1,m);

    ans+=fun(idx+1,(m*10+ar[idx])%n);

    return dp[idx][m]=ans;

}

int main()

{

    // input len , n , array

    memset(dp,-1,sizeof(dp));

    printf("%d\n",fun(0,0));            

    return 0;

}

有人可以解释一下代码背后的逻辑 - 'm*10+ar[idx])%n' 吗？为什么这里 m 乘以 10？

4

3 回答 3

1

假设您有一个 16 位的序列，您可以生成所有 2 16个子序列并测试它们，即 65536 次操作。

或者您可以取前 8 位数字并生成 2 8个可能的子序列，并根据它们的和模 6 的结果对它们进行排序，并对最后 8 位数字执行相同的操作。这只是 512 次操作。

然后，您可以生成原始 16 位字符串的所有子序列，这些子序列可被 6 整除，方法是将第一个列表的每个子序列取模值等于 0（包括空子序列）并将其与最后一个列表的每个子序列连接起来模值等于 0。

然后取第一个列表的每个子序列，其模值为 1，并将其与最后一个列表的每个子序列连接，其模值为 5。然后 2 与 4、3 与 3、4 与 2 和 5 与 1。

因此，在 512 次操作的初始成本之后，您可以只生成总和可被 6 整除的子序列。您可以递归地将此算法应用于更大的序列。

于 2015-07-08T04:14:57.107 回答
0

为字符串中的每个位置创建一个包含 6 位位图的数组。从右到左工作并设置位图数组，以便当从数组之后的某个子序列开始时，位图在数组中设置位，这些子序列在位图中的该位置相加。您可以使用当前位置之后的位图从右到左执行此操作。如果您看到 3 并且在当前位置之后的位图是 010001，则只需跳过 3 就可以访问总和 1 和 5。使用 3 总和 4 和 2 现在可用，因此新位图是 011011。

现在对从左到右的子序列进行深度优先搜索，每个字符的选择是取那个字符还是不取那个字符。当您这样做时，请跟踪到目前为止所拍摄字符的 mod 6 总和。使用位图计算该位置右侧是否有一个子序列，加到目前的总和中，结果为零。只要您可以看到当前和导致和为零的子序列，就继续进行，否则停止并递归。

第一阶段的成本与输入的大小成线性关系（对于固定值 6）。第二阶段的成本与产生的子序列数量成线性关系。事实上，如果您必须实际写出访问过的子序列（例如，通过维护显式堆栈并写出堆栈的内容），那将是程序中最昂贵的部分。

当所有 2^n 个子序列都有效时，最坏的情况当然是输入 000000...0000。

于 2015-07-08T04:47:57.687 回答
0

我很确定一个名为 amit 的用户最近回答了一个类似的关于组合的问题，而不是除数为 4 的子序列，尽管我现在找不到它。在这种情况下，他的答案是创建五个数组（称为它们Array_i），O(n)其中每个数组包含i与 6 具有模关系的数组元素。对于子序列，我们还需要一种记录元素顺序的方法。例如，在您的情况下2486，我们的数组可能是：

Array_0 = [null,null,null,6]
Array_1 = []
Array_2 = [null,4,null,null]
Array_3 = []
Array_4 = [2,null,8,null]
Array_5 = []

现在只需交叉组合适当的数组，保持元素顺序：Array_0、Array_2 和 Array_4、Array_0 和任何其他数组组合：

6, 24, 48, 246, 486
于 2015-07-08T17:05:29.260 回答