莒县做网站,先申请网站空间,视频制作培训机构,品牌网站设计打造给你一个二进制字符串 binary #xff0c;它仅有 0 或者 1 组成。你可以使用下面的操作任意次对它进行修改#xff1a;
操作 1 #xff1a;如果二进制串包含子字符串 00 #xff0c;你可以用 10 将其替换。 比方说#xff0c; 00010…给你一个二进制字符串 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纯思维题需要在两个对字符串的操作中找到规律。考虑两个操作 00 - 10数字变大了符合最大二进制字符串的所求。 10 - 01数字变小了那么我们为什么需要这个操作他的意义是什么 能够显而易见想到的就是010通过10 - 01虽然单步变小了但修改后变为001进而使用00 - 10最终得到101整体是变大的。
观察010 - 001操作2的起到的作用是什么 将1右移将0连起来进而能够使用操作1对整体进行扩大。 那么将示例按照这个思路解析
000110 - 000101000101 - 000011 到此已经将所有0连续起来。
继续考虑所有连续的0最终会变成什么 00 - 100000就会变成1000再变成1100再变成1110。即000011 - 111011。 使用上面的过程多分析几个字符串就能得到规律 通过操作2可以将101010001这种1/0交替的字符串变成100000111这种1...0...1交替的字符串。再通过操作1可以将连续的0变成仅最后一位为0其余位为1的字符串。00000 - 11110。 也就是说最终得到的最大二进制字符串中最多只有一个0。
而且这个0的位置可以通过原字符串中1和0出现的次数以及第一个0出现的位置确定。
以10101001为例
首先出现0之前的1是不需要改动的。记录第一个出现0的位置zero_first 1。遍历字符串得到所有0的个数num 4。那么按照上面的分析原字符串可以变成10000111。进而变成11110111剩余0的位置位于下标 zero_first num -1处。 这里剩余的问题就是严格证明为什么按照这个流程下来得到的数是最大的。 从直觉上想让字符串变大就尽可能的让所有字符是1并且如果有00的位置要尽量靠后。上面过程得到的结果正符合这个直觉。 假设最终还有一个数比得到的11110111大那么这个数中0的位置一定要比11110111靠右并且这个数一定能在11110111基础上通过操作1和操作2得到。而操作1和操作2中将字符串变大的操作需要至少两个0而11110111只有1个0所以不存在这个数。 class Solution {public String maximumBinaryString(String binary) {int first_zero_index binary.indexOf(0);int zero_count 0;int length binary.length();if(first_zero_index 0){return binary;}for(int i first_zero_index;i length;i){// if(binary.charAt(i) 0){// zero_count;// }zero_count - binary.charAt(i) - 1;}return 1.repeat(first_zero_index zero_count - 1) 0 1.repeat(length - zero_count - first_zero_index);}
} 这里还有一个值得注意的地方关注代码中注释掉的部分。他们的效率差别会有多大 // if(binary.charAt(i) 0){// zero_count;// }zero_count - binary.charAt(i) - 1; 原因
字符比较binary.charAt(i) 0需要将字符转换为数字进行比较这是一个相对耗时的操作。字符减法binary.charAt(i) - 1直接将字符转换为数字然后执行减法运算这是一个更快的操作。
因此对于长字符串zero_count - binary.charAt(i) - 1 的效率将比 binary.charAt(i) 0 高得多。
