題目

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

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

比方說， "00010" -> "10010"

操作 2 ：如果二進位制串包含子字串 "10" ，你可以用 "01" 將其替換。

比方說， "00010" -> "00001"

請你返回執行上述操作任意次以後能得到的 最大二進位制字串 。

如果二進位制字串 x 對應的十進位制數字大於二進位制字串 y 對應的十進位制數字，

那麼我們稱二進位制字串 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' 。

解題思路分析

1、貪心；時間複雜度O(n)，空間複雜度O(n)

func maximumBinaryString(binary string) string {	flag := true	rightOne := 0 // 記錄第1個0後面1的數量	for i := 0; i < len(binary); i++ {		if binary[i] == '0' {			flag = false		} else {			if flag == false {				rightOne++			}		}	}	if flag == true { // 全是1，直接返回		return binary	}	// 首先：第1個0之前的1不需要移動。	// 然後：把第1個0之後的1移到後面，後移：10=>01。	// 最後：然後把中間的000，都變成110，00=>10。	arr := make([]byte, len(binary))	for i := 0; i < len(arr); i++ {		arr[i] = '1'	}	arr[len(arr)-1-rightOne] = '0'	return string(arr)}

2、貪心；時間複雜度O(n)，空間複雜度O(n)

func maximumBinaryString(binary string) string {	n := len(binary)	count := strings.Count(binary, "1")	if count >= n-1 {		return binary	}	indexZero := strings.IndexByte(binary, '0')	count = count - indexZero	return strings.Repeat("1", n-1-count) + "0" + strings.Repeat("1", count)}

總結

Medium題目，採用貪心策略，要得到最大二進位制字串 ，在第1個0之前的不需要動，然後把第1個0之後的1透過10=>01移到後面，最後00=>10