难度: Easy
给你一个 二进制 字符串 s ，其中至少包含一个 '1' 。
你必须按某种方式 重新排列 字符串中的位，使得到的二进制数字是可以由该组合生成的 最大二进制奇数 。
以字符串形式，表示并返回可以由给定组合生成的最大二进制奇数。
注意 返回的结果字符串 可以 含前导零。
示例 1：
输入：s = "010" 输出："001" 解释：因为字符串 s 中仅有一个 '1' ，其必须出现在最后一位上。所以答案是 "001" 。
示例 2：
输入：s = "0101" 输出："1001" 解释：其中一个 '1' 必须出现在最后一位上。而由剩下的数字可以生产的最大数字是 "100" 。所以答案是 "1001" 。
提示：
1 <= s.length <= 100s 仅由 '0' 和 '1' 组成s 中至少包含一个 '1'运行时间: 19 ms
内存: 16.0 MB
class Solution:
def maximumOddBinaryNumber(self, s: str) -> str:
zeros = s.count('0')
ones = len(s) - zeros
if ones == 1:
return "0" * zeros + "1"
return "1" * (ones - 1) + "0" * zeros + "1"
为了生成给定二进制字符串s中可以排列出的最大奇数，我们需要：1. 确保最低位是'1'，因为只有这样才能保证数字是奇数。2. 尽可能地把'1'放在高位，以生成较大的数。具体操作如下：首先统计字符串中'0'和'1'的数量。如果'1'的数量为1，只能将这个'1'放在最低位，其余位置都是'0'。如果'1'的数量超过1，除了一个'1'保留在最低位外，其余的'1'尽可能放在高位，'0'紧随其后。
时间复杂度: O(n)
空间复杂度: O(n)
# 定义解决方案类
class Solution:
def maximumOddBinaryNumber(self, s: str) -> str:
# 计算'0'的数量
zeros = s.count('0')
# 计算'1'的数量，通过总长度减去'0'的数量
ones = len(s) - zeros
# 如果只有一个'1', 只能放在最后
if ones == 1:
return '0' * zeros + '1'
# 如果'1'多于一个，尽量将'1'放在前面，最后一个'1'放在最末尾
return '1' * (ones - 1) + '0' * zeros + '1'
统计'0'和'1'的数量是一种高效的方法，因为它只需要遍历字符串一次（时间复杂度为O(n)），然后根据统计结果构造出最大的奇数。如果直接操作原字符串进行排序或重排，可能会涉及到更复杂的排序算法，其时间复杂度通常为O(n log n)，并且在这个特定问题中，排序不是必要的，因为我们只关心'0'和'1'的数量，而不是它们的具体位置。
这种方法仍然非常高效。统计'0'和'1'的数量只需要一次遍历，所以时间复杂度为O(n)，其中n是字符串的长度。因此，即使字符串长度接近100或更长，它依然可以在很短的时间内完成。在实际应用中，这种方法对于处理大规模数据是足够高效的。
将一个'1'保留在最低位是为了确保结果是一个奇数，因为二进制数只有最低位是1时才是奇数。将其余的'1'尽可能放在高位是为了使得整个数尽可能大。在二进制中，高位的'1'对数值的贡献大于低位的'1'，因此这种安排可以确保生成的二进制数是可能的最大值。
这种解法在所有情况下都能保证得到最大的二进制奇数。算法的逻辑保证了在有至少一个'1'的情况下，最大的奇数能够被构造出来。唯一的边界情况是当字符串中没有'1'时，即所有字符都是'0'。在这种情况下，无法构成奇数，因此解决方案应该包括对这种情况的检查和适当的处理（例如返回一个错误信息或特定的输出）。