数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学统计将字符串拆分为以偶数数字开头且最小长度为M的K个子字符串的方法数
在这个问题中，我们将统计将给定字符串划分为K个子字符串的方法数，这些子字符串符合问题陈述中给出的条件。
我们将使用递归来解决这个问题。此外，我们将使用表格动态规划方法来有效地解决这个问题。
问题陈述 - 我们给定一个名为bin_Str的特定长度的字符串。该字符串仅包含从'0'到'9'的数字。我们需要统计将字符串划分为K个子字符串的方法数，这些子字符串符合以下条件。
子字符串至少应包含2个字符。
每个子字符串的第一个字符应为偶数数字，最后一个字符应为奇数数字。
示例
输入
M = 2, K = 2; bin_str = "255687"
输出
1
解释 - 根据问题陈述的条件，我们只能将给定字符串划分为255 | 687。
输入
M = 2, K = 2; bin_str = "26862";
输出
0
解释 - 由于字符串只包含偶数数字，因此我们无法将其拆分为2个子字符串，每个子字符串都以奇数数字结尾。
输入
M = 2, K = 3; bin_str = "856549867";
输出
3
解释 -可能的划分方法有85|65|49867、8565|49|867和85|6549|867。
方法一
我们将使用递归函数来解决此方法中的问题。如果我们在当前索引处找到有效的子字符串，我们将进行递归调用以统计将剩余子字符串划分为K-1个子字符串的方法数。
算法
步骤1 - 获取给定字符串的首字符和尾字符。
步骤2 - 如果首字符不是偶数且尾字符不是奇数，则返回0。
步骤3 - 如果起始索引等于字符串长度，则返回0，因为我们到达了给定字符串的末尾。
步骤4 - 如果K == 1，则取字符串长度和起始索引的差值。如果它等于或大于M，则返回1。否则，返回0。在这里，我们需要获取剩余的子字符串，如果K为1。
步骤5 - 将'ops'初始化为'0'以存储划分方法的数量，将'len'初始化为'0'以存储当前子字符串的长度。
步骤6 - 从'start'索引开始遍历字符串到字符串的末尾。
步骤7 - 将'len'加1。此外，获取当前字符和下一个字符。
步骤8 - 如果'len'大于M，当前数字是奇数，下一个数字是偶数，我们可以在当前索引处结束划分。因此，通过传递下一个索引和K-1作为函数参数来进行countWays()函数的递归调用。
步骤9 - 最后，返回'ops'值。
示例
#include <bits/stdc++.h>
using namespace std;
int countWays(int start, int str_len, int K, int M, string bin_str) {
// Geeting first and last character of the substring
int f_char = bin_str[0] - '0';
int l_char = bin_str[str_len - 1] - '0';
if (f_char % 2 != 0 || l_char % 2 != 1) {
return 0;
}
// When we reach at the end
if (start == str_len)
return 0;
// Base case
if (K == 1) {
int chars = str_len - start;
// Validate minimum length of substring
if (chars >= M)
return 1;
return 0;
}
int ops = 0;
int len = 0;
// Traverse all partions
for (int p = start; p < str_len - 1; p++) {
len++;
int first = bin_str[p] - '0';
int second = bin_str[p + 1] - '0';
// If we can end the partition at p and start a new partition at p+1
if (len >= M && first % 2 == 1) {
if (second % 2 == 0) {
ops += countWays(p + 1, str_len, K - 1, M, bin_str);
}
}
}
return ops;
}
int main() {
int M = 2, K = 2;
string bin_str = "255687";
int str_len = bin_str.length();
cout << "The number of ways to split the string is " << countWays(0, str_len, K, M, bin_str) << endl;
return 0;
}
输出
The number of ways to split the string is 1
拆分字符串的方法数为1
空间复杂度 - O(1)，因为我们不使用额外的空间。
方法二
在此方法中，我们将使用表格动态规划技术来统计将字符串划分为K个分区的数量。我们将使用矩阵来存储先前状态的输出。
算法
步骤1 - 定义大小为1001 x 1001的全局矩阵[]数组。矩阵行映射到字符串字符，矩阵列映射到K。
步骤2 - 获取字符串的首字符和尾字符。如果首字符为偶数且尾字符为奇数，则执行countWays()函数。否则，在输出中打印0。
步骤3 - 在countWays函数中，初始化矩阵[]数组。
步骤4 - 遍历等于字符串长度的行和等于K的列的矩阵。如果行等于字符串长度，则将整行更新为0。
步骤5 - 否则，如果q为1，并且字符串长度-当前索引大于M，则将数组matrix[p][q]初始化为1。否则，将matrix[p][q]初始化为0。
步骤6 - 在其他情况下，将matrix[p][q]初始化为-1。
步骤7 - 使用两个嵌套循环填充矩阵。使用外循环进行2到K的遍历，使用内循环进行0到字符串长度的遍历。
步骤8 - 将'ops'和'len'初始化为0。此外，从第p个索引开始遍历字符串，在每次迭代中将'len'加1。
步骤9 - 获取字符串的当前字符和下一个字符。
步骤10 - 如果长度大于M，当前字符为奇数，下一个字符为偶数，则将matrix[k + 1][q − 1]添加到'ops'。
步骤11 - 将matrix[p][q]更新为'ops'。
步骤12 - 最后返回matrix[0][k]。
示例
#include <bits/stdc++.h>
using namespace std;
int matrix[1001][1001];
int countWays(int str_len, int K, int M, string bin_str) {
// Base case
for (int p = 0; p <= str_len; p++) {
for (int q = 0; q <= K; q++) {
// When index points to end index of string
if (p == str_len)
matrix[p][q] = 0;
else if (q == 1) {
// When only 1 split needs to be done
int chars = str_len - p;
// Validating substring's minimum len
if (chars >= M)
matrix[p][q] = 1;
else
matrix[p][q] = 0;
} else {
// For other cases
matrix[p][q] = -1;
}
}
}
// Dynamic programming approach
for (int q = 2; q <= K; q++) {
for (int p = 0; p < str_len; p++) {
int ops = 0;
int len = 0; // length of current substring
for (int k = p; k < str_len - 1; k++) {
len++;
int first = bin_str[k] - '0';
int second = bin_str[k + 1] - '0';
// Validate condition for split
if (len >= M && first % 2 == 1 && second % 2 == 0) {
// Substring starting from k + 1 index needs to be splited in q-1 parts
ops += matrix[k + 1][q - 1];
}
}
matrix[p][q] = ops;
}
}
return matrix[0][K];
}
int main() {
int M = 2, K = 2;
string bin_str = "255687";
int str_len = bin_str.length();
int f_char = bin_str[0] - '0';
int l_char = bin_str[str_len - 1] - '0';
cout << "The number of ways to split the string is ";
if (f_char % 2 != 0 || l_char % 2 != 1) {
cout << 0 << endl;
} else {
cout << countWays(str_len, K, M, bin_str) << endl;
}
return 0;
}
输出
The number of ways to split the string is 1
时间复杂度 - O(N*N*K)，其中O(N*N)用于查找所有子字符串，O(K)用于K个分区。
空间复杂度 - O(N*K) 用于使用矩阵[]数组。
224 次浏览
