根據給定條件確定具有最多1的子序列的最小步驟

本文的目的是實作一個程序，以找到最小步驟來根據給定條件確定最大 1 秒的子序列。

眾所周知，包含以 null 結尾的字元的一維數組可以用來定義字串。

給定一個長度為K 的字串Str，其中K 始終為偶數，並且包含字元「0」、「1」和「？」將字串分成兩個單獨的字串，我們將它們稱為Str1 和Str2，每個字串都將包含Str 偶數值和Str 奇數值處的字元。目標是確定預測兩個字串（Str1 或 Str2）中 1 的數量最多所需的最少步驟。一步為 Str1 或 Str2 選擇一個字元。當字元為零時選擇“0”，如果字元為一則選擇“1”，如果字元為“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″.

無論剩餘索引選擇什麼數字，Str2 在步驟 4 之後都會有更多的 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″.

無論剩餘索引選擇什麼數字，Str2 在步驟 7 之後都會有更多的 1。

解決方案

為了找到最小步驟來根據給定條件確定最大 1 秒的子序列，我們採用以下方法。

下面給出了解決該問題的方法，並根據給定條件找到最小步驟來確定最大為 1 秒的子序列。

目標是遞歸地解決問題並在考慮每個替代方案後得出解決方案。

術語「遞歸」只不過是函數呼叫自身的過程，無論是直接（即沒有中介）或是間接呼叫自身。此等價函數被認為是遞歸函數。此外，還可以使用遞歸演算法來相對輕鬆地解決各種問題。

演算法

根據下面給出的給定條件找到確定最大 1 秒子序列的最小步驟的演算法

• 第 1 步 - 開始

• 第 2 步 - 定義遞歸函數。

• 步驟 3 - 定義字串 Str 、整數 i、整數 count1 和 count2，用於分別儲存 Str1 和 Str2 中直到 i 的個數。

• 步驟 4 - 定義整數 n1 和 n2 來儲存 Str1 和 Str2 中的可用位置

• 步驟 5 - 如果 i 等於 m，則 Str1 和 Str2 都已完全填充，現在可以肯定地預期答案。因此請回覆 0。

• 第6 步 - 如果count1 超過n2 和count2 的乘積，則傳回0，因為即使在選擇了Str2 中的所有值之後，Str1 現在也將比Str2 擁有更多值。

由於上述原因，如果 count2 超過 n1 和 count1 的乘積，則傳回 0。

• 第 7 步 - 在測試基本實例後驗證 i 是否等於偶數或奇數。如果i是偶數，Str1會選擇這個索引；如果不是，則為 Str2。

由於填充後字串中可存取位置的數量將減少一個位置，因此根據目前填充的字串減少 n1 或 n2。

• 第8 步 - 假設當前字元是'?'即s[i] = '? ' 然後執行選擇「1」和挑選「0」的兩次遞歸調用，將1 合併到兩者後返回兩者中的最小值。

否則，撥打一通電話，然後新增一通電話即可獲得答案。

對此查詢的回應將由最終的遞歸呼叫提供。

• 第 8 步 - 停止

#範例：C 程式

這是上述編寫的演算法的 C 程式實現，用於根據給定條件查找最小步驟來確定最大 1 秒的子序列

// 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

結論

同樣，我們可以根據給定的條件找到確定最大為1s的子序列的最小步數

本文解決了根據給定條件獲得確定最大 1 秒子序列的最少步驟的挑戰。

這裡提供了 C 程式碼以及根據給定條件找到確定最大 1 秒子序列的最小步驟的演算法。

以上是根據給定條件確定具有最多1的子序列的最小步驟的詳細內容。更多資訊請關注PHP中文網其他相關文章！