LeetCode(力扣)算法题_2864_最大二进制奇数
最大二进制奇数
题目描述
给你一个 二进制 字符串 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 方法，导致程序的执行时间会变长。