Easy

题目描述

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

你必须重新排列这些位，使得结果二进制数是可以由这个组合创建的最大奇数二进制数。

返回表示可以由给定组合创建的最大奇数二进制数的字符串。

注意结果字符串可以有前导零。

示例 1：

输入：s = "010"
输出："001"
解释：因为只有一个 '1'，它必须在最后一位。所以答案是 "001"。

示例 2：

输入：s = "0101"
输出："1001"
解释：其中一个 '1' 必须在最后一位。用剩余数字能构成的最大数字是 "100"。所以答案是 "1001"。

约束条件：

  • 1 <= s.length <= 100
  • s 只包含 '0' 和 '1'
  • s 至少包含一个 '1'

提示：

  • 奇数的二进制表示在最低有效位包含 '1'

解题思路

解题思路

这道题要求我们重新排列二进制字符串的位，使得结果是最大的奇数二进制数。

关键观察：

  1. 要使二进制数是奇数，最后一位必须是 '1'
  2. 要使二进制数最大，需要将尽可能多的 '1' 放在前面（高位）

贪心策略：

  1. 统计字符串中 '1' 和 '0' 的个数
  2. 由于最后一位必须是 '1'（保证奇数），我们需要在末位放置一个 '1'
  3. 剩余的 '1' 全部放在前面，然后跟上所有的 '0'，最后是末位的 '1'

具体步骤：

  • 如果有 count1 个 '1' 和 count0 个 '0'
  • 结果字符串的格式为：(count1-1) 个 '1' + count0 个 '0' + 1 个 '1'

这样构造出的二进制数既是奇数（末位为1），又是最大的（高位尽可能多的1）。

代码实现

class Solution {
public:
    string maximumOddBinaryNumber(string s) {
        int count1 = 0, count0 = 0;
        
        // 统计1和0的个数
        for (char c : s) {
            if (c == '1') count1++;
            else count0++;
        }
        
        // 构造结果：(count1-1)个'1' + count0个'0' + 1个'1'
        string result = string(count1 - 1, '1') + string(count0, '0') + "1";
        
        return result;
    }
};

class Solution:
    def maximumOddBinaryNumber(self, s: str) -> str:
        count1 = s.count('1')
        count0 = s.count('0')
        
        # 构造结果：(count1-1)个'1' + count0个'0' + 1个'1'
        return '1' * (count1 - 1) + '0' * count0 + '1'

public class Solution {
    public string MaximumOddBinaryNumber(string s) {
        int count1 = 0, count0 = 0;
        
        // 统计1和0的个数
        foreach (char c in s) {
            if (c == '1') count1++;
            else count0++;
        }
        
        // 构造结果：(count1-1)个'1' + count0个'0' + 1个'1'
        return new string('1', count1 - 1) + new string('0', count0) + "1";
    }
}

/**
 * @param {string} s
 * @return {string}
 */
var maximumOddBinaryNumber = function(s) {
    const ones = s.split('').filter(char => char === '1').length;
    const zeros = s.length - ones;
    
    return '1'.repeat(ones - 1) + '0'.repeat(zeros) + '1';
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(1)

说明：

  • 时间复杂度：需要遍历一次字符串统计字符个数，O(n)
  • 空间复杂度：只使用了常数个额外变量，O(1)（不计算返回结果的空间）