最大二进制奇数
题目描述
给你一个 二进制 字符串 s ，其中至少包含一个 '1' 。
你必须按某种方式 重新排列 字符串中的位，使得到的二进制数字是可以由该组合生成的 最大二进制奇数 。
以字符串形式，表示并返回可以由给定组合生成的最大二进制奇数。
注意 返回的结果字符串 可以 含前导零。
示例 1：
输入：s = "010" 输出："001" 解释：因为字符串 s 中仅有一个 '1' ，其必须出现在最后一位上。所以答案是 "001" 。示例 2：
输入：s = "0101" 输出："1001" 解释：其中一个 '1' 必须出现在最后一位上。而由剩下的数字可以生产的最大数字是 "100" 。所以答案是 "1001" 。
解题思路
贪心算法
由于是二进制，那么 temp 中的每一位，不是 0 就是 1 。根据题意可知，需要返回的是最大的二进制奇数，所以返回结果的最后一位一定是 1 。按照贪心算法的原则，要返回最大二进制奇数，需要将剩下的 1 放置在字符串的最前面。
1. 先统计字符串中 1 的数量 。
class Solution {
public String maximumOddBinaryNumber(String s) {
// 统计字符串中 1 的数量
int temp = 0;
for(int i = 0; i < s.length(); i++){
if((s.charAt(i) - '0') == 1){temp += 1;}
}
}
}2. 使用 StringBuilder 构造一个字符串，用来存储输出结果。
class Solution {
public String maximumOddBinaryNumber(String s) {
// 统计字符串中 1 的数量
int temp = 0;
for(int i = 0; i < s.length(); i++){
if((s.charAt(i) - '0') == 1){temp += 1;}
}
// 用于接收输出结果的字符串
StringBuilder str = new StringBuilder();
}
}3. 减去最后一位的 1 后，将剩下的 1 排在字符串的最前面。
class Solution {
public String maximumOddBinaryNumber(String s) {
// 统计字符串中 1 的数量
int temp = 0;
for(int i = 0; i < s.length(); i++){
if((s.charAt(i) - '0') == 1){temp += 1;}
}
// 用于接收输出结果的字符串
StringBuilder str = new StringBuilder();
// 排入 1
for(int i = 0; i < temp - 1; i++){
str.append("1");
}
}
}4. 将剩下的 0 补上。
class Solution {
public String maximumOddBinaryNumber(String s) {
// 统计字符串中 1 的数量
int temp = 0;
for(int i = 0; i < s.length(); i++){
if((s.charAt(i) - '0') == 1){temp += 1;}
}
// 用于接收输出结果的字符串
StringBuilder str = new StringBuilder();
// 排入 1
for(int i = 0; i < temp - 1; i++){
str.append("1");
}
// 补上 0
for(int i = 0; i < s.length() - temp; i++){
str.append("0");
}
}
}5. 最后补上最后一位的 1 ，再输出结果就OK啦。
class Solution {
public String maximumOddBinaryNumber(String s) {
// 统计字符串中 1 的数量
int temp = 0;
for(int i = 0; i < s.length(); i++){
if((s.charAt(i) - '0') == 1){temp += 1;}
}
// 用于接收输出结果的字符串
StringBuilder str = new StringBuilder();
// 排入 1
for(int i = 0; i < temp - 1; i++){
str.append("1");
}
// 补上 0
for(int i = 0; i < s.length() - temp; i++){
str.append("0");
}
// 最后一位 1
str.append("1");
return str.toString();
}
}复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(1)
其中 n 表示给定字符串的长度 。
代码优化
上述代码虽然能够完成题目要求，但是写的较为繁琐，有以下可优化的点：
1. 统计数字 1 的数量可以优化为：
class Solution {
public String maximumOddBinaryNumber(String s) {
// 统计字符串中 1 的数量
int temp = 0;
for(int i = 0; i < s.length(); i++){
temp += s.charAt(i) - '0';
}
}
}2. 利用 repeat 方法直接返回排好序的结果字符。
class Solution {
public String maximumOddBinaryNumber(String s) {
// 统计字符串中 1 的数量
int temp = 0;
for(int i = 0; i < s.length(); i++){
temp += s.charAt(i) - '0';
}
// 返回结果字符
return "1".repeat(Math.max(0, temp - 1)) + "0".repeat(Math.max(0, s.length() - temp)) + "1";
}
}当然，这样做只是简化了代码，因为反复调用 repeat 方法，导致程序的执行时间会变长。
