0

给定一个二进制字符串，例如 10101011111001，我想删除第一个零（在上述情况下为第二个），如果没有 0，则删除任何 1，因此上述字符串的输出将为 1101011111001。

如果我这样做使用

 for( int i = 0 ; i < siz-1 ; i++ ){
      if( s[i] =='0' && bit ==1) {
         bit = 0;
      }else {
         ans = ans + s[i];
      }
 }  
 if( bit == 1  ) {
     cout << ans <<endl;
 }else {
     ans = ans + s[siz-1];
     cout << ans <<endl;
  }

上面的解决方案给了我 TLE 和使用擦除功能的解决方案正常工作，是什么导致了这种行为？

注意：字符串的大小最大为 10^5

4

4 回答 4

1 
pos = s.find('0');
if (pos == string::npos) {
  result = s.substr(1);
} else {
  result = s.substr(0, pos) + s.substr(pos+1);
}
于 2012-12-23T12:09:23.410 回答
0

您的代码看起来无论如何都需要在末尾打印字符串。如果是这种情况，那么另一种解决方案是检查每个字符并在它不是第一个零时打印它。

这样您就可以避免在打印之前对字符串进行所有操作。

附录：显然，当字符串只有一个时，考虑到不打印最后一个“1”的可能性，需要一个单字符缓冲区来实际打印前一个字符。

于 2012-12-23T12:03:52.507 回答
0

这是示例代码（不是正确的代码，也不是 c++，只是伪代码）

int count=0;
bool zerofound==false;
while(yourstring.contains('0'))
{
 if(yourstring.elementAt(count)=='0')
 {
   yourstring.replace('0','');
   zerofound==true;
   break;
 }
  count++;
}
if(!zerofound)
{
  yourstring.replaceAt(0,'');
}
于 2012-12-23T11:29:55.327 回答
0

在循环中执行此操作会很慢：

ans = ans + s[i];

每次都需要复制字符串。相反，您应该使用：

ans.push_back(s[i]);

这将就地修改字符串。这将为您提供线性运行时间，而不是现在的二次运行时间，这将是长字符串的重大改进。

为了获得最佳结果，您还可以放在ans.reserve(siz);循环之前，这样就不需要执行重新分配。

于 2012-12-23T11:34:04.167 回答