数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学在最多花费 k 的情况下，最大可能的平衡二叉子串分割数
C语言中的数组大小是固定的，这意味着一旦指定了大小，就不能更改；既不能缩小也不能扩展。
众所周知，数组是一组相同数据类型的元素，存储在连续的内存区域中。
给定一个值数组 v[] 和一个二进制数组 a[]。目标是使用最多 k 个硬币尽可能多地划分二进制数组，同时确保每个段的 0 和 1 的数量相等。i 和 j 是分割段相邻的索引，每次分割的成本是 (v[i] - v[j])²。
问题陈述
实现一个程序，查找在最多花费 k 的情况下，最大可能的平衡二叉子串分割数。
示例 1
Let the Input array be: a: [1,0,0, 1, 0, 0, 1, 1] The given values be: v: [7, 8, 9, 10, 11, 12,13,14] K: 1
输出结果：1
解释
因为 K 的值为 1，所以我们可以在第一个和第二个索引之间进行一次分割。
在这种情况下，[0, 1] 和 [0, 0, 1, 1] 是最终得到的平衡二叉子串。
进行此分割的成本为 (8 - 9)² = 1，并且 1 = 1。
示例 2
Let the Input array be: a: [1,0 1, 0, 1, 1, 0,0] The given values be: v: [2, 4, 7, 10, 11, 12, 13, 14] K: 14
Output obtained is: 2
解释
第一次分割将在第一个和第二个索引（即 4 和 7）之间进行，成本为 (4 - 7)² = 9；第二次分割将在第三个和第四个索引（即 7 和 10）之间进行，成本为 (7 - 10)² = 9。目前无法进行更多分割。在这种情况下，产生的平衡二叉子串为 [1, 0]，[1, 0] 和 [1, 1, 0, 0]。
方法
为了找到在最多花费 k 的情况下，最大可能的平衡二叉子串分割数，我们采用以下方法。
这里我们采用自顶向下的方法来解决这个问题，并找到在最多花费 k 的情况下，最大可能的平衡二叉子串分割数。
谈到自顶向下方法，也就是广为人知的动态规划方法。动态规划的主要优点是改进了简单的递归。动态规划可用于优化任何包含对相同输入的重复调用的递归解决方案。其思想是仅存储子问题的结果，以避免以后重新计算它们。通过这种简单的优化，时间复杂度从多项式减少到指数。
算法
下面给出在最多花费 K 的情况下查找最大可能的平衡二叉子串分割数的算法。
步骤 1 − 开始
步骤 2 − 定义一个二维矩阵 m
步骤 3 − 定义一个函数来查找最大可能的平衡二叉子串分割数。
步骤 4 − 定义整数变量 zeroCount 来计数 0 的数量，以及 integer 变量 oneCount 来计数 1 的数量。
步骤 5 − 定义一个整数变量 cntSplits 来计数分割的数量。
步骤 6 − 遍历给定的数组 a
步骤 7 − 检查 0 的数量是否等于 1 的数量，然后存储最大可行值。
步骤 8 − 假设索引位于位置 0，则查找它是 1 还是 0，然后递增计数。
步骤 9 − 如果 1 的计数和 0 的计数不相等，则将 cntSplits 设置为零。
步骤 10 − 将结果值存储在矩阵中。
步骤 11 − 打印获得的期望结果。
步骤 12 − 结束
示例：C程序
这是上面编写的算法的 C 语言程序实现，用于在最多花费 k 的情况下查找最大可能的平衡二叉子串分割数。
#include <stdio.h>
#include <limits.h>
#include <string.h>
//Define a two-dimensional matrix m
int m[1001][1001];
//Define a function to find maximum possible //balanced binary substring splits
int maxSplits(int a[], int v[], int k, int s) {
if (k < 0) {
return INT_MIN;
}
if (m[k][s] != -1) {
return m[k][s];
}
//Define integer variables to count the number of zeros and ones
// Define an integer variable to count the //number of splits
int zeroCount = 0, oneCount = 0;
int cntSplits = 0;
int i;
//Iterating through the given array a
for (i = s - 1; i > 0; i--) {
a[i] == 0 ? zeroCount++ : oneCount++;
// check whether the number of zeros is equal to the number of ones, then store the maximum feasible one
if (zeroCount == oneCount) {
cntSplits = cntSplits > (1 + maxSplits(a, v, k - (v[i] - v[i - 1]) * (v[i] - v[i - 1]), i)) ? cntSplits : (1 + maxSplits(a, v, k - (v[i] - v[i - 1]) * (v[i] - v[i - 1]), i));
}
}
//Suppose the index is at the position 0, then find whether it is a one or a zero. then increment the count
if (i == 0) {
a[0] == 0 ? zeroCount++ : oneCount++;
// set the cntSplits to zero , if count of one and count of zero is unequal.
if (zeroCount != oneCount) {
cntSplits = 0;
}
}
// store the resultant value in the matrix
return m[k][s] = cntSplits;
}
int main() {
int a[] = { 1, 0, 0, 1, 0, 0, 1, 1 };
int v[] = { 7, 8, 9, 10, 11, 12, 13, 14 };
int k = 1;
int s = sizeof(a) / sizeof(a[0]);
//To assign a specific value to a block of memory, we use the memset() function.
memset(m, -1, sizeof(m));
printf("%d\n", maxSplits(a, v, k, s));
return 0;
}
输出
1
结论
同样，我们可以找到在最多花费 K 的情况下，最大可能的平衡二叉子串分割数。
本文解决了获取程序以在最多花费 K 的情况下查找最大可能的平衡二叉子串分割数的挑战。
这里提供了 C 语言代码以及在最多花费 K 的情况下查找最大可能的平衡二叉子串分割数的算法。
80 次查看
