[LeetCode] 2864. Maximum Odd Binary Number

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’.

最大二进制奇数。

给你一个 二进制 字符串 s ，其中至少包含一个 ‘1’ 。
你必须按某种方式 重新排列 字符串中的位，使得到的二进制数字是可以由该组合生成的 最大二进制奇数 。
以字符串形式，表示并返回可以由给定组合生成的最大二进制奇数。
注意 返回的结果字符串 可以 含前导零。

思路

因为需要保证最后的输出是一个奇数，所以需要预留一个 1 放在最低位，其他的 1 统统放在最高位。
具体做法是先扫描一遍 input 字符串，记录一下 0 的个数和 1 的个数，在保证最后一个位置是 1 的情况下优先放 1，其余位置放 0 即可。

复杂度

时间O(n)
空间O(1)

代码

Java实现

class Solution {
    public String maximumOddBinaryNumber(String s) {
        int n = s.length();
        int one = 0;
        for (char c : s.toCharArray()) {
            if (c == '1') {
                one++;
            }
        }
        int zero = n - one;

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < one - 1; i++) {
            sb.append('1');
        }
        for (int i = 0; i < zero; i++) {
            sb.append('0');
        }
        sb.append('1');
        return sb.toString();
    }
}