在这个问题中,我们将计算将给定的字符串划分为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中文网其他相关文章!

C XML框架的选择应基于项目需求。1)TinyXML适合资源受限环境,2)pugixml适用于高性能需求,3)Xerces-C 支持复杂的XMLSchema验证,选择时需考虑性能、易用性和许可证。

C#适合需要开发效率和类型安全的项目,而C 适合需要高性能和硬件控制的项目。 1)C#提供垃圾回收和LINQ,适用于企业应用和Windows开发。 2)C 以高性能和底层控制着称,广泛用于游戏和系统编程。

C 代码优化可以通过以下策略实现:1.手动管理内存以优化使用;2.编写符合编译器优化规则的代码;3.选择合适的算法和数据结构;4.使用内联函数减少调用开销;5.应用模板元编程在编译时优化;6.避免不必要的拷贝,使用移动语义和引用参数;7.正确使用const帮助编译器优化;8.选择合适的数据结构,如std::vector。

C 中的volatile关键字用于告知编译器变量值可能在代码控制之外被改变,因此不能对其进行优化。1)它常用于读取可能被硬件或中断服务程序修改的变量,如传感器状态。2)volatile不能保证多线程安全,应使用互斥锁或原子操作。3)使用volatile可能导致性能slight下降,但确保程序正确性。

在C 中测量线程性能可以使用标准库中的计时工具、性能分析工具和自定义计时器。1.使用库测量执行时间。2.使用gprof进行性能分析,步骤包括编译时添加-pg选项、运行程序生成gmon.out文件、生成性能报告。3.使用Valgrind的Callgrind模块进行更详细的分析,步骤包括运行程序生成callgrind.out文件、使用kcachegrind查看结果。4.自定义计时器可灵活测量特定代码段的执行时间。这些方法帮助全面了解线程性能,并优化代码。

使用C 中的chrono库可以让你更加精确地控制时间和时间间隔,让我们来探讨一下这个库的魅力所在吧。C 的chrono库是标准库的一部分,它提供了一种现代化的方式来处理时间和时间间隔。对于那些曾经饱受time.h和ctime折磨的程序员来说,chrono无疑是一个福音。它不仅提高了代码的可读性和可维护性,还提供了更高的精度和灵活性。让我们从基础开始,chrono库主要包括以下几个关键组件:std::chrono::system_clock:表示系统时钟,用于获取当前时间。std::chron

C 在实时操作系统(RTOS)编程中表现出色,提供了高效的执行效率和精确的时间管理。1)C 通过直接操作硬件资源和高效的内存管理满足RTOS的需求。2)利用面向对象特性,C 可以设计灵活的任务调度系统。3)C 支持高效的中断处理,但需避免动态内存分配和异常处理以保证实时性。4)模板编程和内联函数有助于性能优化。5)实际应用中,C 可用于实现高效的日志系统。

C 中的ABI兼容性是指不同编译器或版本生成的二进制代码能否在不重新编译的情况下兼容。1.函数调用约定,2.名称修饰,3.虚函数表布局,4.结构体和类的布局是主要涉及的方面。


热AI工具

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

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

Undress AI Tool
免费脱衣服图片

Clothoff.io
AI脱衣机

Video Face Swap
使用我们完全免费的人工智能换脸工具轻松在任何视频中换脸!

热门文章

热工具

SublimeText3汉化版
中文版,非常好用

PhpStorm Mac 版本
最新(2018.2.1 )专业的PHP集成开发工具

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

mPDF
mPDF是一个PHP库,可以从UTF-8编码的HTML生成PDF文件。原作者Ian Back编写mPDF以从他的网站上“即时”输出PDF文件,并处理不同的语言。与原始脚本如HTML2FPDF相比,它的速度较慢,并且在使用Unicode字体时生成的文件较大,但支持CSS样式等,并进行了大量增强。支持几乎所有语言,包括RTL(阿拉伯语和希伯来语)和CJK(中日韩)。支持嵌套的块级元素(如P、DIV),

EditPlus 中文破解版
体积小,语法高亮,不支持代码提示功能