计算给定数字字符串连接 K 次后生成的字符串中 01 的子序列
字符串的分析和操作是计算机编程许多应用中的基本操作。计算给定数字字符串重复连接后生成的字符串中具有"01"模式的子序列是一个有趣的挑战。主要问题是确定结果字符串中此类子序列的总数。本文讨论了一种有用的 C++ 方法来成功解决此问题，并提供了一个可靠的答案来处理这一特定工作。
子序列的概念
在字符串操作和序列分析的上下文中，子序列是从其他序列中通过消除零个或多个字符而不改变剩余字符的相对顺序而得到的字符序列。换句话说，子序列是给定序列的子集，其中元素的顺序必须保持不变。
以下是有关子序列的重要事实:
保持顺序 - 子序列保持元素与初始序列的相对顺序。例如，如果原始序列是"19023"，则子序列可以是"923"，其中元素"9"、"2"和"3"是从原始序列中选择的，但仍然以相同的方式排列。
元素删除 - 通过从起始序列中一次删除某些元素来生成子序列。任何特定元素都可以包含在子序列中或排除在外。例如，第一个分组"190"中的潜在子序列包括"1"、"9"、"0"、"19"、"90"、"10"和"190"。
子序列的长度 − 子序列的长度范围可以从零(空子序列)到主序列的长度。这表明子序列可能比原始序列更短或长度相同。
非连续选择 − 与子字符串不同，序列不需要所选组件在原始序列中相邻。可以选择元素，只要它们的相对顺序得以保留。原始序列"1902"的一个子序列示例是"12"，其中元素"1"和"2"不相邻，但仍与原始序列的顺序相同。
示例
输入
S = "101" K = 2
输出
4
这里，给定的字符串重复了 k=2 次，因此通过连接
原始字符串 2 次，我们得到一个新字符串 = "101101"。
以下是"01"的 4 次出现:
第一个可能的子序列: 101101
第二个可能的子序列:101101
第三个可能的子序列:101101
第四个可能的子序列:101101
强力方法
解决以下问题的最简单方法是将原始字符串 str 连接 k 次以生成结果字符串。从那里，从字符串中找到所有可行的配对 (i, j)，使得 (i j) 和 str[i] = 0 和 str[j] = 1。
示例
#include <iostream>
#include <string>
using namespace std;
int count_subseq(string s, int k){
int s_len=s.length();
string s2="";
for (int z = 0; z < k; z++){
s2+=s;
}
int s2_len=s2.length();
int count=0;
int ans;
for(int i=0; i<s2_len;i++){
if(s2[i]=='0'){
for (int j = i+1; j < s2_len; j++){
if(s2[j]=='1' && i<j){
count=count+1;
}
}
}
}
return count;
}
int main(){
string str="1091";
int k=2;
int ans=count_subseq(str, k);
cout<<ans<<endl;
return 0;
}
输出
4
优化方法
设 S 为连接字符串，s 为原始字符串。
如果子序列"01"完全位于 S 中字符串 s 的单个出现内，则可以通过计算"01"在该特定 s 出现中的出现次数来获得 S 中"01"出现的次数。将此计数表示为 s_cnt。在这种情况下，S 中"01"出现的总次数将为 s_cnt*k。这是因为我们可以简单地将相同的"01"重复 k 次以形成 S。
否则，如果字母"0"严格位于 s 的一个出现内(假设为 si)，并且字母"1"位于 s 的其他出现内(假设为 sj)，使得 i < j，我们需要考虑 '0' 和 '1' 在 S 中各自位置的出现情况。
因此，在这种情况下，要找到 S 中"01"出现的次数，我们首先从总共 k 次出现中选择两次字符串 s(kC2 或 (k * (k − 1)) / 2)。这说明在 si 中选择一次 '0' 出现，在 sj 中选择一次 '1' 出现。
接下来，我们将这个计数乘以 si 中 '0' 出现的次数和 sj 中 '1' 出现的次数。
示例
#include <iostream>
#include <string>
using namespace std;
int subseq_cnt(string s, int len, int k){
// 存储原始字符串中存在的 0 和 1 的数量
int oneString_subseq_cnt = 0, ones_cnt = 0, zeros_cnt = 0;
// 计算原始字符串中存在的 1 和 0 的数量
for (int i = 0; i < len; i++){
if (s[i] == '1')
ones_cnt++;
else if (s[i] == '0')
zeros_cnt++;
}
// 不进行连接的情况下存在的子序列数量
int occurred_ones = 0;
for (int i = 0; i < len; i++){
if (s[i] == '1')
occurreded_ones++;
else if (s[i] == '0')
oneString_subseq_cnt += (ones_cnt - occurred_ones);
}
/* ans1= 不经过连接而形成的单个字符串 s 中的子序列 01 的数量。*/
int ans1 = oneString_subseq_cnt * k;
/* ans2= 考虑一次出现中的 0 和另一次出现中的 1 而形成的子序列 01 的数量。*/
int ans2 = ( zeros_cnt *ones_cnt * (((k) * (k - 1)) / 2));
// 返回连接后存在的总子序列
return ans1 + ans2;
}
int main(){
string str = "1091";
int k = 2;
int n = str.length();
cout << subseq_cnt(str, n, k);
return 0;
}
输出
4
测试用例
测试用例 -> "101"
0 和 1 的计数
对于给定的序列"101"，有 1 个"0"和 2 个"1"。
ones_cnt= 2
zeros_cnt= 1
无连接的子序列计数:
遍历序列并跟踪计数。每当遇到"0"时，将 1 的总计数与当前 1 的计数之间的差值添加到变量"oneString_subseq_cnt"中。
在给定的序列"101"中，索引 1 处有 1 个"0"。此时，ones_cnt= 1。因此，"oneString_subseq_cnt"增加 (ones_cnt − occurred_ones) = (1 − 0) = 1。
因此，oneString_subseq_cnt= 1
ans1:处理考虑连接的子序列计数。
ans1 = (oneString_subseq_cnt) * k = 1 * 2 = 2
ans2:处理考虑连接的子序列计数连接和组合。
ans2 = ( zeros_cnt* those_cnt *(((k) * (k − 1)) / 2))
ans2 = (2 * 1 * (((2) * (2 - 1)) / 2))
ans2 = (2 * 1 * 1)
ans2 = 2
因此，最终答案是 ans1+ ans2= 4。
结论
本文提供了一种 C++ 方法来确定将给定数字字符串连接 K 次后创建的字符串中有多少个具有模式"01"的子序列。可以使用提供的代码有效地确定最终连接字符串中所需子序列的实例数。该解决方案提供了一种可行的方法来处理该问题，并且可以在需要对连接字符串中的子序列进行计数的各种编程环境中使用。
