Comment diviser les intervalles de lettres en PHP

La chaîne S est composée de lettres minuscules. Nous devons diviser cette chaîne en autant de segments que possible, et la même lettre n'apparaîtra que dans l'un des segments. Renvoie une liste représentant la longueur de chaque fragment de chaîne. Aujourd'hui, nous allons présenter la méthode de division des intervalles de lettres.

Divisez l'intervalle des lettres

La chaîne S est composée de lettres minuscules. Nous devons diviser cette chaîne en autant de segments que possible, et la même lettre n'apparaîtra que dans l'un des segments. Renvoie une liste représentant la longueur de chaque fragment de chaîne.

Exemple 1 :

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

Conseils : La longueur de

S est comprise entre [1 500]. S ne contient que des lettres minuscules de « a » à « z ».

Idées de résolution de problèmes 1

Si vous souhaitez couper, vous devez avoir deux pointeurs, le premier et le dernier. Une fois que vous avez déterminé le pointeur de fin, vous pouvez déterminer le pointeur de début de la prochaine coupe. Parcourez la chaîne. Si tous les caractères de la partie numérisée apparaissent uniquement dans la plage numérisée, vous pouvez la couper. Les caractères verts numérisés dans l'image ci-dessous ne correspondent pas à la position la plus éloignée au-delà de 8. Si vous coupez à 8, les caractères [0:8] n'apparaîtront pas ailleurs.

maintenir "La position la plus éloignée vers laquelle les caractères numérisés peuvent aller". Lors de la numérisation vers cette position, les caractères coupés n'apparaîtront pas plus tard. Mettez à jour le pointeur de départ et préparez-vous pour la prochaine coupe.

Quelques variables

maxPos Une carte qui enregistre la position la plus éloignée correspondant à chaque lettre. start est la position de départ de la coupe. scanCharMaxPos La position la plus éloignée vers laquelle les caractères numérisés peuvent aller.

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;
    }}

Apprentissage recommandé : Tutoriel vidéo php

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!