【LetMeFly】1702.修改后的最大二進制字符串：腦筋急轉彎（構造，貪心）

力扣題目鏈接：https://leetcode.cn/problems/maximum-binary-string-after-change/

給你一個二進制字符串?binary?，它僅有?0?或者?1?組成。你可以使用下面的操作任意次對它進行修改：

• 操作 1 ：如果二進制串包含子字符串?"00"?，你可以用?"10"?將其替換。

  <ul><li>比方說，?<code>"<strong>00</strong>010" -> "<strong>10</strong>010"</code></li>
  </ul>
  </li>
  <li>操作 2 ：如果二進制串包含子字符串?<code>"10"</code>?，你可以用?<code>"01"</code>?將其替換。
  <ul><li>比方說，?<code>"000<strong>10</strong>" -> "000<strong>01</strong>"</code></li>
  </ul>
  </li>
  

請你返回執(zhí)行上述操作任意次以后能得到的 最大二進制字符串?。如果二進制字符串 x?對應的十進制數(shù)字大于二進制字符串 y?對應的十進制數(shù)字，那么我們稱二進制字符串?x?大于二進制字符串?y?。

?

示例 1：

輸入：binary = "000110"
輸出："111011"
解釋：一個可行的轉換為：
"000110" -> "000101" 
"000101" -> "100101" 
"100101" -> "110101" 
"110101" -> "110011" 
"110011" -> "111011"

示例 2：

輸入：binary = "01"
輸出："01"
解釋："01" 沒辦法進行任何轉換。

?

提示：

• 1 <= binary.length <= 105
• binary 僅包含?'0' 和?'1' 。

解題方法：構造（貪心）

題目分析

如果給定字符串中沒有0，則不在本次討論的范圍之列，直接返回原字符串。

推論1：最終字符串中一定有0

僅有的兩種變換分別是00->10和10->01，只能減少0的個數(shù)，但永遠不可能將所有0消除。

推論2：最終字符串中一定只有一個0

以10111011為例，該字符串中有兩個0，則可以進行以下變換10111011->10011111->11011111，具體變換過程如下：

10111011
10110111 ---+
10101111    +---后面的那個0不斷地通過10->01的變換最終和前面那個0相鄰
10011111 ---+
11011111 -> 相鄰兩個0通過00->10的變換使得二進制字符串相比于初始值更大了

也就是說，假設最終字符串中有兩個0，那么后面的那個0一定可以通過10->01的變換與前面的0相鄰，相鄰兩個0再通過00->10變換，使得第一個0變成了1，字符串值更大了。

若有多個0則同理，最終一定只剩下一個0，變成111..11011..111的形態(tài)。

為什么不繼續(xù)變化了呢？因為11、01都不可變，唯一可變的是10->01。但是這么變的話相當于“0往前移”了，字符串值更小，不可取。

如何判斷最終字符串中0的位置？

由給定的兩種變換00->10和10->01可以發(fā)現(xiàn)，0要么被消除（變換一）要么左移（變換二），單純的左移會導致字符串變小，因此盡量將最前面的0“消除”。

如何消除？通過變換一消除。通過推論2我們知道，只要存在兩個0，則右邊的0必定能千里迢迢地來到左邊的0身邊并與之進行變換一：

111..11011..11011..11
111..11001..11111..11
111..11101..11111..11

也就是說，第一個0的右邊每存在一個0，就能讓第一個0的位置“右移一位”。

最終第一個0（也就是唯一的一個0）的位置，是原始字符串中第一個0的位置，再右移$0的總個數(shù)?1$位。

具體方法

給定字符串，統(tǒng)計其中0的個數(shù)（記為cnt0）。

若無0，則直接返回原始字符串；否則繼續(xù)。

找到字符串中第一個0的位置（記為pos0），構造一個只有pos0 + cnt0 - 1這個位置為0其余位置全部為1的字符串并返回。

時空復雜度分析

• 時間復雜度$O(len(binary))$
• 空間復雜度$O(len(binary))$：空間復雜度來自字符串構造過程中的臨時變量。

AC代碼

C++

class Solution {
public:string maximumBinaryString(string binary) {int cnt0 = count(binary.begin(), binary.end(), '0');if (!cnt0) {return binary;}int first0 = binary.find('0');return string(first0 + (cnt0 - 1), '1') + '0' + string(binary.size() - (first0 + (cnt0 - 1)) - 1, '1');}
};

Python

class Solution:def maximumBinaryString(self, binary: str) -> str:cnt0 = binary.count('0')if not cnt0:return binaryfirst0 = binary.find('0')pos0 = first0 + (cnt0 - 1)return '1' * pos0 + '0' + '1' * (len(binary) - pos0 - 1)

同步發(fā)文于CSDN和我的個人博客，原創(chuàng)不易，轉載經(jīng)作者同意后請附上原文鏈接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/137593422