資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學根據給定條件確定具有最大1的子序列的最小步驟
本文旨在實現一個程式，根據給定條件查詢確定具有最大1的子序列的最小步驟。
眾所周知，可以用以空值結尾的包含字元的一維陣列來定義字串。
給定一個長度為K的字串Str，其中K始終為偶數，並且包含字元“0”、“1”和“?”。將字串分成兩個單獨的字串，分別稱為Str1和Str2，每個字串都將包含Str的偶數值和奇數值的字元。目標是確定預測哪個字串（Str1或Str2）將具有最大數量的1所需的最小步驟數。在單個步驟中選擇Str1或Str2的一個字元。如果字元為零，則選擇'0'；如果字元為一，則選擇'1'；如果字元為'?'，則選擇'1'或'0'。
問題陳述
實現一個程式，根據給定條件查詢確定具有最大1的子序列的最小步驟
示例1
Input: Str = “?10?0?”
Output: 4
解釋
步驟1 − 此處Str[0]為“?”
So select "0" as the character for Str1. Which implies Str1=”0″, Str2=”″.
步驟2 − 此處Str[1]為“1”
Select "1" as the character for Str2. Which implies Str1=”0″, Str2=”1″.
步驟3 − 此處Str[2]為“0”
Select "0" as the character for Str1. Which implies Str1=”00″, Str2=”1″.
步驟4 − 此處Str[3]為“?”
Select "1" as the character for Str2. Which implies Str1=”00″, Str2=”11″.
無論為剩餘索引選擇什麼數字，在步驟4之後，Str2都將具有更多1。
示例2
Input: Str = “1?0??0110”
Output: 4
解釋
步驟1 − 此處Str[0]為“1”
So select "1" as the character for Str1. Which implies Str1=”1″, Str2=”″.
步驟2 − 此處Str[1]為“?”
Select "1" as the character for Str2. Which implies Str1=”1″, Str2=”1″.
步驟3 − 此處Str[2]為“0”
Select "0" as the character for Str1. Which implies Str1=”10″, Str2=”1″.
步驟4 − 此處Str[3]為“?”
Select "1" as the character for Str2. Which implies Str1=”10″, Str2=”11″.
步驟5 − 此處Str[4]為“?”
Select "0" as the character for Str1. Which implies Str1=”100″, Str2=”11″.
步驟6 − 此處Str[5]為“0”
Select "0" as the character for Str2. Which implies Str1=”100″, Str2=”111″.
步驟7 − 此處Str[6]為“1”
Select "1" as the character for Str1. Which implies Str1=”1001″, Str2=”111″.
無論為剩餘索引選擇什麼數字，在步驟7之後，Str2都將具有更多1。
解決方案方法
為了根據給定條件找到確定具有最大1的子序列的最小步驟，我們採用以下方法。
解決此問題並根據給定條件找到確定具有最大1的子序列的最小步驟的方法如下所示。
目標是遞迴地解決問題，並在考慮每種選擇後得出解決方案。
遞迴是指函式直接（即，無需中間體）或間接地呼叫自身的過程。此等效函式被認為是遞迴函式。遞迴演算法也可以很容易地用於解決各種問題。
演算法
下面給出了根據給定條件查詢確定具有最大1的子序列的最小步驟的演算法
步驟1 − 開始
步驟2 − 定義遞迴函式。
步驟3 − 定義字串Str、整數i、整數count1和count2，用於分別儲存Str1和Str2中直到i的1的數量。
步驟4 − 定義整數n1和n2來儲存Str1和Str2中可用的位置。
步驟5 − 如果i等於m，則Str1和Str2都已完全填充，現在可以確定地預測答案。因此返回0。
步驟6 − 如果count1超過n2和count2的乘積，則返回0，因為即使選擇了Str2中的所有1，Str1現在也將比Str2具有更多的1。
步驟7 − 在測試基本情況後，檢查i是偶數還是奇數。如果i是偶數，則Str1將選擇此索引；否則，Str2將選擇此索引。
步驟8 − 假設當前字元為“?”，即s[i] = '?'，則執行選擇'1'和選擇'0'的兩次遞迴呼叫，在兩者中都加入1後返回兩個值的較小值。
步驟8 − 停止
由於上述原因，如果count2超過n1和count1的乘積，則返回0。
由於填充後字串中可用位置的數量將減少一個位置，因此根據當前正在填充的字串減少n1或n2。
否則，進行一次呼叫，然後加一得到答案。
最終的遞迴呼叫將提供此問題的答案。
示例：C++程式
以下是上述根據給定條件查詢確定具有最大1的子序列的最小步驟的演算法的C++程式實現
// the C++ program of the above written algorithm
#include <bits/stdc++.h>
using namespace std;
// the function in order find the minimum number of the steps recursively needed by combining both the 2 strings
int minimumSteps(string& Str, int cnt1, int cnt2,int n1, int n2, int m,int i){
// check whetherthe current pointer reach //the end
if (i == m) {
return 0;
}
// the Condition which indicates here that one string does more ones than the other regardless of which number is opted for theindexes which is remaining
if (cnt1 > (n2 + cnt2)
|| cnt2 > (n1 + cnt1)) {
return 0;
}
int ch1 = 0;
int ch2 = 0;
// on condition that i is found to be even, then choose the character for Str
if (i % 2 == 0) {
if (Str[i] == '?') {
return min( 1 + minimumSteps(Str, i + 1, cnt1 + 1, cnt2, n1 - 1, n2, m), 1 + minimumSteps( Str, i + 1, cnt1, cnt2, n1 - 1, n2, m));
} else if (Str[i] == '1') {
ch1 = 1 + minimumSteps(Str, i + 1, cnt1 + 1, cnt2, n1 - 1, n2, m);
return ch1;
} else {
ch2 = 1 + minimumSteps(Str, i + 1, cnt1, cnt2, n1 - 1, n2, m);
return ch2;
}
}
else {
if (Str[i] == '?') {
return min(1 + minimumSteps(Str, i + 1, cnt1, cnt2 + 1, n1, n2 - 1, m),1 + minimumSteps(Str, i + 1,cnt1, cnt2, n1, n2 - 1, m));
} else if (Str[i] == '1') {
ch1 = 1+ minimumSteps(Str, i + 1, cnt1, cnt2 + 1, n1, n2 - 1, m);
return ch1;
} else {
ch2 = 1+ minimumSteps( Str, i + 1, cnt1, cnt2, n1, n2 - 1, m);
return ch2;
}
}
}
int main(){
string str = "?10?0?01";
int M = str.size();
cout << minimumSteps(str, 0, 0, 0, M / 2, M / 2, M);
return 0;
}
輸出
1
結論
同樣，我們可以根據給定條件找到確定具有最大1的子序列的最小步驟。
本文解決了根據給定條件獲得確定具有最大1的子序列的最小步驟的挑戰。
這裡提供了C++程式設計程式碼以及根據給定條件查詢確定具有最大1的子序列的最小步驟的演算法。
70 次瀏覽
