So teilen Sie Buchstabenintervalle in PHP auf

Die Zeichenfolge S besteht aus Kleinbuchstaben. Wir müssen diese Zeichenfolge in so viele Segmente wie möglich unterteilen, und derselbe Buchstabe erscheint nur in einem der Segmente. Gibt eine Liste zurück, die die Länge jedes Zeichenfolgenfragments darstellt. Heute stellen wir die Methode zur Aufteilung von Buchstabenintervallen vor.

Dividieren Sie das Buchstabenintervall

String S besteht aus Kleinbuchstaben. Wir müssen diese Zeichenfolge in so viele Segmente wie möglich unterteilen, und derselbe Buchstabe erscheint nur in einem der Segmente. Gibt eine Liste zurück, die die Länge jedes Zeichenfolgenfragments darstellt.

Beispiel 1:

输入：S = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：划分结果为 "ababcbaca", "defegde", "hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。

Tipps: Die Länge von

S liegt zwischen [1, 500]. S enthält nur Kleinbuchstaben „a“ bis „z“.

Ideen zur Problemlösung 1

Wenn Sie schneiden möchten, müssen Sie zwei Zeiger haben, den ersten und den letzten. Sobald Sie den Endzeiger bestimmt haben, können Sie den Startzeiger des nächsten Schnitts bestimmen. Durchlaufen Sie die Zeichenfolge. Wenn alle Zeichen im gescannten Teil nur im gescannten Bereich erscheinen, können Sie sie ausschneiden. Die gescannten grünen Zeichen im Bild unten entsprechen nicht der am weitesten entfernten Position jenseits von 8. Wenn Sie bei 8 schneiden, werden die Zeichen [0:8] an keiner anderen Stelle angezeigt.

behalten Sie „Die am weitesten entfernte Position, zu der die gescannten Zeichen gelangen können“. Beim Scannen an diese Position werden die ausgeschnittenen Zeichen später nicht angezeigt. Aktualisieren Sie den Startzeiger und bereiten Sie sich auf den nächsten Schnitt vor.

Einige Variablen

maxPos Eine Karte, die die am weitesten entfernte Position jedes Buchstabens aufzeichnet. Start ist die Startposition des Schneidens. scannenCharMaxPos Die am weitesten entfernte Position, zu der die gescannten Zeichen gehen können.

class Solution {
    /** 
    * @param String $S 
    * @return Integer[] 
    */
    function partitionLabels($S) {
        $maxPos = [];
        $length = strlen($S);
        for ($i = 0; $i < $length; $i++) { // 存放字母与它的最远位置
            $maxPos[$S[$i]] = $i;
        }
        $res = [];
        $start = 0;                        // 待切割的起始位置
        $scannedCharMaxPos = 0;            // 已扫描的字符中最远的位置
        for ($i = 0; $i < $length; $i++) {
            $curCharMaxPos = $maxPos[$S[$i]]; // 当前扫描的字符的最远位置
            $scannedCharMaxPos = max($scannedCharMaxPos, $curCharMaxPos); // 更新「已扫描的字符中最远的位置」
            if ($i == $scannedCharMaxPos) { // 正好扫描到「已扫描的字符的最远位置」，到达切割点
                $res[] = $i - $start + 1;
                $start = $i + 1;              // 更新，下一个待切割的字符串的起始位置
            }
        }
        return $res;
    }}

Empfohlenes Lernen: php-Video-Tutorial

Das obige ist der detaillierte Inhalt vonSo teilen Sie Buchstabenintervalle in PHP auf. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!