2864. 最大二进制奇数

题目描述：

给你一个 二进制 字符串 s ，其中至少包含一个 ‘1’ 。

你必须按某种方式 重新排列 字符串中的位，使得到的二进制数字是可以由该组合生成的 最大二进制奇数 。

以字符串形式，表示并返回可以由给定组合生成的最大二进制奇数。

注意 返回的结果字符串 可以 含前导零。

示例 1：

输入：s = "010"
输出："001"
解释：因为字符串 s 中仅有一个 '1' ，其必须出现在最后一位上。所以答案是 "001" 。

示例 2：

输入：s = "0101"
输出："1001"
解释：其中一个 '1' 必须出现在最后一位上。而由剩下的数字可以生产的最大数字是 "100" 。所以答案是 "1001" 。

提示：

• 1 <= s.length <= 100
• s 仅由 ‘0’ 和 ‘1’ 组成
• s 中至少包含一个 ‘1’

---

解题分析及思路：

方法：贪心

思路：

统计字符串中 0 和 1 的个数，然后按照 1 的个数构造最大的奇数即可。

• 需注意二进制最低位是1 。
• 其他剩余所以1都放在最高位即可。

丑陋 逻辑比较清楚的写法：

func maximumOddBinaryNumber(s string) string {
	var subs [2]int
	for index := range s {
		subs[s[index]-'0']++
	}
	subs[1]--
	var results []byte
	for i := 0; i < subs[1]; i++ {
		results = append(results, '1')
	}
	for i := 0; i < subs[0]; i++ {
		results = append(results, '0')
	}
	results = append(results, '1')
	return string(results)
}

简洁的写法：

func maximumOddBinaryNumber1(s string) string {
	var countOfOne = strings.Count(s, "1")
	return strings.Repeat("1", countOfOne-1) + strings.Repeat("0", len(s)-countOfOne) + "1"
}

复杂度：

• 时间复杂度：O(N)
• 空间复杂度：O(1)

执行结果：

• 执行耗时:0 ms,击败了100.00% 的Go用户
• 内存消耗:2.6 MB,击败了35.90% 的Go用户