【2024.04.10】LeetCode每日一题·修改后的最大二进制字符串

2024年04月10日 17时31分

标签： LeetCode 数学贪心字符串

## 题目描述

给你一个二进制字符串`binary`，它仅有`0`或者`1`组成。你可以使用下面的操作任意次对它进行修改：

* 操作`1`：如果二进制串包含子字符串`"00"`，你可以用`"10"`将其替换。

* 比方说，`"00010" -> "10010"`

* 操作`2`：如果二进制串包含子字符串`"10"`，你可以用`"01"`将其替换。
    * 比方说， "00010" -> "00001"

请你返回执行上述操作任意次以后能得到的**最大二进制字符串**。如果二进制字符串`x`对应的十进制数字大于二进制字符串`y`对应的十进制数字，那么我们称二进制字符串`x`大于二进制字符串`y`。

#### 示例1
````
输入：binary = "000110"
输出："111011"
解释：一个可行的转换为：
"000110" -> "000101" 
"000101" -> "100101" 
"100101" -> "110101" 
"110101" -> "110011" 
"110011" -> "111011"
````

#### 示例2
````
输入：binary = "01"
输出："01"
解释："01" 没办法进行任何转换。
````

#### 提示
````
1 <= binary.length <= 10^5
binary 仅包含 '0' 和 '1' 。
````

#### 来源

> 来源：力扣（LeetCode）
> 
> 链接：[1702. 修改后的最大二进制字符串](https://leetcode.cn/problems/maximum-binary-string-after-change/description/)

## 解题思路
我们可以将一个二进制字符串分为左右两个部分（每个部分都可能为空）：（1）左边为全包含字符1的部分，即前导1的部分，与（2）右边为剩下的第一个字符为0的部分。

对于左半部分，显然保留原始字符串是最大的。对于右半部分，由于操作`2`相当于把字符1右移一位，因此能够将右半部分中存在的所有字符1移到字符串的最后，剩下的部分为连续的字符0；然后使用操作`1`将连续的字符0用字符1填满，最后仅会剩下一个字符0。由于此时字符0在最右边，因此得到的字符串一定是最大的。

整个过程需要遍历一遍字符串，因此时间复杂度为$$O(n)$$。

## 代码
````cpp
class Solution {
public:
    string maximumBinaryString(string binary) {
        int head_1 = 0, back_1 = 0, flag = 0, len = binary.length();
        for(char& c: binary){
            if(!flag && c == '0') flag = 1;
            if(!flag && c == '1') head_1++; // 前导1的个数
            if(flag && c == '1') back_1++; // 可以放到最后的1的个数
        }
        string ans(len, '1');
        int pos_0 = len - back_1 - 1;
        if(pos_0 < head_1){
            return binary;
        }
        else{
            ans[pos_0] = '0';
            return ans;
        }
    }
};
````

## 用时和内存
> 执行用时：136 ms，在所有C++提交中击败了77.55%的用户
>
> 内存消耗：45.91 MB，在所有C++提交中击败32.65%的用户
>

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【2024.04.10】LeetCode每日一题·修改后的最大二进制字符串

所有评论

暂无评论

新增评论