0

バイナリ文字列を指定すると、ex 10101011111001 の場合、最初のゼロ (上記の場合は 2 番目のゼロ) を削除し、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

0

ループでこれを行うと遅くなります：

ans = ans + s[i];

毎回文字列のコピーを作成する必要があります。代わりに、次を使用する必要があります。

ans.push_back(s[i]);

文字列をインプレースで変更します。これにより、現在の2次ランタイムではなく、線形ランタイムが提供されます。これは、長い文字列の大幅な改善になります。

最良の結果を得るans.reserve(siz);には、ループの前に配置して、再割り当てを実行する必要がないようにすることもできます。

于 2012-12-23T11:34:04.167 に答える
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 に答える