网站建设一般花多少费用,职业学院网站建设,开发软件多少钱,vs音乐网站开发实例最大二进制奇数
题目描述
给你一个 二进制 字符串 s #xff0c;其中至少包含一个 1 。
你必须按某种方式 重新排列 字符串中的位#xff0c;使得到的二进制数字是可以由该组合生成的 最大二进制奇数 。
以字符串形式#xff0c;表示并返回可以由给定组合生成的最大二进…最大二进制奇数
题目描述
给你一个 二进制 字符串 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 方法导致程序的执行时间会变长。
