資料結構
網路
關係資料庫管理系統 (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
