データ構造とアルゴリズム: 文字列の分割とバランス

[[441873]]

バランスの取れた文字列を分割する

LeetCode の問題へのリンク: https://leetcode-cn.com/problems/split-a-string-in-balanced-strings

バランスの取れた文字列では、「L」文字と「R」文字の数は同じです。

バランスの取れた文字列 s が与えられた場合、それをできるだけ多くのバランスの取れた文字列に分割するように求められます。

注意: 分割によって取得される各文字列はバランスの取れた文字列である必要があります。

分割によって取得できるバランスの取れた文字列の最大数を返します。

例1:

入力: s = "RLRRLLRLRL"
出力: 4
説明: は「RL」、「RRLL」、「RL」、「RL」に分割でき、各部分文字列には同じ数の「L」と「R」が含まれます。

例2:

入力: s = "RLLLLRRRLR"
出力: 3
説明: は「RL」、「LLLRRR」、「LR」に分割でき、各部分文字列には同じ数の「L」と「R」が含まれます。

例3:

入力: s = "LLLLRRRR"
出力: 1
説明: s は「LLLLRRRR」としてのみ残ります。

例4:

入力: s = "RLRRRLLRLL"
出力: 2
説明: は「RL」、「RRRLLRLL」に分割でき、各部分文字列には同じ数の「L」と「R」が含まれます。

アイデア

この質問は複雑に思えるかもしれませんが、実は非常に単純な貪欲問題です。貪欲に関しては、貪欲アルゴリズムの詳細な説明をここに載せています。これは知っておくべきです!

前から後ろへトラバースし、バランスの取れた部分文字列に遭遇する限り、カウントは +1 となり、1 回トラバースできます。

局所最適: 前から後ろへ走査し、バランスの取れた部分文字列に遭遇するたびにカウントする

グローバル最適性: 最もバランスの取れた部分文字列がカウントされます。

局所最適性は、全体最適性につながる可能性があります。反例を挙げられない場合は、貪欲性を試してください。

たとえば、LRLR 自体はバランスの取れた部分文字列ですが、LR に遭遇すると分割される可能性があります。

C++ コードは次のとおりです。

クラスソリューション{
公共：
 int balancedStringSplit(文字列 s) {
 int結果 = 0;
整数 カウント= 0;
 ( int i = 0; i < s.size ( ) ); i++) {
            s[i] == 'R'の場合、カウント++;
それ以外 カウント--;  
            count == 0 の場合、結果 ++;
        }
結果を返します。
    }
 };

拡大する

生徒の中には、あなたの推論は信頼できず、数学的な証明がないと考える人もいるかもしれません。どうすればそれが合理的だと言えるのでしょうか? 局所最適が全体最適につながることをどのように示すことができるのでしょうか?

数学的な証明には、一般的に 2 つの方法があります。

数学的帰納法
反証による証明

厳密な数学的証明を本当に提供したい場合、それは実際のところ練習問題や面接の範囲を超えています。

したがって、貪欲問題の思考プロセスは次のようになります。局所最適解が大域最適解につながる可能性がある場合は、反例を挙げてみます。反例を挙げることができない場合は、貪欲解を試します。

その他の言語

ジャワ

クラスソリューション{
公共  int balancedStringSplit(文字列 s) {
 int結果 = 0;
整数 カウント= 0;
 ( int i = 0; i < s.length(); i++) {
            s.charAt(i) == 'R'の場合、カウント++;
それ以外 カウント--;  
            count == 0 の場合、結果 ++;
        }
結果を返します。
    }
 }

JavaScript

 var balancedStringSplit =関数(s) {
    let res = 0, total = 0; //res はバランスの取れた文字列の数、total は現在の"R"文字と"L"文字の差です
for (let c of s){// 文字列の各文字を走査する
        //先頭の文字数の差は 0 なので、トラバースするときに最初に文字数の差を変更する必要があります。そうしないと、結果の数に影響します。
        total += c === 'R' ? 1:-1; // "R"に遭遇するとtotal++; "L"に遭遇するとtotal --  
        if(total === 0) res++; // 「R」と「L」の数が同じであれば、バランスの取れた文字列とみなすことができます
    }
 resを返します。
 };