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