LeetCode每日一题[C++]-2864.最大二进制奇数(贪心)

题目描述

给你一个 二进制 字符串 s ，其中至少包含一个 '1' 。

你必须按某种方式 重新排列 字符串中的位，使得到的二进制数字是可以由该组合生成的 最大二进制奇数 。

以字符串形式，表示并返回可以由给定组合生成的最大二进制奇数。

注意 返回的结果字符串 可以 含前导零。

示例 1：

输入：s = "010"
输出："001"
解释：因为字符串 s 中仅有一个 '1' ，其必须出现在最后一位上。所以答案是 "001" 。

示例 2：

输入：s = "0101"
输出："1001"
解释：其中一个 '1' 必须出现在最后一位上。而由剩下的数字可以生产的最大数字是 "100" 。所以答案是 "1001" 。

提示：

• 1 <= s.length <= 100
• s 仅由 '0' 和 '1' 组成
• s 中至少包含一个 '1'

解题思路

        题目给定二进制字符串 s构造字典序最大的二进制奇数，根据定义可以知道字符串中每一位要么为 0，要么为 1。由于构造的数必须为奇数，则最低位必须为 1，因此我们从字符串 s 中选择一个 1 放置到最低位。按照贪心原则，其余的 1全部放在最高位，剩余的 0 放在剩下的位即可，直接构造目标字符串返回即可。

复杂度分析

时间复杂度：O(n)，其中 n 表示给定字符串的长度。只需要遍历一遍字符串即可。

空间复杂度：O(1)，除返回值外不需要额外的空间。

代码

#include <vector>
#include <iostream>
using namespace std;
class Solution {
public:
    string maximumOddBinaryNumber(string s) {
        int cnt = 0;
        for (size_t i = 0; i < s.length(); i++)
        {
            if (s[i] == '1')
            {
                cnt++;
            }
            
        }
        return string(cnt - 1, '1') + string(s.length() - cnt, '0') + '1';
    }
};
int main()
{
    Solution solution;
    string s = "010";
    string res = solution.maximumOddBinaryNumber(s);
    cout << res << endl;

    s = "0101";
    res = solution.maximumOddBinaryNumber(s);
    cout << res << endl;
}