数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学计算由给定数字字符串连接K次生成的字符串中“01”子序列的个数
在许多计算机编程应用中，字符串的分析和处理是基本操作。计算由给定数字字符串重复连接K次生成的字符串中“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"。
以下是 4 个“01”的出现：
第一个可能的子序列：101101
第二个可能的子序列：101101
第三个可能的子序列：101101
第四个可能的子序列：101101
暴力法
解决这个问题最简单的方法是将原始字符串 str 连接 k 次以生成结果字符串。从那里，找到字符串中所有可能的配对 (i, j)，使得 (i < j) 且 str[i] = 0 且 str[j] = 1。
示例
以下是上述方法在不同编程语言中的实现：C、C++、Java 和 Python：
#include <stdio.h>
#include <string.h>
int count_subseq(char s[], int k) {
int s_len = strlen(s);
char s2[1000] = "";
for (int z = 0; z < k; z++) {
strcat(s2, s);
}
int s2_len = strlen(s2);
int count = 0;
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() {
char str[] = "1091";
int k = 2;
int ans = count_subseq(str, k);
printf("%d\n", ans);
return 0;
}
输出
4
#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
public class SubsequenceCount {
static int countSubseq(String s, int k) {
StringBuilder s2 = new StringBuilder();
for (int z = 0; z < k; z++) {
s2.append(s);
}
int s2Len = s2.length();
int count = 0;
for (int i = 0; i < s2Len; i++) {
if (s2.charAt(i) == '0') {
for (int j = i + 1; j < s2Len; j++) {
if (s2.charAt(j) == '1' && i < j) {
count++;
}
}
}
}
return count;
}
public static void main(String[] args) {
String str = "1091";
int k = 2;
int ans = countSubseq(str, k);
System.out.println(ans);
}
}
输出
4
def count_subseq(s, k):
s2 = ""
for z in range(k):
s2 += s
s2_len = len(s2)
count = 0
for i in range(s2_len):
if s2[i] == '0':
for j in range(i + 1, s2_len):
if s2[j] == '1' and i < j:
count += 1
return count
if __name__ == "__main__":
str_val = "1091"
k_val = 2
ans_val = count_subseq(str_val, k_val)
print(ans_val)
输出
4
优化方法
令 S 为连接后的字符串，s 为原始字符串。
如果子序列“01”完全位于 S 中字符串 s 的单个出现内，则可以通过计算 s 中“01”出现的次数来获得 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' 的出现次数。
示例
以下是上述方法在不同编程语言中的实现：C、C++、Java 和 Python：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int subseq_cnt(char s[], int len, int k){
// storing the count of 0's and 1's present in the original string
int oneString_subseq_cnt = 0, ones_cnt = 0, zeros_cnt = 0;
// calculating the number of 1s and 0s present in the original string
for (int i = 0; i < len; i++){
if (s[i] == '1')
ones_cnt++;
else if (s[i] == '0')
zeros_cnt++;
}
// Count of subsequences present without doing concatenation
int occured_ones = 0;
for (int i = 0; i < len; i++){
if (s[i] == '1')
occured_ones++;
else if (s[i] == '0')
oneString_subseq_cnt += (ones_cnt - occured_ones);
}
/* ans1= number of subsequences 01 formed witnin a single string s without concatenating.*/
int ans1 = oneString_subseq_cnt * k;
/* ans2= number of subsequences 01 formed by considering 0 in one occurence and 1 in other occurence.*/
int ans2 = ( zeros_cnt *ones_cnt * (((k) * (k - 1)) / 2));
// Return the total subsequences present after concatenation
return ans1 + ans2;
}
int main(){
char str[] = "1091";
int k = 2;
int n = strlen(str);
printf("%d", subseq_cnt(str, n, k));
return 0;
}
输出
4
#include <iostream>
#include <string>
using namespace std;
int subseq_cnt(string s, int len, int k){
// storing the count of 0's and 1's present in the original string
int oneString_subseq_cnt = 0, ones_cnt = 0, zeros_cnt = 0;
// calculating the number of 1s and 0s present in the original string
for (int i = 0; i < len; i++){
if (s[i] == '1')
ones_cnt++;
else if (s[i] == '0')
zeros_cnt++;
}
// Count of subsequences present without doing concatenation
int occured_ones = 0;
for (int i = 0; i < len; i++){
if (s[i] == '1')
occured_ones++;
else if (s[i] == '0')
oneString_subseq_cnt += (ones_cnt - occured_ones);
}
/* ans1= number of subsequences 01 formed witnin a single string s without concatenating.*/
int ans1 = oneString_subseq_cnt * k;
/* ans2= number of subsequences 01 formed by considering 0 in one occurence and 1 in other occurence.*/
int ans2 = ( zeros_cnt *ones_cnt * (((k) * (k - 1)) / 2));
// Return the total subsequences present after concatenation
return ans1 + ans2;
}
int main(){
string str = "1091";
int k = 2;
int n = str.length();
cout << subseq_cnt(str, n, k);
return 0;
}
输出
4
public class SubsequenceCount {
static int subseqCnt(String s, int len, int k) {
// storing the count of 0's and 1's present in the original string
int oneStringSubseqCnt = 0, onesCnt = 0, zerosCnt = 0;
for (int i = 0; i < len; i++) {
if (s.charAt(i) == '1')
onesCnt++;
else if (s.charAt(i) == '0')
zerosCnt++;
}
// Count of subsequences present without doing concatenation
int occuredOnes = 0;
for (int i = 0; i < len; i++) {
if (s.charAt(i) == '1')
occuredOnes++;
else if (s.charAt(i) == '0')
oneStringSubseqCnt += (onesCnt - occuredOnes);
}
/* ans1= number of subsequences 01 formed witnin a single string s without concatenating.*/
int ans1 = oneStringSubseqCnt * k;
int ans2 = (zerosCnt * onesCnt * (((k) * (k - 1)) / 2));
// Return the total subsequences present after concatenation
return ans1 + ans2;
}
public static void main(String[] args) {
String str = "1091";
int k = 2;
int n = str.length();
System.out.println(subseqCnt(str, n, k));
}
}
输出
4
def subseq_cnt(s, len, k):
#storing the count of 0's and 1's present in the original string
one_string_subseq_cnt = 0
ones_cnt = 0
zeros_cnt = 0
for i in range(len):
if s[i] == '1':
ones_cnt += 1
elif s[i] == '0':
zeros_cnt += 1
# Count of subsequences present without doing concatenation
occured_ones = 0
for i in range(len):
if s[i] == '1':
occured_ones += 1
elif s[i] == '0':
one_string_subseq_cnt += (ones_cnt - occured_ones)
# ans1= number of subsequences 01 formed witnin a single string s without concatenating.
ans1 = one_string_subseq_cnt * k
#ans2= number of subsequences 01 formed by considering 0 in one occurence and 1 in other occurence.
ans2 = (zeros_cnt * ones_cnt * (((k) * (k - 1)) // 2))
# Return the total subsequences present after concatenation
return ans1 + ans2
if __name__ == "__main__":
str_val = "1091"
k_val = 2
n_val = len(str_val)
print(subseq_cnt(str_val, n_val, k_val))
输出
4
测试用例
Test case → "101"
0 和 1 的个数
对于给定的序列“101”，'0' 出现 1 次，'1' 出现 2 次。
ones_cnt= 2 zeros_cnt= 1
无连接的子序列个数
遍历序列并跟踪计数。每当遇到 '0' 时，将 1 的总数与 1 的当前计数之间的差值添加到变量 'oneString_subseq_cnt'。
在给定的序列“101”中，在索引 1 处有一个 '0'。此时，ones_cnt= 1。因此，'oneString_subseq_cnt' 增加 (ones_cnt − occured_ones) = (1 − 0) = 1。
所以，oneString_subseq_cnt= 1
ans1 - 处理考虑连接的子序列计数。
ans1 = (oneString_subseq_cnt) * k = 1 * 2 = 2
ans2 - 处理考虑连接和组合的子序列计数。
ans2 = (zeros_cnt * ones_cnt * (((k) * (k − 1)) / 2))
ans2 = (2 * 1 * (((2) * (2 - 1)) / 2))
ans2 = (2 * 1 * 1)
ans2 = 2
因此，最终答案是 ans1 + ans2 = 4。
结论
本文提供了一种 C++ 方法来确定在将给定数字字符串连接 K 次生成的字符串中，“01”模式子序列的个数。可以使用提供的代码有效地确定最终连接字符串中所需子序列的出现次数。此解决方案提供了一种可行的处理问题的方法，并可用于需要在连接字符串中计算子序列的各种编程环境中。
浏览量：137
