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