LeetCode 题解工作台
最大二进制奇数
给你一个 二进制 字符串 s ，其中至少包含一个 '1' 。 你必须按某种方式 重新排列 字符串中的位，使得到的二进制数字是可以由该组合生成的 最大二进制奇数 。 以字符串形式，表示并返回可以由给定组合生成的最大二进制奇数。 注意 返回的结果字符串 可以 含前导零。 示例 1： 输入： s = "0…
3
题型
6
代码语言
3
相关题
当前训练重点
简单 · 贪心·invariant
答案摘要
我们先统计字符串 中 的个数，记为 。那么我们将 $cnt - 1$ 个 放在最高位，剩下的 $|s| - cnt$ 个 放在后面，最后再加上一个 即可。 时间复杂度 ，空间复杂度 。其中 为字符串 的长度。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
给你一个 二进制 字符串 s ，其中至少包含一个 '1' 。
你必须按某种方式 重新排列 字符串中的位，使得到的二进制数字是可以由该组合生成的 最大二进制奇数 。
以字符串形式，表示并返回可以由给定组合生成的最大二进制奇数。
注意 返回的结果字符串 可以 含前导零。
示例 1：
输入：s = "010" 输出："001" 解释：因为字符串 s 中仅有一个 '1' ，其必须出现在最后一位上。所以答案是 "001" 。
示例 2：
输入：s = "0101" 输出："1001" 解释：其中一个 '1' 必须出现在最后一位上。而由剩下的数字可以生产的最大数字是 "100" 。所以答案是 "1001" 。
提示：
1 <= s.length <= 100s仅由'0'和'1'组成s中至少包含一个'1'
解题思路
方法一：贪心
我们先统计字符串 中 的个数，记为 。那么我们将 个 放在最高位，剩下的 个 放在后面，最后再加上一个 即可。
时间复杂度 ，空间复杂度 。其中 为字符串 的长度。
class Solution:
def maximumOddBinaryNumber(self, s: str) -> str:
cnt = s.count("1")
return "1" * (cnt - 1) + (len(s) - cnt) * "0" + "1"
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n) |
| 空间 | O(n) |
面试官常问的追问
外企场景- question_mark
Ask why placing a '1' at the end guarantees an odd number.
- question_mark
Check if candidates correctly separate the last '1' from the remaining bits.
- question_mark
Expect explanation of greedy choice for maximizing the binary value.
常见陷阱
外企场景- error
Forgetting to reserve one '1' at the least significant position, producing an even number.
- error
Reordering '0's and '1's incorrectly, reducing the maximum value.
- error
Assuming multiple '1's can occupy the last position, violating the odd constraint.
进阶变体
外企场景- arrow_right_alt
Find the maximum even binary number by placing '0' at the least significant bit.
- arrow_right_alt
Count the number of maximum odd binary numbers possible from the same string.
- arrow_right_alt
Extend the problem to ternary strings with a similar odd-value constraint.