题目描述
给你一个 二进制 字符串 s
,其中至少包含一个 '1'
。
你必须按某种方式 重新排列 字符串中的位,使得到的二进制数字是可以由该组合生成的 最大二进制奇数。
以字符串形式,表示并返回可以由给定组合生成的最大二进制奇数。
注意 返回的结果字符串 可以 含前导零。
样例
输入:s = "010"
输出:"001"
解释:因为字符串 s 中仅有一个 '1',其必须出现在最后一位上。所以答案是 "001"。
输入:s = "0101"
输出:"1001"
解释:其中一个 '1' 必须出现在最后一位上。而由剩下的数字可以生产的最大数字是 "100"。所以答案是 "1001"。
限制
1 <= s.length <= 100
s
仅由'0'
和'1'
组成。s
中至少包含一个'1'
。
算法
(贪心) $O(n)$
- 将所有的
1
尽可能放到最前边,最后留一个1
在最低位。
时间复杂度
- 遍历字符串一次,构造答案一次,故时间复杂度为 $O(n)$。
空间复杂度
- 在原数组上直接修改,故空间复杂度为 $O(n)$。
C++ 代码
class Solution {
public:
string maximumOddBinaryNumber(string s) {
const int n = s.size();
int one = 0;
for (char c : s)
if (c == '1')
++one;
for (int i = 0; i < one - 1; i++)
s[i] = '1';
for (int i = one - 1; i < n - 1; i++)
s[i] = '0';
s[n - 1] = '1';
return s;
}
};