目录
方法一
算法
Example
输出
方法二
示例
首页 后端开发 C++ 计算将字符串分割为以偶数开头且最小长度为M的K个子字符串的方法数

计算将字符串分割为以偶数开头且最小长度为M的K个子字符串的方法数

Sep 09, 2023 pm 02:01 PM
字符串分割 方法数 偶数开头

计算将字符串分割为以偶数开头且最小长度为M的K个子字符串的方法数

在这个问题中,我们将计算将给定的字符串划分为K个子字符串的方法,使其满足问题陈述中给出的条件。

我们将使用递归来解决这个问题。此外,我们还将使用表格动态规划方法来高效解决这个问题。

问题陈述 − 我们有一个名为bin_Str的特定长度的字符串。该字符串只包含从'0'到'9'的数字字符。我们需要计算将字符串分割成K个子字符串的方式数,使其满足以下条件。

  • 子字符串应至少包含2个字符。

  • 每个子字符串的第一个字符应为偶数,最后一个字符应为奇数。

示例示例

输入

M = 2, K = 2; bin_str = "255687"
登录后复制

Output

1
登录后复制

Explanation − 根据问题陈述的条件,我们可以将255 | 687分割成给定字符串的一部分。

输入

M = 2, K = 2; bin_str = "26862";
登录后复制

Output

0
登录后复制

解释 − 由于字符串只包含偶数数字,我们无法将其分割成两个子字符串,使得每个子字符串以奇数数字结尾。

输入

M = 2, K = 3; bin_str = "856549867";
登录后复制

输出

3
登录后复制

Explanation − 可能的分区方式有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’的值。

Example

#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 的全局矩阵 matrix[] 数组。矩阵的行映射到一个字符串字符,矩阵的列映射到 K。

第二步 − 取字符串的第一个和最后一个字符。如果第一个字符是偶数且最后一个字符是奇数,则执行countWays()函数。否则,在输出中打印0。

步骤 3 − 在 countWays 函数中,初始化 matrix[] 数组。

步骤 4 − 遍历矩阵的行数等于字符串长度,列数等于K。如果行数等于字符串长度,则将整行更新为0。

步骤5 − 否则,如果q为1,并且字符串长度减去当前索引大于M,则用1初始化数组matrix[p][q]。否则,用0初始化matrix[p][q]。

步骤 6 − 在其他情况下,将矩阵[p][q]初始化为-1。

第7步− 使用两个嵌套循环填充矩阵。使用外部循环进行2到K的遍历,使用嵌套循环进行0到字符串长度的遍历。

第8步 - 将'ops'和'len'初始化为0。此外,从第p个索引开始遍历字符串,并在每次迭代中将'len'增加1。

第9步 − 取出字符串的当前字符和下一个字符。

第10步− 如果长度大于M,当前字符是奇数,并且下一个字符是偶数,则将matrix[k + 1][q − 1]添加到'ops'中。

第11步− 使用‘ops’更新矩阵[p][q]。

第12步− 最后返回matrix[0][k]。

Example

的中文翻译为:

示例

#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 个分区。

空间复杂度 - 使用matrix[]数组为O(N*K)。

以上是计算将字符串分割为以偶数开头且最小长度为M的K个子字符串的方法数的详细内容。更多信息请关注PHP中文网其他相关文章!

本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
2 周前 By 尊渡假赌尊渡假赌尊渡假赌
仓库:如何复兴队友
4 周前 By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒险:如何获得巨型种子
3 周前 By 尊渡假赌尊渡假赌尊渡假赌

热工具

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

Python 3.x 中如何使用split()函数将字符串按照指定分隔符分割 Python 3.x 中如何使用split()函数将字符串按照指定分隔符分割 Jul 31, 2023 pm 08:33 PM

Python是一种流行的编程语言,它提供了许多内置函数来处理字符串。其中一个常用的函数是split()函数,可以按照指定的分隔符将字符串分割成多个子串。本文将介绍如何在Python3.x中使用split()函数。在Python中,split()函数是字符串类的一个内置函数,它的基本语法如下:string.split(separator,maxsplit)

字符串的最大分割长度,使得字符串中的每个字符都出现在一个子字符串中 字符串的最大分割长度,使得字符串中的每个字符都出现在一个子字符串中 Aug 25, 2023 pm 02:41 PM

在本文中,我们将探讨如何找到具有唯一字符的字符串的最大化分区的长度问题。我们首先了解问题陈述,然后研究解决这个问题的朴素和高效方法,包括它们各自的算法和时间复杂度。最后,我们将在C++中实现解决方案。问题陈述给定一个字符串,将字符串分割为尽可能多的子字符串,使得字符串中的每个字符只出现在一个子字符串中。返回这些最大化分割的长度。天真的方法天真的方法是通过字符串迭代,记录每个字符的最后出现位置。然后,再次迭代字符串,并在找到当前字符的最后出现位置时创建分区。算法(朴素)初始化一个数组以存储字符串中

检查一个字符串是否可以被分割成三个子字符串,其中一个子字符串是另外两个子字符串的子串 检查一个字符串是否可以被分割成三个子字符串,其中一个子字符串是另外两个子字符串的子串 Sep 22, 2023 am 11:53 AM

在这个问题中,我们需要分割给定的字符串,使得第三个子字符串可以是前两个子字符串的子字符串。让我们想想解决办法。仅当前两个字符串包含第三个字符串的所有字符时,第三个字符串才可以是前两个字符串的子字符串。所以,我们需要在给定的字符串中找到至少一个出现频率大于3的字符,并且我们可以取该单个字符的第三个子串。问题陈述-我们给出了一个包含N个小写字母字符的字符串str。我们需要检查是否可以将字符串拆分为三个子字符串a、b和c,使得子字符串c是a和b的子字符串。根据是否能找到3个子串,打印“yes”或“no

计算将字符串分割为以偶数开头且最小长度为M的K个子字符串的方法数 计算将字符串分割为以偶数开头且最小长度为M的K个子字符串的方法数 Sep 09, 2023 pm 02:01 PM

在这个问题中,我们将计算将给定的字符串划分为K个子字符串的方法,使其满足问题陈述中给出的条件。我们将使用递归来解决这个问题。此外,我们还将使用表格动态规划方法来高效解决这个问题。问题陈述−我们有一个名为bin_Str的特定长度的字符串。该字符串只包含从'0'到'9'的数字字符。我们需要计算将字符串分割成K个子字符串的方式数,使其满足以下条件。子字符串应至少包含2个字符。每个子字符串的第一个字符应为偶数,最后一个字符应为奇数。示例示例输入M=2,K=2;bin_str="255687&q

PHP字符串函数实例:字符串分割 PHP字符串函数实例:字符串分割 Jun 20, 2023 pm 01:58 PM

PHP中有许多字符串函数,其中字符串分割函数是非常常用的。字符串分割函数可以将一个字符串按照指定的分隔符进行分割,并返回一个数组。下面我们就来介绍几个常用的字符串分割函数。explode函数explode函数可以将字符串按照指定的分隔符进行分割,并返回一个数组。其语法如下:explode(string$separator,string$string

如何在PHP中将字符串分割为数组 如何在PHP中将字符串分割为数组 Jul 08, 2023 pm 01:49 PM

如何在PHP中将字符串分割为数组在PHP中,我们经常需要处理字符串,并将其拆分为多个部分。将字符串分割为数组是一种常见的操作,可以帮助我们更好地处理字符串的各个部分。在本文中,我们将学习如何使用PHP中的函数将字符串分割为数组,并提供一些代码示例。使用explode函数将字符串分割为数组PHP提供了一个名为explode的函数,可以将字符串按照指定的分隔符进

解决PHP中explode函数报错的方法 解决PHP中explode函数报错的方法 Mar 11, 2024 am 11:45 AM

解决PHP中explode函数报错的方法,需要具体代码示例在PHP中,explode函数是用于将字符串按照指定的分隔符拆分成数组的函数。然而,有时候在使用explode函数时会出现报错的情况,主要是因为传入的参数不符合函数的要求所导致的。下面我们将针对可能出现的问题和解决方法进行详细讨论,并且提供具体的代码示例。参数个数错误导致的报错当使用explode函数

PHP中如何使用explode函数分割字符串 PHP中如何使用explode函数分割字符串 Jun 26, 2023 pm 12:03 PM

在PHP语言中,有很多基础函数可以帮我们快速有效地处理字符串。其中,explode函数是一个很实用的字符串分割函数。它可以将一个字符串按照指定的分割符分割成数组,进而进行更为灵活的字符串操作。在本文中,我们将会介绍PHP中如何使用explode函数来分割字符串。一、explode函数格式explode函数在PHP语言中的格式如下:explode(separa

See all articles