最大二进制奇数

You are given a binary string s that contains at least one '1'.

You have to rearrange the bits in such a way that the resulting binary number is the maximum odd binary number that can be created from this combination.

Return a string representing the maximum odd binary number that can be created from the given combination.

Note that the resulting string can have leading zeros.

 

Example 1:

Input: s = "010"
Output: "001"
Explanation: Because there is just one '1', it must be in the last position. So the answer is "001".

Example 2:

Input: s = "0101"
Output: "1001"
Explanation: One of the '1's must be in the last position. The maximum number that can be made with the remaining digits is "100". So the answer is "1001".

 

Constraints:

• 1 <= s.length <= 100
• s consists only of '0' and '1'.
• s contains at least one '1'.

/*
题目思路：
1. 首先，我们需要确保字符串中的一个 '1' 必须出现在最后一位上以确保结果是一个奇数。
2. 然后，我们将剩余的 '0' 和 '1' 进行排序以生成最大的二进制数。
3. 将步骤1和2的结果拼接起来即可得到最终结果。
使用Java Stream简化代码。
*/

import java.util.stream.Collectors;

public class Solution {
    public String largestOddBinary(String s) {
        // 计算 '1' 的数量
        long onesCount = s.chars().filter(ch -> ch == '1').count();
        // 计算 '0' 的数量
        long zerosCount = s.length() - onesCount;
        // 构建结果字符串
        String result = "1" + "0".repeat((int)zerosCount) + "1".repeat((int)(onesCount - 1));
        return result;
    }
}

为了生成给定二进制字符串s中可以排列出的最大奇数，我们需要：1. 确保最低位是'1'，因为只有这样才能保证数字是奇数。2. 尽可能地把'1'放在高位，以生成较大的数。具体操作如下：首先统计字符串中'0'和'1'的数量。如果'1'的数量为1，只能将这个'1'放在最低位，其余位置都是'0'。如果'1'的数量超过1，除了一个'1'保留在最低位外，其余的'1'尽可能放在高位，'0'紧随其后。

O(n)

O(n)