連続する最長の 1 部分文字列の長さを最大化するために、削除する必要がある 0 の数を最小限に抑えます。

この記事では、C 文字列操作に関連する興味深い問題を詳しく掘り下げます。今日私たちが勉強する問題は、「最も長く連続する 1 の部分文字列の長さを最大にするために、削除する必要がある 0 の数を最小限に抑える」方法です。この問題は、文字列操作と動的プログラミングのスキルを磨くのに最適な方法です。

＃＃＃問題文＃＃＃

バイナリ文字列が与えられた場合、タスクは、最長の 1 部分文字列の長さを最大化するために削除する必要がある 0 の数を最小限に抑えることです。

C ソリューション

この問題を解決するには、スライディング ウィンドウ法を使用できます。左ポインタと右ポインタの 2 つのポインタを維持します。最初は、両方のポインターが最初の要素を指します。次に、右ポインタを右に動かし続けます。 「0」が見つかった場合は、カウンターがインクリメントされます。カウンタがゼロ除去の許容数より大きくなった場合は、「0」に到達するまで左ポインタを右に移動し、カウンタをデクリメントします。

また、これまでに確認した 1 つの部分文字列の最大長を格納する変数 maxLen も維持します。

＃＃＃例＃＃＃

これは問題を解決する C コードです -

リーリー ＃＃＃出力＃＃＃ リーリー

テストケースの説明

バイナリ文字列「110100110」を考えてみましょう。2 つのゼロを削除できます。

この文字列と k の値を maxSubstring 関数に渡すと、左からスキャンが開始されます。 「0」に遭遇するたびに、zeroCount がインクリメントされます。 zeroCount が k を超えると、「0」に到達するまで左ポインタが右に移動し始め、zeroCount がデクリメントされます。

このプロセスでは、1 の最大部分文字列長である maxLen を継続的に更新します。指定された文字列について、最大 2 つのゼロを削除しない場合の 1 の部分文字列の最大長は 5、つまり 2 番目と 3 番目の「0」を削除した後の部分文字列「11111」になります。

したがって、関数は 5 を返します。

＃＃＃結論は＃＃＃

この質問では、スライディング ウィンドウ手法を効果的に使用して、C での複雑な文字列操作の問題を解決する方法を示します。これは、動的プログラミングと文字列処理技術を理解して実践するための優れた質問です。 C コーディングのスキルを向上させるために、このような質問を練習し続けてください。

以上が連続する最長の 1 部分文字列の長さを最大化するために、削除する必要がある 0 の数を最小限に抑えます。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。