最多可以用 A 個 0 和 B 個 1 來替換 ?，且相鄰字元不重複的最大字元數

---

本文旨在實現一個程式，計算最多可以用 A 個 0 和 B 個 1 來替換 ?，且相鄰字元不重複的最大字元數。

給定兩個整數 A 和 B，分別表示可用的 0 和 1 的數量，以及一個只包含特殊字元 "*" 和 "?" 的字串 Str。目標是確定在 "?" 位置最多可以使用的字元數，而不會導致任何相鄰字元相同。

示例 1

Let us give the input string str = “*??*??*”, A = 5, B = 2
Output obtained is : 4

解釋

您可以將字串更改為 "*01*01*"。因此，最多可以使用 (2 + 2 = 4) 個字元替換 "?"。

示例 2

Let us give the input string str = “*??*???*”, A = 5, B = 0
Output obtained is : 3

解釋

您可以將字串更改為 "*0?*0?0*"。因此，最多可以使用 (1 + 2 = 3) 個字元替換 "?"。

示例 3

Let us give the input string str = “*??*??*”, A = 0, B = 2
Output obtained is : 2

解釋

您可以將字串更改為 "*?1*?1*"。因此，最多可以使用 (1 + 1 = 2) 個字元替換 "?"。

問題陳述

實現一個程式來查詢最多可以用 A 個 0 和 B 個 1 來替換 ?，且相鄰字元不重複的最大字元數

演算法

以下是查詢最多可以用 A 個 0 和 B 個 1 來替換 ?，且相鄰字元不重複的最大字元數的演算法：

• 步驟 1 - 定義一個函式來確定最多可以放入 "?" 位置的字元 "A" 和 "B" 的最大數量。

• 步驟 2 - 定義一個字串 str，變數 l 定義為字串的大小或長度。

• 步驟 3 - 定義一個整型變數 current。

  定義變數 current 用於儲存當前 "?" 的數量，並將其初始化為零。

• 步驟 4 - 定義一個數組 segLengths[] 來儲存相鄰 "?" 段的長度。

• 步驟 5 - 遍歷字串並檢查字元是否為 '？'。如果是，則將 current 變數加 1。

• 步驟 6 - 檢查 current 是否等於 0。如果不等於 0，則必須將 current 變數重新初始化為零。

• 步驟 7 - 定義一個整型變數來儲存最大計數。

• 步驟 8 - 定義一個整型變數 "halfX" 來儲存陣列 segLengths[] 中每個元素的一半。

• 步驟 9 - 定義一個整型變數 "halfY" 來儲存每個元素的一半及其餘數。

• 步驟 10 - 如果 aCount 大於 bCount，則將 maxCount 加上 aCount 和 halfX 的最小值。

• 步驟 11 - 更新 aCount。

• 步驟 12 - 將 maxCount 加上 bCount 和 halfY 的最小值。

• 步驟 13 - 更新 bCount。

• 步驟 14 - 返回獲得的 maxCount。

示例 (C 程式)

以下是上述演算法的 C 程式實現，用於查詢最多可以用 A 個 0 和 B 個 1 來替換 ?，且相鄰字元不重複的最大字元數。

#include <stdio.h>
#include <string.h>
int maximumChar(char *str, int aCount, int bCount){
   int l = strlen(str);
   int current = 0;
   int segLengths[100];
   int segCount = 0;
   for (int i = 0; i < l; i++)   {
      if (str[i] == '?') {
         current++;
      } else {
         if (current != 0) {
            segLengths[segCount++] = current;
            current= 0;
         }
      }
   }
   if (current != 0) {
      segLengths[segCount++] = current;
   }
   int maxCount = 0;
   for (int i = 0; i < segCount; i++)  {
      int halfX = segLengths[i] / 2;
      int halfY = segLengths[i] / 2 + segLengths[i] % 2;
      if (aCount > bCount) {
         int temp = aCount;
         aCount = bCount;
         bCount = temp;
      }
      maxCount += (aCount < halfX ? aCount : halfX);
      aCount -= (aCount < halfX ? aCount : halfX);
      maxCount += (bCount < halfY ? bCount : halfY);
      bCount -= (bCount < halfY ? bCount : halfY);
   }
   return maxCount;
}
int main(){
   char str[] = "*??*??*";
   int aCount = 5, bCount = 2;
   printf("%d
", maximumChar(str, aCount, bCount));
   return 0;
}

輸出

執行後，將產生以下輸出：

4

結論

同樣，我們可以找到最多可以用 A 個 0 和 B 個 1 來替換 ?，且相鄰字元不重複的最大字元數。本文解決了獲得程式來查詢“最多可以用 A 個 0 和 B 個 1 來替換 ?，且相鄰字元不重複的最大字元數”的挑戰。這裡提供了 C 程式設計程式碼以及查詢最多可以用 A 個 0 和 B 個 1 來替換 ?，且相鄰字元不重複的最大字元數的演算法。